Paper 2015/539 Original: eprint.iacr.org/2015/539 ↗

Tweaking Even-Mansour Ciphers

Abstract

We study how to construct efficient tweakable block ciphers in the Random Permutation model, where all parties have access to public random permutation oracles. We propose a construction that combines, more efficiently than by mere black-box composition, the CLRW construction (which turns a traditional block cipher into a tweakable block cipher) of Landecker et al. (CRYPTO 2012) and the iterated Even-Mansour construction (which turns a tuple of public permutations into a traditional block cipher) that has received considerable attention since the work of Bogdanov et al. (EUROCRYPT 2012). More concretely, we introduce the (one-round) tweakable Even-Mansour (TEM) cipher, constructed from a single $n$-bit permutation $P$ and a uniform and almost XOR-universal family of hash functions $(H_k)$ from some tweak space to $\{0,1\}^n$, and defined as $(k,t,x)\mapsto H_k(t)\oplus P(H_k(t)\oplus x)$, where $k$ is the key, $t$ is the tweak, and $x$ is the $n$-bit message, as well as its generalization obtained by cascading $r$ independently keyed rounds of this construction. Our main result is a security bound up to approximately $2^{2n/3}$ adversarial queries against adaptive chosen-plaintext and ciphertext distinguishers for the two-round TEM construction, using Patarin's H-coefficients technique. We also provide an analysis based on the coupling technique showing that asymptotically, as the number of rounds $r$ grows, the security provided by the $r$-round TEM construction approaches the information-theoretic bound of $2^n$ adversarial queries.