Re: new coreutil? shuffle - randomize file contents

[Paul Eggert]

Frederik Eaton <address@hidden> writes:

> How about this: Put an upper limit on the number of samples that your
> adversary will be able to try before the earth blows up.

But that's not how adversarial attacks work.  They work by exploiting
flaws in your pseudorandom number generator.

Thus, for example, it's possible that by looking at the first half of
the pseudorandom output, the adversary would be able to deduce
information about the seed that you used, and thus they'll have extra
information about what the second half of the output will look like;
this is information that they wouldn't be able to guess if the output
were truly random.  The application to high-stakes poker games should
be obvious.

This may help to explain the results I already referred to in
<http://www.maa.org/mathland/mathtrek_10_16_00.html>.  From first
principles, to randomize a deck of 52 cards, you need about lg (52!)
random bits, which is about 220 random bits.  If each shuffle divides
the deck in half and then picks halves at random to interleave, then
it introduces about 50 bits of information, and you should need about
5 shuffles to randomize the deck.  Actual shuffles aren't that good,
though, and there are a few other factors, so you'll need 6 or 7
shuffles to randomize a real deck, depending on whether you listen to
the guys from Stanford or the guys from Oxford.  If you could get by
with a lot fewer shuffles, I'd expect those bright guys at Stanford
and Oxford would have figured it out by now.

Similarly, if you have a deck of 10 million cards, you'll need about
lg (1e7!) random bits, which is about 220 million random bits.  Notice
that the problem does not scale linearly: here you need 22 times as
many random bits as records, even though to shuffle a 52-card deck you
need only about 5 times as many random bits as records.  If you cut
this huge deck and half and shuffle it, you'll need more than 22
shuffles to randomize it.

(I agree that all this is overkill for non-adversarial applications.)