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
In cryptography, post-quantum cryptography (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack ...
. 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
Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor.
On a quantum computer, to factor an integer N , Shor's algorithm runs in polynom ...
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
Assumption, in Christianity, refers to the Assumption of Mary, a belief in the taking up of the Virgin Mary into heaven.
Assumption may also refer to:
Places
* Assumption, Alberta, Canada
* Assumption, Illinois, United States
** Assumption Tow ...
that certain well-studied
computational lattice problems cannot be solved efficiently.
History
In 1996,
Miklós Ajtai
Miklós Ajtai (born 2 July 1946) is a computer scientist at the IBM Almaden Research Center, United States. In 2003, he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm (deve ...
introduced the first lattice-based cryptographic construction whose security could be based on the hardness of well-studied lattice problems,
and
Cynthia Dwork
Cynthia Dwork (born June 27, 1958) is an American computer scientist at Harvard University, where she is Gordon McKay Professor of Computer Science, Radcliffe Alumnae Professor at the Radcliffe Institute for Advanced Study, and Affiliated Professo ...
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
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
lattice problem. She then showed a
cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography:
* the probability of a particular n-bit output re ...
whose security is equivalent to the computational hardness of SIS.
In 1998,
Jeffrey Hoffstein
Jeffrey Ezra Hoffstein (born September 28, 1953 in New York City) is an American mathematician, specializing in number theory, automorphic forms, and cryptography.
Education and career
Hoffstein graduated with a bachelor's degree in 1974 from Cor ...
,
Jill Pipher
Jill Catherine Pipher (born December 14, 1955 in Harrisburg, Pennsylvania) was the president of the American Mathematical Society. She began a two-year term in 2019. She is also the past-president of the Association for Women in Mathematics (AWM, ...
, and
Joseph H. Silverman introduced a lattice-based
public-key encryption
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic al ...
scheme, known as
NTRU
NTRU is an open-source public-key cryptosystem that uses lattice-based cryptography to encrypt and decrypt data. It consists of two algorithms: NTRUEncrypt, which is used for encryption, and NTRUSign, which is used for digital signatures. Unli ...
. 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
Learning with errors (LWE) is the computational problem of inferring a linear n-ary function f over a finite ring from given samples y_i = f(\mathbf_i) some of which may be erroneous.
The LWE problem is conjectured to be hard to solve, and thus to ...
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
Craig Alan Gentry (born November 29, 1983) is an American former professional baseball outfielder. He played in Major League Baseball (MLB) for the Texas Rangers, Oakland Athletics, Los Angeles Angels and Baltimore Orioles.
Baseball career ...
introduced the first
fully homomorphic encryption
Homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, result in an identical ...
scheme, which was based on a lattice problem.
Mathematical background
In
linear algebra
Linear algebra is the branch of mathematics concerning linear equations such as:
:a_1x_1+\cdots +a_nx_n=b,
linear maps such as:
:(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,
and their representations in vector spaces and through matrices ...
, a
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
is the set of all integer linear combinations of vectors from a
basis
Basis may refer to:
Finance and accounting
* Adjusted basis, the net cost of an asset after adjusting for various tax-related items
*Basis point, 0.01%, often used in the context of interest rates
* Basis trading, a trading strategy consisting ...
of
. In other words,
For example,
is a lattice, generated by the
standard basis for
. Crucially, the basis for a lattice is not unique. For example, the vectors
,
, and
form an alternative basis for
.
The most important lattice-based computational problem is the
Shortest Vector Problem In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lat ...
(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
, 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
Homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, result in an identical ...
:
* 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 4th, 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 2nd, 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 2nd, 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 2nd, 2022.]
*
NewHope
In post-quantum cryptography, NewHope is a key-agreement protocol by Erdem Alkim, Léo Ducas, Thomas Pöppelmann, and Peter Schwabe that is designed to resist quantum computer attacks.
NewHope is based on a mathematical problem ring learning with ...
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 6th, 2022.]
* NTRU Prime.
[BERNSTEIN, Daniel J. et al., NTRU Prime: round 3. 2020. Available from the Internet on , accessed in November 8th, 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 2nd, 2021.
] which is built upon module learning with errors (module-LWE). Dilithium was selected for standardization by the NIST.
*
Falcon
Falcons () are birds of prey in the genus ''Falco'', which includes about 40 species. Falcons are widely distributed on all continents of the world except Antarctica, though closely related raptors did occur there in the Eocene.
Adult falcons ...
, 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 8th, 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
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
post-quantum cryptography
In cryptography, post-quantum cryptography (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack ...
. 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
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
'' 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
Homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, result in an identical ...
,
indistinguishability obfuscation
In cryptography, indistinguishability obfuscation (abbreviated IO or iO) is a type of software obfuscation with the defining property that obfuscating any two programs that compute the same mathematical function results in programs that cannot b ...
,
cryptographic multilinear maps, and
functional encryption.
See also
*
Lattice problems In computer science, lattice problems are a class of optimization problems related to mathematical objects called lattices. The conjectured intractability of such problems is central to the construction of secure lattice-based cryptosystems: Lat ...
*
Learning with errors
Learning with errors (LWE) is the computational problem of inferring a linear n-ary function f over a finite ring from given samples y_i = f(\mathbf_i) some of which may be erroneous.
The LWE problem is conjectured to be hard to solve, and thus to ...
*
Homomorphic encryption
Homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, result in an identical ...
*
Post-quantum cryptography
In cryptography, post-quantum cryptography (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack ...
*
Ring learning with errors
*
Ring learning with Errors Key Exchange
In cryptography, a public key exchange algorithm is a cryptographic algorithm which allows two parties to create and share a secret key, which they can use to encrypt messages between themselves. The ring learning with errors key exchange (RLWE- ...
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