Some Notes on Post-Quantum Cryptanalysis
Mårtensson, Erik LU
(2020)
- Abstract
- 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... (More) - 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/ab79fe93-2f19-4e6d-b813-4fac4b3b8499
- author
- Mårtensson, Erik
LU
- supervisor
- opponent
-
- Prof. May, Alexander, University of Ruhr, Germany.
- organization
- publishing date
- 2020
- type
- Thesis
- publication status
- published
- subject
- keywords
- Cryptography, Post-quantum cryptography, LWE, BKW, Cryptanalysis, Lattice sieving, SVP, Lattice-based cryptography, Code-based cryptography
- pages
- 290 pages
- publisher
- Department of Electroscience, Lund University
- defense location
- Lecture hall E:1406, building E, John Ericssons väg 2, Faculty of Engineering LTH, Lund University, Lund.
- defense date
- 2021-01-22 09:15:00
- ISBN
- 978-91-7895-712-5
- 978-91-7895-711-8
- language
- English
- LU publication?
- yes
- id
- ab79fe93-2f19-4e6d-b813-4fac4b3b8499
- date added to LUP
- 2020-12-17 15:11:39
- date last changed
- 2024-02-22 04:06:49
@phdthesis{ab79fe93-2f19-4e6d-b813-4fac4b3b8499,
abstract = {{Cryptography as it is used today relies on a foundational level on the assumption<br/>that either the Integer Factoring Problem (IFP) or the Discrete<br/>Logarithm Problem (DLP) is computationally intractable. In the 1990s Peter<br/>Shor developed a quantum algorithm that solves both problems in polynomial<br/>time. Since then alternative foundational mathematical problems to replace IFP<br/>and DLP have been suggested. This area of research is called post-quantum<br/>cryptology.<br/><br/>To remedy the threat of quantum computers the National Institute of Standards<br/>and Technology (NIST) has organized a competition to develop schemes<br/>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.<br/><br/>The lattice-based candidates are based on the difficulty of either the Learning<br/>With Errors problem (LWE) or the Nth Degree Truncated Polynomial problem<br/>(NTRU), of which LWE is the focus of this thesis. The difficulty of both these<br/>problems in turn relies on the difficulty of variations of the Shortest Vector<br/>Problem (SVP). Code-based cryptography is based on the difficulty of decoding<br/>random linear codes.<br/><br/>The main focus of this thesis is on solving the LWE problem using the Blum-<br/>Kalai-Wasserman algorithm (BKW).We have the following improvements of the<br/>algorithm.<br/><br/>1. We combined BKW with state-of-the-art lattice sieving methods to improve<br/>the complexity of the algorithm. We also elaborate on the similarities<br/>and differences between BKW and lattice sieving, two approaches<br/>that on a shallow level look very different.<br/>2. We developed a new binary approach for the distinguishing phase of the<br/>BKW algorithm and showed that it performs favorably compared to previous<br/>distinguishers.<br/>3. We investigated the Fast Fourier Transform (FFT) approach for the distinguishing<br/>part of BKW showing that it performs better than theory<br/>predicts and identically with the optimal distinguisher. We showed that<br/>we could improve its performance by limiting the number of hypotheses<br/>being tested.<br/>4. We introduced practical improvements of the algorithm such as nonintegral<br/>step sizes, a file-based sample storage solution and an implementation<br/>of the algorithm.<br/><br/>We also improved the classical state-of-the-art approaches for k-sieving -<br/>lattice sieving where k vectors are combined at a time - by using quantum<br/>algorithms. At the cost of a small increase in time complexity we managed<br/>to drastically decrease the space requirement compared to the state-of-the-art<br/>quantum algorithm for solving the SVP.<br/><br/>Finally, we developed an algorithm for decoding linear codes where the noise<br/>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.}},
author = {{Mårtensson, Erik}},
isbn = {{978-91-7895-712-5}},
keywords = {{Cryptography; Post-quantum cryptography; LWE; BKW; Cryptanalysis; Lattice sieving; SVP; Lattice-based cryptography; Code-based cryptography}},
language = {{eng}},
publisher = {{Department of Electroscience, Lund University}},
school = {{Lund University}},
title = {{Some Notes on Post-Quantum Cryptanalysis}},
url = {{https://lup.lub.lu.se/search/files/88158602/thesis_main_document.pdf}},
year = {{2020}},
}