An Enciphering Scheme Based on a Card Shuffle
Viet Tung Hoang,
Ben Morris, and
We introduce the swap-or-not shuffle and show that the technique
gives rise to a new method to convert a pseudorandom function
(PRF) into a pseudorandom permutation (PRP) (or, alternatively, to
directly build a confusion/diffusion blockcipher). We then prove that
swap-or-not has excellent quantitative security bounds, giving a
Luby-Rackoff type result that ensures security (assuming an ideal round function)
to a number of adversarial queries that is nearly the size of the
construction.s domain. Swap-or-not provides a direct solution for building
a small-domain cipher and achieving format-preserving encryption,
yielding the best bounds known for a practical scheme for enciphering
credit-card numbers. The analysis of swap-or-not is based on the theory
of mixing times of Markov chains.
Citation: V. Hoang, B. Morris, and P. Rogaway.
An Enciphering Scheme Based on a Card Shuffle.
Availability: Proceedings version available in pdf.