Reverse Cycle Walking and Its Applications
Sarah Miracle and Scott Yilek
We study the problem of constructing a block-cipher on a "possibly-strange" set S using a block-cipher on a larger set T. Such constructions are useful in format-preserving encryption, where for example the set S might contain "valid 9-digit social security numbers" while T might be the set of 30-bit strings. Previous work has solved this problem using a technique called cycle walking, first formally analyzed by Black and Rogaway. Assuming the size of S is a constant fraction of the size of T, cycle walking allows one to encipher a point x in S by applying the block-cipher on T a small /expected/ number of times and O(N) times in the worst case, where N = |T|, without any degradation in security. We introduce an alternative to cycle walking that we call /reverse cycle walking/, which lowers the worst-case number of times we must apply the block-cipher on T from O(N) to O(log N). Additionally, when the underlying block-cipher on T is secure against q = (1-e)N adversarial queries, we show that applying reverse cycle walking gives us a cipher on S secure even if the adversary is allowed to query all of the domain points. Such fully-secure ciphers have been the the target of numerous recent papers.
Sarah Miracle and Scott Yilek.
Reverse Cycle Walking and Its Application.
Advances in Cryptology - ASIACRYPT 2016 LNCS Vol 10031, pp 679-700, Springer 2016.