**Tweaking Even-Mansour Ciphers**

*Benoît Cogliati and Rodolphe Lampe and Yannick Seurin*

**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.

**Category / Keywords: **secret-key cryptography / tweakable block cipher, CLRW construction, key-alternating cipher, Even-Mansour construction, H-coefficients technique, coupling technique

**Original Publication**** (with major differences): **IACR-CRYPTO-2015

**Date: **received 2 Jun 2015

**Contact author: **yannick seurin at m4x org

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

**Note: **An abridged version appears in the proceedings of CRYPTO 2015. This is the full version.

**Version: **20150608:093700 (All versions of this report)

**Short URL: **ia.cr/2015/539

[ Cryptology ePrint archive ]