Cryptology ePrint Archive: Report 2015/539

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:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]