Paper 2016/894

Indifferentiability of 3-Round Even-Mansour with Random Oracle Key Derivation

Chun Guo and Dongdai Lin

Abstract

We revisit the Even-Mansour (EM) scheme with random oracle key derivation previously considered by Andreeva et al. (CRYPTO 2013). For this scheme, Andreeva et al. provided an indifferentiability (from an ideal $(k,n)$-cipher) proof for 5 rounds while they exhibited an attack for 2 rounds. Left open is the (in)differentiability of 3 and 4 rounds. We present a proof for the indifferentiability of 3 rounds and thus closing the aforementioned gap. This also separates EM ciphers with non-invertible key derivations from those with invertible ones in the full indifferentiability setting. Prior work only established such a separation in the weaker sequential-indifferentiability setting (ours, DCC, 2015). Our results also imply 3-round EM indifferentiable under multiple random known-keys, partially settling a problem left by Cogliati and Seurin (FSE 2016). The key point for our indifferentiability simulator is to pre-emptively obtain some chains of ideal-cipher-queries to simulate the structures due to the related-key boomerang property in the 3-round case. The length of such chains have to be as large as the number of queries issued by the distinguisher. Thus the situation somehow resembles the context of hash-of-hash $H^2$ considered by Dodis et al. (CRYPTO 2012). Besides, a technical novelty of our proof is the absence of the so-called distinguisher that completes all chains.

Note: In the earlier versions, the definitions for a G3-tuple to be "bad" are silly (although correct). We revise them. This leads to a slightly improved bound.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
blockcipherideal cipherindifferentiabilitykey-alternating cipheriterated Even-Mansour cipherH-coefficients technique.
Contact author(s)
guochun @ iie ac cn
History
2017-01-13: last of 2 revisions
2016-09-14: received
See all versions
Short URL
https://ia.cr/2016/894
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/894,
      author = {Chun Guo and Dongdai Lin},
      title = {Indifferentiability of 3-Round Even-Mansour with Random Oracle Key Derivation},
      howpublished = {Cryptology ePrint Archive, Paper 2016/894},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/894}},
      url = {https://eprint.iacr.org/2016/894}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.