Cryptology ePrint Archive: Report 2014/953

The Related-Key Security of Iterated Even-Mansour Ciphers

Pooya Farshim and Gordon Procter

Abstract: The simplicity and widespread use of blockciphers based on the iterated Even--Mansour (EM) construction has sparked recent interest in the theoretical study of their security. Previous work has established their strong pseudorandom permutation and indifferentiability properties, with some matching lower bounds presented to demonstrate tightness. In this work we initiate the study of the EM ciphers under related-key attacks which, despite extensive prior work, has received little attention. We show that the simplest one-round EM cipher is strong enough to achieve non-trivial levels of RKA security even under chosen-ciphertext attacks. This class, however, does not include the practically relevant case of offsetting keys by constants. We show that two rounds suffice to reach this level under chosen-plaintext attacks and that three rounds can boost security to resist chosen-ciphertext attacks. We also formalize how indifferentiability relates to RKA security, showing strong positive results despite counterexamples presented for indifferentiability in multi-stage games.

Category / Keywords: secret-key cryptography / Even-Mansour, related-key attack, public permutation, ideal cipher, indifferentiability

Date: received 20 Nov 2014, last revised 21 Nov 2014

Contact author: gtprocter at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20141121:094832 (All versions of this report)

Short URL: ia.cr/2014/953

Discussion forum: Show discussion | Start new discussion