The Mix-and-Cut Shuffle: Small-Domain Encryption Secure against N Queries

Authors

Thomas Ristenpart and Scott Yilek

Abstract

We provide a new shuffling algorithm, called Mix-and-Cut, that provides a provably-secure block cipher even for adversaries that can observe the encryption of all N=2^n domain points. Such fully secure ciphers are useful for format-preserving encryption, where small domains (e.g., n=30) are common and databases may well include examples of almost all ciphertexts. Mix-and-Cut derives from a general framework for building fully secure pseudorandom permutations (PRPs) from fully secure pseudorandom separators (PRSs). The latter is a new primitive that we treat for the first time. Our framework was inspired by, and uses ideas from, a particular cipher due to Granboulin and Pornin. To achieve full security for Mix-and-Cut using this framework, we give a simple proof that a PRP secure for (1-epsilon)N queries (recently achieved efficiently by Hoang, Morris, and Rogaway’s Swap-or-Not cipher) yields a PRS secure for N queries.

Reference

Thomas Ristenpart and Scott Yilek
The Mix-and-Cut Shuffle: Small-Domain Encryption Secure against N Queries.
Advances in Cryptology - CRYPTO 2013. LNCS Vol. 8042, pp. 392-409, R. Canetti and J. Garay eds., Springer, 2013.

Versions

Conference Version

See Also

Video of Presentation at CRYPTO
CRYPTO 2013