Partition and mix: generalizing the swap-or-not shuffle

Abstract

Card shuffle algorithms have been studied from a cryptographic point of view with applications to format preserving encryption. In this work, we naturally extend the swap-or-not shuffle, proposed by Hoang, Morris and Rogaway at Crypto 2012, by replacing a perfect matching used in each round by a keyed partition with a certain uniform property. The resulting construction, dubbed the partition-and-mix (or simply PM) shuffle, is proved to be secure up to (1 - delta)N queries for any delta > 0 and the domain size N, while the number of rounds is significantly reduced compared to the swap-or-not. We give concrete examples of the keyed partitions that provide security as well as allow efficient implementation in practice. Such uniform keyed partitions seem of independent interest. The partition-and-mix shuffle might also be viewed as an alternative block cipher structure that extends the domain of a small block cipher operating on each block of the partition.