Frederik Eaton <[EMAIL PROTECTED]> 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.) _______________________________________________ Bug-coreutils mailing list Bug-coreutils@gnu.org http://lists.gnu.org/mailman/listinfo/bug-coreutils
