Learning with Error
Zhiyong Zheng, Kun Tian, Fengxia Liu · Financial Mathematics and Fintech · 2022
Abstract Learning with error was proposed by O. Regev in 2005 (see Regev, 2009), which can be regarded as a dual form of SIS problem. LWE has very important applications in modern cryptography, such as LWE-based fully homomorphic encryption. The main purpose of this chapter is to explain the mathematical principles of the LWE problem in detail, especially the polynomial equivalence between the average LWE problem and the hard problems on lattice, which is one generalization of the Ajtai reduction principle and solves the computational complexity of the LWE problem effectively.