Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations

How can we generate a permutation of the numbers 1 through n such that, given the history so far, it is hard to guess the next element? The twist is that the permutation generator (the "Dealer") has limited memory, while the "Guesser" has unlimited memory. With unbounded memory (or even just n bits), the Dealer can generate a truly random permutation, for which the expected number of correct guesses is ln n.Our main results establish tight bounds for the relationship between the guessing probability and the memory m required to generate the permutation. We suggest a method for an m-bit Dealer that operates in constant time per turn and ensures that any Guesser can correctly guess only O(n/m + log m) cards in expectation. The method is fully transparent, requiring no hidden information from the Dealer (i.e., it is "open book" or "whitebox").We further show that this bound is essentially optimal, even if the Dealer is allowed to use secret memory. Specifically, for any m-bit Dealer, there is a (computationally powerful) Guesser that achieves Ω(n/m + log m) correct guesses in expectation. We point out that the assumption that the Guesser is computationally powerful is necessary: under cryptographic assumptions, there exists a low-memory Dealer that can fool any computationally bounded Guesser.Finally, we present an O(n) bit memory Dealer that generates perfectly random permutations and operates in constant time per turn.