Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / block cipher, ideal cipher, known-key attacks, iterated Even-Mansour cipher, key-alternating cipher, indifferentiability, correlation intractability

Original Publication (with major differences): IACR-FSE-2016

Date: received 20 Apr 2016

Contact author: yannick seurin at m4x org

Available format(s): PDF | BibTeX Citation

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

Version: 20160421:205442 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]