Paper 2016/394

Strengthening the Known-Key Security Notion for Block Ciphers

Benoît Cogliati and Yannick Seurin

Abstract

We reconsider the formalization of known-key attacks against ideal primitive-based block ciphers. This was previously tackled by Andreeva, Bogdanov, and Mennink (FSE 2013), who introduced the notion of known-key indifferentiability. Our starting point is the observation, previously made by Cogliati and Seurin (EUROCRYPT 2015), that this notion, which considers only a single known key available to the attacker, is too weak in some settings to fully capture what one might expect from a block cipher informally deemed resistant to known-key attacks. Hence, we introduce a stronger variant of known-key indifferentiability, where the adversary is given multiple known keys to ``play'' with, the informal goal being that the block cipher construction must behave as an independent random permutation for each of these known keys. Our main result is that the 9-round iterated Even-Mansour construction (with the trivial key-schedule, i.e., the same round key xored between permutations) achieves our new ``multiple'' known-keys indifferentiability notion, which contrasts with the previous result of Andreeva et al. that one single round is sufficient when only a single known key is considered. We also show that the 3-round iterated Even-Mansour construction achieves the weaker notion of multiple known-keys sequential indifferentiability, which implies in particular that it is correlation intractable with respect to relations involving any (polynomial) number of known keys.

Note: An abridged version appears in the proceedings of FSE 2016. This is the full version.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in FSE 2016
Keywords
block cipherideal cipherknown-key attacksiterated Even-Mansour cipherkey-alternating cipherindifferentiabilitycorrelation intractability
Contact author(s)
yannick seurin @ m4x org
History
2016-04-21: received
Short URL
https://ia.cr/2016/394
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/394,
      author = {Benoît Cogliati and Yannick Seurin},
      title = {Strengthening the Known-Key Security Notion for Block Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2016/394},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/394}},
      url = {https://eprint.iacr.org/2016/394}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.