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

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$.
• 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.