Lattice-based cryptography

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. 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.

History

In 1996, Miklós Ajtai introduced the first lattice-based cryptographic construction whose security could be based on the hardness of well-studied lattice problems, and Cynthia Dwork showed that a certain average-case lattice problem, known as Short Integer Solutions (SIS), is at least as hard to solve as a worst-case lattice problem. 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. However, their scheme is not known to be at least as hard as solving a worst-case lattice problem.

The first lattice-based public-key encryption scheme whose security was proven under worst-case hardness assumptions was introduced by Oded Regev in 2005, together with the Learning with Errors problem (LWE). Since then, much follow-up work has focused on improving Regev's security proof and improving the efficiency of the original scheme. 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.

Mathematical background

In linear algebra, a lattice $L \subset \mathbb^n$ is the set of all integer linear combinations of vectors from a basis $\$ of $\mathbb^n$. In other words,
$L = \Big\\; .$
For example, $\mathbb^n$ is a lattice, generated by the standard basis for $\mathbb^n$. Crucially, the basis for a lattice is not unique. For example, the vectors $(3, 1, 4)$, $(1,5,9)$, and $(2, -1, 0)$ form an alternative basis for $\mathbb^3$.

The most important lattice-based computational problem is the Shortest Vector Problem (SVP or sometimes GapSVP), which asks us to approximate the minimal Euclidean length of a non-zero lattice vector. This problem is thought to be hard to solve efficiently, even with approximation factors that are polynomial in $n$, and even with a quantum computer. Many (though not all) lattice-based cryptographic constructions are known to be secure if SVP is in fact hard in this regime.

Selected lattice-based schemes

This section presents selected lattice-based schemes, grouped by primitive.

Encryption

Selected schemes for the purpose of encryption:

* GGH encryption scheme, which is based in the closest vector problem (CVP). In 1999, Nguyen published a critical flaw in the scheme's design.NGUYEN, Phon. Cryptanalysis of the Goldreich-Goldwasser-Halevi Cryptosystem from crypto ’97. In ''Crypto ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology'', pages 288–304, London, UK, 1999. Springer-Verlag.
* NTRUEncrypt.

Homomorphic encryption

Selected schemes for the purpose of homomorphic encryption:

* Gentry's original scheme.
* Brakerski and Vaikuntanathan.

Hash functions

Selected schemes for the purpose of hashing:

* SWIFFT.
* Lattice Based Hash Function (LASH).

Key exchange

Selected schemes for the purpose of key exchange, also called key establishment, key encapsulation and key encapsulation mechanism (KEM):

* CRYSTALS-Kyber,AVANZI, R. et al. CRYSTALS-KYBER Algorithm Specifications And Supporting Documentation. CRYSTALS Team, 2021. Available from the Internet on , accessed on November 4^th, 2022.
which is built upon module learning with errors (module-LWE). Kyber was selected for standardization by the NIST.
* FrodoKEM,FrodoKEM team. FrodoKEM. 2022. Available from the Internet on , accessed on November 2^nd, 2022.ALKIM, E. et al. FrodoKEM learning with errors key encapsulation algorithm specifications and supporting documentation. 2020. Available from the Internet on , accessed in November 1st, 2022 a scheme based on the learning with errors (LWE) problem. FrodoKEM joined the standardization call conducted by the National Institute of Standards and Technology (NIST),CSRC, National Institute of Standards and Technology. Post-Quantum Cryptography. 2019. Available from the Internet on , accessed in November 2^nd, 2022. and lived up to the 3^rd round of the process. It was then discarded due to low performance reasons. In October, 2022, the Twitter account associated to cryptologist Daniel J. Bernstein posted security issues in frodokem640.BERNSTEIN, Daniel J. FrodoKEM documentation claims that "the FrodoKEM parameter sets comfortably match their target security levels with a large margin". Warning: That's not true. Send 2^40 ciphertexts to a frodokem640 public key; one of them will be decrypted by a large-scale attack feasible today. 2022. Available from the Internet on , accessed in November 2^nd, 2022.
* NewHope is based on the ring learning with errors (RLWE) problem.SCHWABE, Peter et al. NewHope's Web site. 2022. Available from the Internet on , accessed in December 6^th, 2022.
* NTRU Prime.BERNSTEIN, Daniel J. et al., NTRU Prime: round 3. 2020. Available from the Internet on , accessed in November 8^th, 2022.
* Peikert's work, which is based on the ring learning with errors (RLWE) problem.
* Saber, which is based on the module learning with rounding (module-LWR) problem.

Signing

Selected schemes for the purpose of digital signatures:

* CRYSTALS-Dilithium,BAI, S. et al. CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation (Version 3.1). CRYSTALS Team, 2021. Available from Internet on , accessed in November 2^nd, 2021.
which is built upon module learning with errors (module-LWE). Dilithium was selected for standardization by the NIST.
* Falcon, selected for standardization by the NIST.FOUQUE, Pierre-Alain et al. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. 2020. Available from the Internet on , accessed in November 8^th, 2020.
* GGH signature scheme.
* Güneysu, Lyubashevsky, and Pöppelmann's work, which is based on ring learning with errors (RLWE).
* MITAKA, a variant of Falcon.ESPITAU, Thomas et al. MITAKA: A Simpler, Parallelizable, Maskable Variant of Falcon. 2021.
* NTRUSign.
* qTESLA, which is based on ring learning with errors (RLWE). The qTESLA scheme joined the standardization call conducted by the National Institute of Standards and Technology (NIST).ALKIM, E. et al. The Lattice-Based Digital Signature Scheme qTESLA. IACR, 2019. Cryptology ePrint Archive, Report 2019/085. Available from Internet on , accessed in NOVEMBER 1st, 2022.

Security

Lattice-based cryptographic constructions are the leading candidates for public-key post-quantum cryptography. 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 are known to be solvable in polynomial time on a quantum computer. Furthermore, algorithms for factorization tend to yield algorithms for discrete logarithm, and vice versa. 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. I.e., if there exists an algorithm that can efficiently break the cryptographic scheme with non-negligible probability, then there exists an efficient algorithm that solves a certain lattice problem on any input. In contrast, cryptographic schemes based on, e.g., factoring would be broken if factoring was easy "on an average input,'' even if factoring was in fact hard in the worst case. However, for the more efficient and practical lattice-based constructions (such as schemes based on NTRU and even schemes based on LWE with more aggressive parameters), such worst-case hardness results are not known. For some schemes, worst-case hardness results are known only for certain structured lattices or not at all.

Functionality

For many cryptographic primitives, the only known constructions are based on lattices or closely related objects. These primitives include fully homomorphic encryption, indistinguishability obfuscation, cryptographic multilinear maps, and functional encryption.

See also

* Lattice problems
* Learning with errors
* Homomorphic encryption
* Post-quantum cryptography
* Ring learning with errors
* Ring learning with Errors Key Exchange

References

Bibliography

* Oded Goldreich, Shafi Goldwasser, and Shai Halevi. "Public-key cryptosystems from lattice reduction problems". In ''Crypto ’97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology'', pages 112–131, London, UK, 1997. Springer-Verlag.
* Oded Regev. Lattice-based cryptography. In ''Advances in cryptology (CRYPTO)'', pages 131–141, 2006.

{{DEFAULTSORT:Lattice Based Cryptography
Cryptography

Post-quantum cryptography