Counterexample

Summary

A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "student John Smith is not lazy" is a counterexample to the generalization “students are lazy”, and both a counterexample to, and disproof of, the universal quantification “all students are lazy.” In mathematics, the term "counterexample" is also used (by a slight abuse) to refer to examples which illustrate the necessity of the full hypothesis of a theorem. This is most often done by considering a case where a part of the hypothesis is not satisfied and the conclusion of the theorem does not hold. In mathematics In mathematics, counterexamples are often used to prove the boundaries of possible theorems. By using counterexamples to show that certain conjectures are false, mathematical researchers can then avoid going down blind alleys and learn to modify conjectures to p

Official source

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Related people

Related units

Related concepts

Related courses

Related lectures

, ,

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.

Springer2012

Counterexample

New counterexamples for sums-differences

New counterexamples for sums-differences