PhD defence: Some Notes on Post-Quantum Cryptanalysis (Erik Mårtensson)
Thesis title: Some Notes on Post-Quantum Cryptanalysis
Author: Erik Mårtensson, Department of Electrical and Information Technology, Lund University
Opponent: Prof. Alexander May, Ruhr-Universität Bochum, Germany
When: 22 January 2021 at 9.15
Location: Online at the zoom platform - access by registration
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.
- 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.
- We developed a new binary approach for the distinguishing phase of the BKW algorithm and showed that it performs favorably compared to previous distinguishers.
- 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.
- 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.
Please register at https://www.lth.se/digitalth/events/register-2021-01-22-9-15 inorder to get an access link for the zoom platform.
22 januari 2021 09:15
Online at the zoom platform (Link by registration)
thomas [dot] johansson [at] eit [dot] lth [dot] se