TCHo: A Code-Based Cryptosystem

Alexandre Raphaël Duc, Serge Vaudenay
Springer Berlin Heidelberg, 2013
Book chapter

TCHo is a public-key cryptosystem based on the hardness of finding a multiple polynomial with low weight and on the hardness of distinguishing between the output of an LFSR with noise and some random source. An early version was proposed in 2006 by Finiasz and Vaudenay with non-polynomial (though practical) decryption time. The latest version came in 2007 with more co-authors. It reached competitive (heuristic) polynomial complexity and IND-CPA security. Since then, a key-recovery chosen ciphertext attack was published by Herrmann and Leander in 2009. In this paper we review the state of the art on this cryptosystem, together with some latest improvements regarding implementation and selection of parameters. We provide also more formal results regarding correctness and we update the key generation algorithm.

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

Alexandre Raphaël Duc, Serge Vaudenay
Springer Berlin Heidelberg, 2013
Book chapter

Abstract

Official source

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

About this result

Related concepts (16)

Related concepts

Related publications (9)

Related publications

Primeless Modular Cryptography (Extended Abstract)

Sonia Mihaela Bogos, Serge Vaudenay

Most of the known public-key cryptosystems have an overall complexity which is dominated by the key-production algorithm, which requires the generation of prime numbers. This is most inconvenient in settings where the key-generation is not an one-off process, e.g., secure delegation of computation or EKE password-based key exchange protocols. To this end, we extend the Goldwasser-Micali (GM) cryptosystem to a provably secure system, denoted SIS, where the generation of primes is bypassed. Using number-theoretic and linear optimisation techniques, we align the security guarantees (i.e., resistance to factoring of moduli, etc.) of SIS to those of other well-known cryptosystems based on modular arithmetics. %Taking into consideration different possibilities to implement the fundamental operations, We explicitly compare and contrast the asymptotic complexity of well-known public-key cryptosystems based on modular arithmetics (e.g., GM and/or RSA) with that of SIS's. The latter shows that once we are ready to accept an increase in the size of the moduli, SIS's offers significant speed-ups to applications like the aforementioned secure delegation of computation or protocols where a fresh key needs to be generated with every new session. We also developed an efficient extension of SIS to handle more than one bit at a time, using linear codes, which will be omitted herein due to space constraints.

2012

HELEN: A Public-Key Cryptosystem Based on the LPN and the Decisional Minimal Distance Problems

Alexandre Raphaël Duc, Serge Vaudenay

We propose HELEN, a code-based public-key cryptosystem whose security is based on the hardness of the Learning from Parity with Noise problem (LPN) and the decisional minimum distance problem. We show that the resulting cryptosystem achieves indistinguishability under chosen plaintext attacks (IND-CPA security). Using the Fujisaki-Okamoto generic construction, HELEN achieves IND-CCA security in the random oracle model. Our cryptosystem looks like the Alekhnovich cryptosystem. However, we carefully study its complexity and we further propose concrete optimized parameters.

Springer2013

HELEN: a Public-key Cryptosystem Based on the LPN Problem (Extended Abstract)

Alexandre Raphaël Duc, Serge Vaudenay

We propose HELEN, a new code-based public-key cryptosystem whose security is based on the hardness of the Learning from Parity with Noise problem~(LPN) and the decisional minimum distance problem. We show that the resulting cryptosystem achieves indistinguishability under chosen plaintext attacks (IND-CPA security). Using the Fujisaki-Okamoto generic construction, HELEN achieves IND-CCA security in the random oracle model. We further propose concrete parameters.

2012

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

RSA (cryptosystem)

RSA (Rivest–Shamir–Adleman) is a public-key cryptosystem, one of the oldest, that is widely used for secure data transmission. The acronym "RSA" comes from the surnames of Ron Rivest, Adi Shamir and

Chosen-plaintext attack

A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker can obtain the ciphertexts for arbitrary plaintexts. The goal of the attack is to gain informatio