Post-Quantum Cryptography

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