Resistance against
Iterated Attacks Revisited
Atefeh Mashatan (EPFL,
Serge Vaudenay (EPFL,
Abstract:
Iterated attacks are comprised of iterating adversaries who can make $d$
plaintext queries, in each iteration to compute a bit, and are trying to
distinguish between a random cipher $C$ and the ideal random cipher $C^*$
based on all bits. In EUROCRYPT '99, Vaudenay
showed that a $2d$-decorrelated cipher resists to iterated attacks of order
$d$ when iterations make almost no common queries. Then, he first asked what
the necessary conditions are for a cipher to resist a non-adaptive iterated
attack of order $d$. Secondly, he speculated that repeating a plaintext query
in different iterations does not provide any advantage to a non-adaptive
distinguisher. We close here these two long-standing open problems.
We show that, in order to resist non-adaptive iterated attacks of order $d$, decorrelation of order $2d-1$ is not sufficient. We do
this by providing a counterexample consisting of a cipher decorrelated
to the order $2d-1$ and a successful non-adaptive iterated attack of order
$d$ against it.
Moreover, we prove that the aforementioned claim is wrong by showing that a
higher probability of having a common query between different iterations can
translate to a high advantage of the adversary in distinguishing $C$ from
$C^*$. We provide a counterintuitive example consisting of a cipher decorrelated to the order $2d$ which can be broken by an
iterated attack of order 1 having a high probability of common queries.