Sometimes-Recurse Shuffle - Almost-Random Permutations in Logarithmic Expected Time.
Ben Morris, Phillip Rogaway · 2013
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 Θ(lgN) calls, on average, to the one-bit-output random function. The approach is based on card shuffling. The basic idea is to use the 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.