International Association for Cryptologic Research
In this paper, the authors introduced a block cipher construction based on a single permutation. Their construction has since been lauded for its simplicity, yet also criticized for not providing the same security as other block ciphers against generic attacks. In this paper, the authors prove that if a small number of plaintexts are encrypted under multiple independent keys, the Even-Mansour construction surprisingly offers similar security as an ideal block cipher with the same block and key size. Note that this multi-key setting is of high practical relevance, as real-world implementations often allow frequent rekeying.