I've read recently the paper "Minimalism in Cryptography: The Even-Mansour Scheme Revisited" by Dunkelman, Keller and Shamir where it is claimed that the following construction (Single-Key EM) is secure:

$$C=K\oplus E(P\oplus K)$$

with $E$ being a publicly known fixed permutation.

Is there any reason not to use the above scheme (as block cipher) with AES-128 and key $0^{128}$ as $E$?

As for the reasons why somebody may want to use it:

  • It can provide smaller implementations, enabling the hard-coding of the round constants
  • It may be faster for the same reason
  • It is more key-agile, allowing for much faster key switches (e.g. in a hashing / KFB scenario)
  • $\begingroup$ I guess that you might rather want to refer to the algorithm as Single-Key EM in the title as well. XTS seems to have some additional properties that are not included in this scheme (and is treated as a mode of encryption rather than a block cipher). $\endgroup$
    – Maarten Bodewes
    Commented Nov 1, 2015 at 16:27
  • $\begingroup$ @MaartenBodewes, fixed. Note that XTS $\neq$ XEX $\neq$ Single-Key EM as XTS uses two keys, XEX is XTS with one key and Single-Key EM is the here described scheme. $\endgroup$
    – SEJPM
    Commented Nov 1, 2015 at 17:09

1 Answer 1


This is considered in §6 of Bogdanov et al., who go on to devise an alternative 2-round AES-based Even-Mansour cipher—$\text{AES}^2$. The problem is, essentially, that 1-round Even-Mansour is only secure up to $2^{n/2}$ blockcipher queries, for an $n$-bit block. Specifically, a collision between $\text{SEM}_K(P) \oplus P$ and $E(P) \oplus P$ immediately reveals $K$ (cf. §4.2 of Dunkelman-Keller-Shamir).

In general, you want an Even-Mansour cipher targeting $n$-bit security to have block size $2n$. This is the case with, e.g., Salsa20 and ChaCha's core functions, which are Even-Mansour-like, target 256-bit security, and work on 512-bit blocks. Several permutation-based CAESAR candidates, such as Prøst or Minalpher, work similarly.

  • $\begingroup$ Very good answer! Great resources, good job! $\endgroup$ Commented Mar 5, 2020 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.