Abstract | ||
---|---|---|
A t-round key-alternating cipher (also called iterated EvenMansour cipher) can be viewed as an abstraction of AES. It defines a cipher E from t fixed public permutations P-1, ... ,P-t: {0,1}(n) -> {0,1}(n) and a key k = k(0) parallel to center dot center dot center dot parallel to k(t) is an element of {0,1}(n(t+1)) by setting E-k(x) = k(t)circle plus P-t(k(t-1) circle plus Pt-1 (center dot center dot center dot k(1)circle plus P-1(k(0)circle plus x)center dot center dot center dot)). The indistinguishability of E-k from a truly random permutation by an adversary who also has oracle access to the (public) random permutations P-1,P- ..., P-t was investigated in 1997 by Even and Mansour for t = 1 and for higher values of t in a series of recent papers. For t = 1, Even and Mansour proved indistinguishability security up to 2(n/2) queries, which is tight. Much later Bogdanov et al. (2011) conjectured that security should be 2(t/t+1n) queries for general t, which matches an easy distinguishing attack (so security cannot be more). A number of partial results have been obtained supporting this conjecture, besides Even and Mansour's original result for t = 1: Bogdanov et al. proved security of 2(2/3n) for t >= 2, Steinberger (2012) proved security of 2(3/4n) for t >= 3, and Lampe, Patarin and Seurin (2012) proved security of 2(t/t+2n) for all even values of t, thus "barely" falling short of the desired 2(t/t+1n). Our contribution in this work is to prove the long-sought-for security bound of 2 n, up to a constant multiplicative factor depending on t. Our method is essentially an application of Patarin's H-coefficient technique. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-642-55220-5_19 | ADVANCES IN CRYPTOLOGY - EUROCRYPT 2014 |
DocType | Volume | ISSN |
Journal | 8441 | 0302-9743 |
Citations | PageRank | References |
63 | 1.48 | 30 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Shan Chen | 1 | 63 | 1.48 |
John P. Steinberger | 2 | 329 | 18.30 |