Paper 2015/851

Beyond-Birthday-Bound Security for Tweakable Even-Mansour Ciphers with Linear Tweak and Key Mixing

Benoît Cogliati and Yannick Seurin


The iterated Even-Mansour construction defines a block cipher from a tuple of public $n$-bit permutations $(P_1,\ldots,P_r)$ by alternatively xoring some $n$-bit round key $k_i$, $i=0,\ldots,r$, and applying permutation $P_i$ to the state. The \emph{tweakable} Even-Mansour construction generalizes the conventional Even-Mansour construction by replacing the $n$-bit round keys by $n$-bit strings derived from a master key \emph{and a tweak}, thereby defining a tweakable block cipher. Constructions of this type have been previously analyzed, but they were either secure only up to the birthday bound, or they used a nonlinear mixing function of the key and the tweak (typically, multiplication of the key and the tweak seen as elements of some finite field) which might be costly to implement. In this paper, we tackle the question of whether it is possible to achieve beyond-birthday-bound security for such a construction by using only linear operations for mixing the key and the tweak into the state. We answer positively, describing a 4-round construction with a $2n$-bit master key and an $n$-bit tweak which is provably secure in the Random Permutation Model up to roughly $2^{2n/3}$ adversarial queries.

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

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
tweakable block cipheriterated Even-Mansour cipherkey-alternating cipherbeyond-birthday-bound security
Contact author(s)
benoitcogliati @ hotmail fr
yannick seurin @ m4x org
2015-09-07: revised
2015-09-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benoît Cogliati and Yannick Seurin},
      title = {Beyond-Birthday-Bound Security for Tweakable Even-Mansour Ciphers with Linear Tweak and Key Mixing},
      howpublished = {Cryptology ePrint Archive, Paper 2015/851},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.