Paper 2017/873

Cycle Slicer: An Algorithm for Building Permutations on Special Domains

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 $\mathcal{X}$ to construct a cipher on a smaller domain $\mathcal{S} \subseteq \mathcal{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 $\mathcal{S}$ is large relative to the size of $\mathcal{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 $\mathcal{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).

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in ASIACRYPT 2017
Keywords
format-preserving encryptionsmall-domain block ciphersMarkov chainsmatchings
Contact author(s)
syilek @ stthomas edu
History
2017-09-13: received
Short URL
https://ia.cr/2017/873
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/873,
      author = {Sarah Miracle and Scott Yilek},
      title = {Cycle Slicer: An Algorithm for Building Permutations on Special Domains},
      howpublished = {Cryptology ePrint Archive, Paper 2017/873},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/873}},
      url = {https://eprint.iacr.org/2017/873}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.