## Post-Quantum Cryptography

Publication: Research › Ph.D. thesis – Annual report year: 2011

### Standard

**Post-Quantum Cryptography.** / Gauthier Umana, Valérie; Knudsen, Lars Ramkilde (Supervisor); Leander, Gregor (Supervisor).

Publication: Research › Ph.D. thesis – Annual report year: 2011

### Harvard

*Post-Quantum Cryptography*. Ph.D. thesis, Technical University of Denmark (DTU), Kgs. Lyngby, Denmark.

### APA

*Post-Quantum Cryptography*. Kgs. Lyngby, Denmark: Technical University of Denmark (DTU).

### CBE

### MLA

*Post-Quantum Cryptography*Kgs. Lyngby, Denmark: Technical University of Denmark (DTU). 2011.

### Vancouver

### Author

### Bibtex

}

### RIS

TY - BOOK

T1 - Post-Quantum Cryptography

AU - Gauthier Umana,Valérie

A2 - Knudsen,Lars Ramkilde

A2 - Leander,Gregor

PY - 2011

Y1 - 2011

N2 - The security of almost all the public-key cryptosystems used in practice depends on the fact that the prime factorization of a number and the discrete logarithm are hard problems to solve. In 1994, Peter Shor found a polynomial-time algorithm which solves these two problems using quantum computers. The public key cryptosystems that can resist these emerging attacks are called quantum resistant or post-quantum cryptosystems. There are mainly four classes of public-key cryptography that are believed to resist classical and quantum attacks: code-based cryptography, hash-based cryptography, lattice-based cryptography and multivariate public-key cryptography. In this thesis, we focus on the rst two classes. In the rst part, we introduce coding theory and give an overview of code-based cryptography. The main contribution is an attack on two promising variants of McEliece's cryptosystem, based on quasi-cyclic alternant codes and quasi-dyadic codes (joint work with Gregor Leander). We also present a deterministic polynomial-time algorithm to solve the Goppa Code Distinguisher problem for high rate codes (joint work with Jean-Charles Faugere, Ayoub Otmani, Ludovic Perret and Jean-Pierre Tillich). In the second part, we rst give an overview of hash based signature schemes. Their security is based on the collision resistance of a hash function and is a good quantum resistant alternative to the used signature schemes. We show that several existing proposals of how to make multiple-time signature schemes are not any better than using existing one-time signature schemes a multiple number of times. We propose a new variant of the classical one-time signature schemes based on (near-)collisions resulting in two-time signature schemes. We also give a new, simple and ecient algorithm for traversing a tree in tree-based signature schemes (joint work with Lars R. Knudsen and Sren S. Thomsen).

AB - The security of almost all the public-key cryptosystems used in practice depends on the fact that the prime factorization of a number and the discrete logarithm are hard problems to solve. In 1994, Peter Shor found a polynomial-time algorithm which solves these two problems using quantum computers. The public key cryptosystems that can resist these emerging attacks are called quantum resistant or post-quantum cryptosystems. There are mainly four classes of public-key cryptography that are believed to resist classical and quantum attacks: code-based cryptography, hash-based cryptography, lattice-based cryptography and multivariate public-key cryptography. In this thesis, we focus on the rst two classes. In the rst part, we introduce coding theory and give an overview of code-based cryptography. The main contribution is an attack on two promising variants of McEliece's cryptosystem, based on quasi-cyclic alternant codes and quasi-dyadic codes (joint work with Gregor Leander). We also present a deterministic polynomial-time algorithm to solve the Goppa Code Distinguisher problem for high rate codes (joint work with Jean-Charles Faugere, Ayoub Otmani, Ludovic Perret and Jean-Pierre Tillich). In the second part, we rst give an overview of hash based signature schemes. Their security is based on the collision resistance of a hash function and is a good quantum resistant alternative to the used signature schemes. We show that several existing proposals of how to make multiple-time signature schemes are not any better than using existing one-time signature schemes a multiple number of times. We propose a new variant of the classical one-time signature schemes based on (near-)collisions resulting in two-time signature schemes. We also give a new, simple and ecient algorithm for traversing a tree in tree-based signature schemes (joint work with Lars R. Knudsen and Sren S. Thomsen).

M3 - Ph.D. thesis

BT - Post-Quantum Cryptography

PB - Technical University of Denmark (DTU)

ER -