Welcome to the resource topic for 2016/865
Title:
Reverse Cycle Walking and Its Applications
Authors: Sarah Miracle, Scott Yilek
Abstract:We study the problem of constructing a block-cipher on a “possibly-strange” set \mathcal S using a block-cipher on a larger set \mathcal T. Such constructions are useful in format-preserving encryption, where for example the set \mathcal S might contain “valid 9-digit social security numbers” while \mathcal 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 \mathcal S is a constant fraction of the size of \mathcal T, cycle walking allows one to encipher a point x \in \mathcal S by applying the block-cipher on \mathcal T a small /expected/ number of times and O(N) times in the worst case, where N = |\mathcal 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 \mathcal T from O(N) to O(\log N). Additionally, when the underlying block-cipher on \mathcal T is secure against q = (1-\epsilon)N adversarial queries, we show that applying reverse cycle walking gives us a cipher on \mathcal 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.
ePrint: https://eprint.iacr.org/2016/865
Talk: https://www.youtube.com/watch?v=1kZw9mPKHaw
Slides: https://iacr.org/cryptodb/archive/2016/ASIACRYPT/presentation/27919.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .