Projects per year
Abstract
The security of almost all the publickey 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 polynomialtime algorithm which
solves these two problems using quantum computers. The public key cryptosystems
that can resist these emerging attacks are called quantum resistant or postquantum
cryptosystems. There are mainly four classes of publickey cryptography that are
believed to resist classical and quantum attacks: codebased cryptography, hashbased
cryptography, latticebased cryptography and multivariate publickey cryptography.
In this thesis, we focus on the rst two classes. In the rst part, we introduce coding
theory and give an overview of codebased cryptography. The main contribution is
an attack on two promising variants of McEliece's cryptosystem, based on quasicyclic
alternant codes and quasidyadic codes (joint work with Gregor Leander). We also
present a deterministic polynomialtime algorithm to solve the Goppa Code Distinguisher
problem for high rate codes (joint work with JeanCharles Faugere, Ayoub
Otmani, Ludovic Perret and JeanPierre 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 multipletime signature schemes are not any better than
using existing onetime signature schemes a multiple number of times. We propose
a new variant of the classical onetime signature schemes based on (near)collisions
resulting in twotime signature schemes. We also give a new, simple and ecient
algorithm for traversing a tree in treebased signature schemes (joint work with Lars
R. Knudsen and Sren S. Thomsen).
Original language  English 

Place of Publication  Kgs. Lyngby, Denmark 

Publisher  Technical University of Denmark 
Number of pages  156 
Publication status  Published  2011 
Fingerprint Dive into the research topics of 'PostQuantum Cryptography'. Together they form a unique fingerprint.
Projects
 1 Finished

Post quantum cryptology
Gauthier Umana, V., Knudsen, L. R., Leander, G., Beelen, P., Canteaut, A. M. & Johansson, T.
Technical University of Denmark
01/11/2008 → 21/12/2011
Project: PhD