**Reverse Cycle Walking and Its Applications**

*Sarah Miracle and 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.

**Category / Keywords: **format-preserving encryption, small-domain block ciphers, Markov chains

**Original Publication**** (in the same form): **IACR-ASIACRYPT-2016

**Date: **received 6 Sep 2016, last revised 10 Sep 2016

**Contact author: **sarah miracle at stthomas edu, syilek at stthomas edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20160910:153750 (All versions of this report)

**Short URL: **ia.cr/2016/865

[ Cryptology ePrint archive ]