# A Construction of a Cipher from a Single Pseudorandom Permutation

A paper from 1997 A construction of a cipher from a single pseudorandom permutation proposes a cipher in which The message block is XORed with K1 before applying F [a single random permutation], and the outcome is XORed with K2. The authors state We show that the resulting cipher is secure (when the permutation is random or pseudorandom)

I found one paper Limitations of the Even-Mansour Construction that describes its severe limitations, but it still provoked some questions:

1. Is there any means to make a similarly simple cipher secure (even in theory)? How?
2. Might repeating further rounds make it secure against DCA?
3. Is there a similar cipher that 'is' useful by modern standards?
• For points 1 and 3 - your question reminds me of the Skein hash family. It describes a (relatively) simple PRP design with multiple rounds. The articles as well decribe usage for PRNG, cipher, KDF.. – gusto2 Nov 11 '17 at 14:02

## 1 Answer

Even-Mansour is not as severely limited as you make it sound. The success probability for an attacker of Even-Mansour has been shown in various papers to be at best $$\text{Adv}^{SPRP}_{EM_{K_1, K_2}}(q, p) \le \frac{2qp}{2^n}\,,$$ where $q$ is the amount of black-box queries you make to the cipher (read: known or chosen plaintexts), $p$ the number of queries you make to the permutation (read: bruteforce), and $n$ the bit width of the permutation. The same security bound applies to the single-key variant $$\text{SEK}_K(x) = P(x \oplus K) \oplus K.$$ Now, this means that, unlike an optimal block cipher, in which no matter how much data you collect you still expect around $2^n$ computational effort to break it, here by collecting $q$ plaintexts the effort goes down to $2^n/q$.

Now, to answer your questions:

• Even-Mansour is already secure, as long as you adequately deal with the above caveats. For example, if you choose your permutation to be, say, 512 bits wide, you have nothing to fear from any realistic attacker.

• Yes, iterating several permutations does give you better security. For example, the key-alternating cipher (or iterated Even-Mansour) $$\text{KAC}_{K_0, K_1, K_2,\dots,K_t}(x) = P_t(P_1(x \oplus K_0) \oplus K_1) \dots) \oplus K_t$$ achieves better security $$\text{Adv}^{SPRP}_{\text{KAC}_{K_0, K_1, K_2,\dots,K_t}}(q,p_1,p_2,\dots,p_t) \le \frac{4^tqp_1p_2\dots p_t}{2^{nt}}\,,$$ which quickly converges to optimal as $t$ grows.

• As seen above, iterating Even-Mansour is an effective way to strengthen the cipher. In practice, however, having several independent permutations and keys is inconvenient, and so you see designs that use a single permutation along with multiple round keys, each derived from a single master key. The AES is one such design, with the public permutation—the round function—being weaker than a random permutation but efficient to compute. This is a very successful design principle, and you will find many other ciphers following the same strategy.