Some Notes on Post-Quantum Cryptanalysis

Forskningsoutput: AvhandlingDoktorsavhandling (sammanläggning)

679 Nedladdningar (Pure)


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

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

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
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.
Tilldelande institution
  • Institutionen för elektro- och informationsteknik
  • Johansson, Thomas, handledare
  • Stankovski Wagner, Paul, Biträdande handledare
  • Guo, Qian, Biträdande handledare
Tilldelningsdatum2021 jan. 22
ISBN (tryckt)978-91-7895-711-8
ISBN (elektroniskt)978-91-7895-712-5
StatusPublished - 2020

Bibliografisk information

Defence details
Date: 2021-01-22
Time: 09:15
Place: Lecture hall E:1406, building E, John Ericssons väg 2, Faculty of Engineering LTH, Lund University, Lund.
External reviewer(s)
Name: May, Alexander
Title: Prof.
Affiliation: University of Ruhr, Germany.

Ämnesklassifikation (UKÄ)

  • Annan elektroteknik och elektronik


Utforska forskningsämnen för ”Some Notes on Post-Quantum Cryptanalysis”. Tillsammans bildar de ett unikt fingeravtryck.

Citera det här