Analysis strategies and solving algorithms of the LWE problem: A survey

WANG Leizhang,ZHANG Shuailing,WANG Bao cang

PDF(1233 KB)
PDF(1233 KB)
Journal of Guangzhou University(Natural Science Edition) ›› 2021, Vol. 20 ›› Issue (4) : 29-45.

Analysis strategies and solving algorithms of the LWE problem: A survey

  • WANG Leizhang, ZHANG Shuailing, WANG Bao cang
Author information +
History +

Abstract

Lattice public key cryptography is widely conceived as the most promising candidate in the quantum computing era due to the averagecase / hardcase equivalence of the underlying mathematic cally intractable problems, the linearity of the involved algebraic structures, and the tremendous cryp tographic functionalities. At present, numerous post quantum lattice cryptographic algorithms were deeloped to rely their securities on a lattice problem: the learning with errors ( LWE) problem. There fore, it is of vital significance to study the algorithms for solving the LWE problems to give insights in to the security of lattice public key cryptography. This paper firstly reviews and compares different solution strategies for distinct types of LWE problems. Secondly, we outline the basic ideas and technical principles of the existing lattice reduction algorithms. Finally, some prospections are made on the research focuses and trends in solving the LWE problems with lattice based reduction algorithms.

Key words

lattice cryptography / learning with error / lattice basis reduce algorithm

Cite this article

Download Citations
WANG Leizhang,ZHANG Shuailing,WANG Bao cang. Analysis strategies and solving algorithms of the LWE problem: A survey. Journal of Guangzhou University(Natural Science Edition). 2021, 20(4): 29-45

References

LenstraAK,LenstraHW,LovászL.Factoringpolynomialswithrationalcoefficients[J].MathematischeAnnalen,1982, 261(6):515534.
PDF(1233 KB)

310

Accesses

0

Citation

Detail

Sections
Recommended

/