Dr. Miracle Presents Research at Cryptology Conference

December 26, 2017 / By: UST CISC Department

CISC Assistant Professor Sarah Miracle recently presented a paper at the 23rd Annual International Conference on the Theory and Application of Cryptology and Information Security (AsiaCrypt) in Hong Kong, China. The paper detailed joint research conducted by Sarah Miracle and CISC Associate Professor Scott Yilek.

Since its inception, AsiaCrypt has been dedicated to furthering the science and practice of designing computation and communication systems which are secure in the presence of adversaries, and is one of the three flagship conferences of the International Association of Cryptologic Research (IACR). The full title and abstract are below.



Cycle Slicer: An Algorithm for Building Permutations on Special Domains


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 SX, 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).