How to Encipher Messages on a Small Domain Deterministic Encryption and the Thorp Shuffle
Ben Morris, Phillip Rogaway, Till Stegers · 2009
We analyze the security of the Thorp shuffle, or, equivalently, a maximally unbalanced Feistel network. Roughly said, the Thorp shuffle on N cards mixes any N 1−1/r of them in O(r lg N) steps. Correspondingly, making O(r) passes of maximally unbalanced Feistel over an n-bit string ensures CCA-security to 2 n(1−1/r) queries. Our results, which employ Markov-chain techniques, enable the construction of a practical and provably-secure blockcipher-based scheme for deterministically enciphering credit card numbers and the like using a conventional blockcipher.