[1] Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems — which could, theoretically, be defeated using Shor's algorithm on a quantum computer — some lattice-based constructions appear to be resistant to attack by both classical and quantum computers.
Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.
In 2024 NIST announced the Module-Lattice-Based Digital Signature Standard for post-quantum cryptography.
[4] She then showed a cryptographic hash function whose security is equivalent to the computational hardness of SIS.
In 1998, Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman introduced a lattice-based public-key encryption scheme, known as NTRU.
The first lattice-based public-key encryption scheme whose security was proven under worst-case hardness assumptions was introduced by Oded Regev in 2005,[6] together with the learning with errors problem (LWE).
[9][10][11][12] Much more work has been devoted to constructing additional cryptographic primitives based on LWE and related problems.
For example, in 2009, Craig Gentry introduced the first fully homomorphic encryption scheme, which was based on a lattice problem.
This problem is thought to be hard to solve efficiently, even with approximation factors that are polynomial in
Many (though not all) lattice-based cryptographic constructions are known to be secure if SVP is in fact hard in this regime.
[33] Dilithium was one of the two digital signature schemes initially chosen by the NIST in their post-quantum cryptography process, the other one being SPHINCS⁺, which is not based on lattices but on hashes.
In August 2023, NIST published FIPS 204 (Initial Public Draft), and started calling Dilithium "Module-Lattice-Based Digital Signature Algorithm" (ML-DSA).
[37] Lattice-based cryptographic constructions hold a great promise for public-key post-quantum cryptography.
[38] Indeed, the main alternative forms of public-key cryptography are schemes based on the hardness of factoring and related problems and schemes based on the hardness of the discrete logarithm and related problems.
However, both factoring and the discrete logarithm problem are known to be solvable in polynomial time on a quantum computer.
This further motivates the study of constructions based on alternative assumptions, such as the hardness of lattice problems.
Many lattice-based cryptographic schemes are known to be secure assuming the worst-case hardness of certain lattice problems.
Assessments of the security levels provided by reduction arguments from hard problems - based on recommended parameter sizes, standard estimates of the computational complexity of the hard problems, and detailed examination of the steps in the reductions - are called concrete security and sometimes practice-oriented provable security.
[41][42] For many cryptographic primitives, the only known constructions are based on lattices or closely related objects.