An Enciphering Scheme
Based on a Card Shuffle
Viet
Tung Hoang (
Ben
Morris (
Phillip
Rogaway (
Abstract:
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.