Resistance against Iterated Attacks by Decorrelation Revisited

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 2

d

-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 2

d

 − 1 is not sufficient. We do this by providing a counterexample consisting of a cipher decorrelated to the order 2

d

 − 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 2

d

which can be broken by an iterated attack of order 1 having a high probability of common queries.