**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: **ia.cr/2016/394

[ Cryptology ePrint archive ]