# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 4 Lattice-Based Cryptography
The NTRU is more efficient than other existing cryptosystems such as RSA and is thought to be immune to threats of a quantum computer, making it a prominent post-quantum cryptosystem. Although the NTRU is a 28-year-old cryptographic scheme, it remains a fundamental lattice-based cryptosystem and a current subject of research. NTRU has been updated several times since its conception to adapt to cryptanalytic developments. During the standardization process of the National Institute of Standards and Technology (NIST) for post-quantum cryptography, several concrete encryption-key encapsulation mechanism (KEM) and NTRU-based signature techniques were presented [37]. Concerning the KEM, two candidates, NTRUEncrypt and NTRU-HRSS-KEM, were fused to form a scheme known as \"NTRU\". The system is relatively simple to be performed in constant time and has a high performance rate, allowing it to be used in production. Moreover, Falcon, an NTRU-based signature scheme, also reached the final round of standardization, as it is distinguished by extremely quick execution and small key sizes [37]. Other characteristics that made it stand out are its compactness, scalability, flexibility, memory economy and, of course, security. The McEliece cryptographic scheme [38] was the ancestor of the cryptographic scheme introduced by [PERSON], [PERSON] and [PERSON] in 1997, the GGH cryptosystem [39]. Inspired by the McEliece cryptosystem, in which the private and public keys are representations of a linear code, GGH enables us to understand well the use of lattices in cryptography. The basic idea of constructing the cryptosystem is to have a \"good basis\" of a lattice, representing the private key, and a \"bad basis\" of the same lattice, representing the public key. In both cryptographic schemes, the plaintext is added with a noise vector, and the result of their addition is the ciphertext. The fundamental difference between these two cryptographic systems is that the domains in which the operations take place are distinct. A discrete implementation of GGH, NTRU and the cryptosystem presented below in this work, LWE, was introduced in [40]. According to its three creators, the increase in the key size of the GGH cryptosystem compensates for the decrease in computational time. A few years later, [PERSON] proposed a simple way to minimize both the key size and the ciphertext without reducing the level of security [41, 42]. Several attacks have been performed [43, 44, 45] that demonstrated the fragility and vulnerability of the GGH cryptosystem, so many researchers then considered GGH useless. Despite being regarded as one of the most prominent lattice-based cryptosystems and maintaining theoretical relevance, it is not recommended for practical application due to security flaws. GGH is inefficient in comparison to other stronger and more efficient lattice-based cryptosystems like NTRU and learning with errors (LWE) due to its weakness to these preformed attacks [40]. Besides encryption and decryption cryptographic schemes, one important cryptographic primitive used in electronic data transfer is digital signatures, which ensure the authenticity of the messages transmitted. The high-level concepts for lattice-based signatures are similar to the previous digital signature schemes, but the technical details are far more complicated. The main source of difficulty is the distinct algebraic structure of the hard one-way function that underpins lattice cryptography. Typically, mathematical operations are performed inside a lattice structure in a lattice-based digital signature protocol. Certain lattice problems, such as the learning with errors (LWE) problem, which will be analyzed below, and the short integer solution (SIS) problem, that are assumed to be hard, form the basis for the security of these schemes. The digital signature algorithms based on lattices offer certain benefits, including their ability to withstand quantum attacks and their potential for effective implementation.