Post-Quantum Cryptography
Publication: Research › Ph.D. thesis – Annual report year: 2011
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).
Original language | English |
---|
Place of Publication | Kgs. Lyngby, Denmark |
---|---|
Publisher | Technical University of Denmark (DTU) |
Number of pages | 156 |
State | Published - 2011 |
Download as:
Download statistics
No data available
ID: 6426367