**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Revisiting Iterated Attacks in the Context of Decorrelation Theory

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 perfect cipher C* based on all bits. Vaudenay showed that a 2d-decorrelated cipher resists to iterated attacks of order d. when iterations have 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. I.e., whether decorrelation of order 2d-1 could be sufficient. 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 negatively. For those questions, we provide two counter-intuitive examples. We also deal with adaptive iterated adversaries who can make both plaintext and ciphertext queries in which the future queries are dependent on the past queries. We show that decorrelation of order 2d protects against these attacks of order d. We also study the generalization of these distinguishers for iterations making non-binary outcomes. Finally, we measure the resistance against two well-known statistical distinguishers, namely, differential-linear and boomerang distinguishers and show that 4-decorrelation degree protects against these attacks.

Official source

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 concepts

Loading

Related publications

Loading

Related concepts (16)

Cipher

In cryptography, a cipher (or cypher) is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common ter

Vigenère cipher

The Vigenère cipher (viʒnɛːʁ) is a method of encrypting alphabetic text where each letter of the plaintext is encoded with a different Caesar cipher, whose increment is determined by the correspond

Plaintext

In cryptography, plaintext usually means unencrypted information pending input into cryptographic algorithms, usually encryption algorithms. This usually refers to data that is transmitted or stored

Related publications (9)

Loading

Loading

Loading

Asli Bay, Atefeh Mashatan, Serge Vaudenay

Decorrelation Theory deals with general adversaries who are mounting iterated attacks, i.e., attacks in which an adversary is allowed to make d queries in each iteration with the aim of distinguishing a random cipher C from the ideal random cipher C^*. A bound for a non-adaptive iterated distinguisher of order d, who is making plaintext (resp. ciphertext) queries, against a 2d-decorrelated cipher has already been derived by Vaudenay at EUROCRYPT '99. He showed that a 2d-decorrelated cipher resists against iterated non-adaptive distinguishers of order d when iterations have almost no common queries. More recently, Bay et al. settled two open problems arising from Vaudenay's work at CRYPTO '12, yet they only consider non-adaptive iterated attacks. Hence, a bound for an adaptive iterated adversary of order d, who can make both plaintext and ciphertext queries, against a 2d-decorrelated cipher has not been studied yet. In this work, we study the resistance against this distinguisher and we prove the bound for an adversary who is making adaptive plaintext and ciphertext queries depending on the previous queries to an oracle.

2012Inspired by fast correlation attacks on stream ciphers, we present a stream cipher-like construction for a public-key cryptosystem whose security relies on two problems: finding a low-weight multiple of a given polynomial and a Hidden Correlation problem. We obtain a weakly secure public-key cryptosystem we call TCHo (as for Trapdoor Cipher, Hardware Oriented). Using the Fujisaki-Okamoto construction, we can build an hybrid cryptosystem, TCHon-FO, resistant against adaptive chosen ciphertext attacks.

Asli Bay, Atefeh Mashatan, Serge Vaudenay

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.