How to Encipher Messages on a Small Domain: Deterministic Encryption and the Thorp Shuffle

Reference: Advances in Cryptology, CRYPTO 2009.

Abstract: 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