Re: 2011/541 proposal is not new
Posted by: djb
Date: 08 October 2011 15:41
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