Some Notes on Post-Quantum Cryptanalysis

Cryptography as it is used today relies on a foundational level on the assumption
that either the Integer Factoring Problem (IFP) or the Discrete
Logarithm Problem (DLP) is computationally intractable. In the 1990s Peter
Shor developed a quantum algorithm that solves both problems in polynomial
time. Since then alternative foundational mathematical problems to replace IFP
and DLP have been suggested. This area of research is called post-quantum
cryptology.

To remedy the threat of quantum computers the National Institute of Standards
and Technology (NIST) has organized a competition to develop schemes
for post-quantum encryption and digital signatures. For both categories latticebased cryptography candidates dominate. The second most promising type of candidate for encryption is code-based cryptography.

The lattice-based candidates are based on the difficulty of either the Learning
With Errors problem (LWE) or the Nth Degree Truncated Polynomial problem
(NTRU), of which LWE is the focus of this thesis. The difficulty of both these
problems in turn relies on the difficulty of variations of the Shortest Vector
Problem (SVP). Code-based cryptography is based on the difficulty of decoding
random linear codes.

The main focus of this thesis is on solving the LWE problem using the Blum-
Kalai-Wasserman algorithm (BKW).We have the following improvements of the
algorithm.

1. We combined BKW with state-of-the-art lattice sieving methods to improve
the complexity of the algorithm. We also elaborate on the similarities
and differences between BKW and lattice sieving, two approaches
that on a shallow level look very different.
2. We developed a new binary approach for the distinguishing phase of the
BKW algorithm and showed that it performs favorably compared to previous
distinguishers.
3. We investigated the Fast Fourier Transform (FFT) approach for the distinguishing
part of BKW showing that it performs better than theory
predicts and identically with the optimal distinguisher. We showed that
we could improve its performance by limiting the number of hypotheses
being tested.
4. We introduced practical improvements of the algorithm such as nonintegral
step sizes, a file-based sample storage solution and an implementation
of the algorithm.

We also improved the classical state-of-the-art approaches for k-sieving -
lattice sieving where k vectors are combined at a time - by using quantum
algorithms. At the cost of a small increase in time complexity we managed
to drastically decrease the space requirement compared to the state-of-the-art
quantum algorithm for solving the SVP.

Finally, we developed an algorithm for decoding linear codes where the noise
is Gaussian instead of binary. We showed how code-based schemes with Gaussian noise are easily broken. We also found other applications for the algorithm in side-channel attacks and in coding theory.