A -round \emph{key-alternating cipher} (also called \emph{iterated
Even-Mansour cipher}) can be viewed as an abstraction of AES. It
defines a cipher from fixed public permutations and a key by setting . The
indistinguishability of from a truly random permutation by an
adversary who also has oracle access to the (public) random
permutations was investigated in 1997 by Even and
Mansour for and for higher values of in a series of recent
papers. For , Even and Mansour proved indistinguishability
security up to queries, which is tight. Much later Bogdanov
et al (2011) conjectured that security should be
queries for general , 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 : Bogdanov et al proved security of
for , Steinberger (2012) proved security
of for , and Lampe, Patarin and Seurin
(2012) proved security of for all even values of
, thus "barely" falling short of the desired
.
Our contribution in this work is to prove the long-sought-for security
bound of , up to a constant multiplicative factor
depending on . Our method is essentially an application of
Patarin's H-coefficient technique.
The proof contains some coupling-like and inclusion-exclusion ideas,
but the main trick that pushes the computations through is
to stick with the combinatorics and to
refrain from rounding any quantities too early.
For the reader's interest, we include a self-contained
tutorial on the H-coefficient technique.
@misc{cryptoeprint:2013/222,
author = {Shan Chen and John Steinberger},
title = {Tight security bounds for key-alternating ciphers},
howpublished = {Cryptology {ePrint} Archive, Paper 2013/222},
year = {2013},
url = {https://eprint.iacr.org/2013/222}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.