Ben Morris and
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 Θ(lg N) calls, on average, to the one-bit-output random function. The approach is based on card
shuffing. The basic idea is to use the sometimes-recurse transformation: lightly shuffe the deck (with
some other shuffe), cut the deck, and then recursively shuffle one of the two halves. Our work builds
on a recent paper of Ristenpart and Yilek.
Citation: Unpublished manuscript. Auguest 2013.
Availability: Available in pdf.