**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# Revisiting Iterated Attacks in the Context of Decorrelation Theory

Résumé

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

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Publications associées (9)

Chargement

Chargement

Chargement

Concepts associés (16)

Chiffre (cryptologie)

En cryptologie, un chiffre est une manière secrète d'écrire un message à transmettre, au moyen de caractères et de signes disposés selon une convention convenue au préalable. Plus précisément, le chi

Chiffre de Vigenère

vignette|Blaise de Vigenère.
Le chiffre de Vigenère est un système de chiffrement par substitution polyalphabétique dans lequel une même lettre du message clair peut, suivant sa position dans celui-ci

Texte en clair

En cryptographie, un texte en clair (ou message clair) désigne une information non chiffrée. Il s'oppose à un rendu inintelligible par un processus de chiffrement à toute personne non autorisée. Ce

Inspired 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.

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.

2012