Lattice-based cryptography is one of the most competitive candidates for protecting privacy, both in current applications and post quantum period. The central problem that serves as the hardness foundation of lattice-based cryptography is called the Learning with Errors (LWE). It asks to solve a noisy equation system, which is linear and over-determined modulo q. Normally, we call LWE problem as an average-case problem as all the coefficients in the equation system are randomly chosen modulo q. The LWE problem is conjectured to be hard even wtih a large scale quantum computer. It is at least as hard as standard problems defined in the lattices, such as Bounded Distance Decoding (BDD) and unique Shortest Vector Problem (uSVP). Finally, the best known algorithm for solving these problems is BKZ, which is very expensive.
In this thesis, we study the quantum hardness of LWE, the hardness relations between the underlying problems BDD and uSVP, and the practical performance of the BKZ algorithm. First, we give a strong evidence of quantum hardness of LWE. Concretely, we consider a relaxed version of the quantum version of dihedral coset problem and show an computational equivalence between LWE and this problem. Second, we tighten the hardness relation between BDD and uSVP. More precisely, We improve the reduction from BDD to uSVP by a factor √ 2 , compared to the one by Lyubashevsky and Micciancio. Third, we propose a more precise simulator for BKZ. In the last work, we propose the first probabilistic simulotor for BKZ, which can pridict the practical behavior of BKZ very precisely.
Chapter 1: Introduction.
The backgroud and motivation of this thesis, as well as a brief description of our main contributions are given in this chapter.
Chapter 2: Preliminaries.
Some necessary prerequisite definitions, concepts and results are given in this chapter.
Chapter 3: An improved reduction from BDD to uSVP.
In this chapter, we first give a brief discussion of the Lyubashevsky-Micciancio reduction from
BDD1/2γ
to
uSVPγ.
Then we give our improved reduction from
BDD1/√ 2 γ
to
uSVPγ.
We refer the reader to the link: https://eprint.iacr.org/2016/753, for a publication corresponding to this chapter.
Chapter 4: A Computational Equivalence between LWE and an Extrapolated Variant of DCP.
In this chapter, we first give a brief discussion on Regev's uSVP to DCP reduction.
Then we given our results on the computational equivalence between LWE and an extrapolated version of DCP.
We refer the reader to the link: https://arxiv.org/abs/1710.08223, for a publication corresponding to this chapter.
Chapter 5: A finer modelling of BKZ: understanding the head concavity.
In this chapter, we first report some experiments providing more insight on the shorter-than-expected phenomenon, which denote the phenomenon that the first few Gram-Schmidt norms in experiments are smaller than the ones in the Chen--Nguyen BKZ simulator.
Then, we present a refined BKZ simulator, and experimentally show that the new simulator can predict the behavior of BKZ more accurately.
Finally, we further propose a new BKZ variant by exploiting the shorter-than-expected phenomenon, which can be used to solve the SVP-120 instance of the Darmstadt lattice challenge faster.
Our BKZ experiments were run using the fplll (version 5.2.0) and fpylll (version 0.4.0dev) open-source libraries.
Our simulator, coded in Python, and the BKZ variants, coded in C++ are all freely available online: https://github.com/BKZsimulator under the GNU Lesser General Public License (either version 2.1 of the License or any later version).