1 Discrete mathematics, Department of Mathematics, Technical University of Denmark2 Department of Mathematics, Technical University of Denmark3 Department of Applied Mathematics and Computer Science, Technical University of Denmark
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).