When Stream Cipher Analysis Meets Public-Key Cryptography

Serge Vaudenay
Springer, 2006
Conference paper

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.

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 concepts

Related publications

Serge Vaudenay
Springer, 2006
Conference paper

Abstract

Official source

https://infoscience.epfl.ch/record/110701?ln=en

About this result

Related concepts (9)

Related concepts

Related publications (2)

Related publications

Caesar cipher

In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code, or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of

Public-key cryptography

Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. K

Stream cipher

A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream (keystream). In a stream cipher, each plaintext digit is encrypted one at a time

Resistance against Adaptive Plaintext-Ciphertext Iterated Distinguishers

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

Revisiting Iterated Attacks in the Context of Decorrelation Theory

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

2014