Paper 2016/865

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 $$ from $$ to $$. Additionally, when the underlying block-cipher on $$ is secure against $$ adversarial queries, we show that applying reverse cycle walking gives us a cipher on $$ 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.