Cycle Slicer: An Algorithm for Building Permutations on Special Domains

Authors

Sarah Miracle and Scott Yilek

Abstract

We introduce an algorithm called Cycle Slicer that gives new solutions to two important problems in format-preserving encryption: domain targeting and domain completion. In domain targeting, where we wish to use a cipher on domain X to construct a cipher on a smaller domain S subseteq X, using Cycle Slicer leads to a significantly more efficient solution than Miracle and Yilek's Reverse Cycle Walking (ASIACRYPT 2016) in the common setting where the size of S is large relative to the size of X. In domain completion, a problem recently studied by Grubbs, Ristenpart, and Yarom (EUROCRYPT 2017) in which we wish to construct a cipher on domain X while staying consistent with existing mappings in a lazily-sampled table, Cycle Slicer provides an alternative construction with better worst-case running time than the Zig-Zag construction of Grubbs et al. Our analysis of Cycle Slicer uses a refinement of the Markov chain techniques for analyzing matching exchange processes, which were originally developed by Czumaj and Kutylowski (Rand. Struct. & Alg. 2000).

Reference

Sarah Miracle and Scott Yilek.
Cycle Slicer: An Algorithm for Building Permutations on Special Domains
Advances in Cryptology - ASIACRYPT 2017. LNCS Vol. 10626, pp. 392-416, Springer, 2017.

Versions

ePrint Version

See Also

ASIACRYPT 2017