Cryptology ePrint Archive: Report 2013/560

Sometimes-Recurse Shuffle: Almost-Random Permutations in Logarithmic Expected Time

Ben Morris and Phillip Rogaway

Abstract: We describe a security-preserving construction of a random permutation of domain size~$N$ from a random function, the construction tolerating adversaries asking all~$N$ plaintexts, yet employing just $\Theta(\lg N)$ calls, on average, to the one-bit-output random function. The approach is based on card shuffling. The basic idea is to use the \textit{sometimes-recurse} transformation: lightly shuffle the deck (with some other shuffle), cut the deck, and then recursively shuffle one of the two halves. Our work builds on a recent paper of Ristenpart and Yilek.

Category / Keywords: secret-key cryptography / Card shuffling, format-preserving encryption, PRF-to-PRP conversion, mix-and-cut shuffle, pseudorandom permutations, sometimes-recurse shuffle, swap-or-not shuffle

Original Publication (in the same form): IACR-EUROCRYPT-2014

Date: received 3 Sep 2013, last revised 1 Apr 2014

Contact author: rogaway at cs ucdavis edu, morris@math ucdavis edu

Available format(s): PDF | BibTeX Citation

Note: Minor revisions and clarifications.

Version: 20140402:035151 (All versions of this report)

Short URL: ia.cr/2013/560

Discussion forum: Show discussion | Start new discussion