The 2011 Dunkelman--Keller--Shamir "New Single-Key Even-Mansour Scheme" was actually published at least ten years earlier. See, e.g., the 2001 Kilian--Rogaway J. Cryptology paper, specifically the "Setting k1=k2" subsection.

It's of course even more minimal to use the k1=k2 construction with only an encryption oracle in counter mode, without a decryption oracle. The cryptanalyst is limited by the inability to see the inverse, and also by the structure of the counters: if blocks are large then many input bits are constant. This usually reduces the number of rounds needed to protect against differential attacks.

I used the same K+F(K+n) structure in Salsa20 several years ago, with a 128-bit counter n, a 256-bit secret key K, and a 512-bit output block.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago

Dear Dan,

Thank you very much for bringing to our attention the Kilian-Rogaway [KR] paper, which we somehow missed. We will be happy to add this reference to the next revision of our paper.

Our paper contains many results such as the introduction of the new *slidex* attack and a description of its many applications to various cryptographic schemes. We understand that your only objection is related to the novelty of the single-key variant of the EM scheme, which is one of these results.

Rivest's original DESX scheme contained three independent keys. You correctly point out that the [KR] paper briefly mentions the idea of using the same pre/post whitening keys in DESX. In a similar way, the [EM] paper suggests the idea of eliminating the middle encryption key in the DESX construction. However, neither one of these papers explicitly talks about a scheme which performs BOTH changes simultaneously. Since we were interested in getting a minimal construction, we pointed out that such a combination is simpler than any one of the previous proposals. If you object to our proposal since it is a special case of the previous constructions, you should also object to the [EM] and [KR] proposals since they are also special cases of the previously discovered DESX construction.

A deeper problem with your argument is that you cannot deduce that the single and double key versions of EM have equivalent security from the fact that the two schemes have the same lower bound and the same upper bound proven on their security. This is true only if these bounds are TIGHT, which is exactly what we prove as the main technical result of our paper. Without this new result, one scheme could have a security matching the lower bound and the other scheme could have a security matching the upper bound, which would contradict your argument that the schemes are equivalent since the [KR] lower bound applies to both of them.

Finally, we would like to point out that the counter mode of operation you mention is used as a STREAM CIPHER, and in this category a one time pad is conceptually simpler. Our goal was to analyze the simplest possible BLOCK CIPHER, which is defined as a keyed collection of permutations over blocks of b bits, with no memorized state.



Edited 1 time(s). Last edit at 08-Oct-2011 14:50 by Orr.

Hi Orr,

The problem is that you say things like "The New Single-Key Even-Mansour Scheme" and "We develop our new variant of the Even-Mansour scheme" when in fact exactly the same K+F(K+n) construction has been known for many years. There's a serious risk that readers will give you credit for "SEM" when in fact you deserve none of that credit.

Rivest proposed K2+DES(K1+n,K0) as a way to improve the security of DES(n,K0). Kilian and Rogaway analyzed the security of K2+F(K1+n,K0) for uniform random keyed permutations F. (I understand that you're reporting tighter security bounds.)

Kilian and Rogaway mentioned that Even and Mansour had proposed K2+F(K1+n), and that this was tantamount to the special case |K0|=0 of the K2+F(K1+n,K0) construction. They also proposed simplifying K2+F(K1+n,K0) by taking K2=K1, producing K1+F(K1+n,K0), and they claimed that this didn't lose security. (I understand that you're proving something along these lines.)

Your "new" proposal K+F(K+n) is a special case of the Kilian--Rogaway proposal K1+F(K1+n,K0), namely the special case |K0|=0. Compared to the original K2+F(K1+n,K0) construction, you're taking K1=K2 as proposed by Kilian and Rogaway, and you're taking |K0|=0 as proposed by Even and Mansour (and discussed by Kilian and Rogaway).

You say that _simultaneously_ taking K1=K2 and |K0|=0 is new. I find this more than a little bit absurd. Have you been spending too much time talking to patent lawyers?

Two minutes on Google lead me to a 2002 eprint paper by Kurosawa, with the first paragraph discussing "F(x+S)+S" where "S is a secret mask" and "F is publicly accessible." You might correctly point out that Kurosawa's credits in the same paragraph are bogus, but you can't deny that he's talking about exactly your "minimal" block cipher.

As for further simplifications: I find it obvious that having _two_ cipher oracles, one for encryption F(n+S)+S and one for its inverse, is not as simple as having just the first oracle. Being unable to decrypt blocks puts a constraint on the mode of operation, but we can further simplify by choosing one mode of operation, namely counter mode, which of course doesn't need to decrypt blocks.

You seem to be complaining that the resulting stream cipher (e.g., Salsa20) isn't as simple as a one-time pad. Does it also bother you that your favorite block ciphers aren't as simple as a randomly generated codebook? The whole point here is to be able to simulate the large random objects using a _small_ key.

---D. J. Bernstein
Research Professor, Computer Science, University of Illinois at Chicago