View source for Lattice-based cryptography

{{short description|Constructions of cryptographic primitives that involve lattices}}
'''Lattice-based cryptography''' is the generic term for constructions of [[cryptographic primitive]]s that involve [[Lattice (group)|lattices]], either in the construction itself or in the security proof. Lattice-based constructions support important standards of [[post-quantum cryptography]].<ref name="csrc201900" />  Unlike more widely used and known public-key schemes such as the [[RSA (cryptosystem)|RSA]], [[Diffie-Hellman]] or [[Elliptic-curve cryptography|elliptic-curve]] cryptosystems — which could, theoretically, be defeated using [[Shor's algorithm]] on a [[Quantum computing|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 [[Computational hardness assumption|assumption]] that certain well-studied computational [[lattice problem]]s cannot be solved efficiently.

In 2024 [[NIST]] announced the Module-Lattice-Based Digital Signature Standard for post-quantum cryptography.<ref>{{Cite web |date=August 2024 |title=Module-Lattice-Based Digital Signature Standard |url=https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf |website=[[NIST.gov]]}}</ref>

==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,<ref name=":1">{{Cite book |last=Ajtai |first=Miklós |title=Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing |year=1996 |isbn=978-0-89791-785-8 |pages=99–108 |chapter=Generating Hard Instances of Lattice Problems |citeseerx=10.1.1.40.2489 |doi=10.1145/237814.237838 |s2cid=6864824}}</ref> and [[Cynthia Dwork]] showed that a certain average-case lattice problem, known as [[Short integer solution problem|short integer solutions]] (SIS), is at least as hard to solve as a [[Worst-case complexity|worst-case]] lattice problem.<ref>[https://eccc.weizmann.ac.il/report/1996/065/  Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence].</ref> 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 cryptography|public-key encryption]] scheme, known as [[NTRUEncrypt|NTRU]].<ref>{{Cite book |last=Hoffstein |first=Jeffrey |title=Algorithmic Number Theory |last2=Pipher |first2=Jill |last3=Silverman |first3=Joseph H. |year=1998 |isbn=978-3-540-64657-0 |series=Lecture Notes in Computer Science |volume=1423 |pages=267–288 |chapter=NTRU: A ring-based public key cryptosystem |citeseerx=10.1.1.25.8422 |doi=10.1007/bfb0054868}}</ref> 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 (computer scientist)|Oded Regev]] in 2005,<ref name=":2">{{Cite book |last=Regev |first=Oded |title=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC '05 |date=2005-01-01 |publisher=ACM |isbn=978-1581139600 |pages=84–93 |chapter=On lattices, learning with errors, random linear codes, and cryptography |citeseerx=10.1.1.110.4776 |doi=10.1145/1060590.1060603 |s2cid=53223958}}</ref> together with the [[learning with errors]] problem (LWE). Since then, much follow-up work has focused on improving Regev's security proof<ref name=":3">{{Cite book |last=Peikert |first=Chris |title=Proceedings of the 41st annual ACM symposium on Symposium on theory of computing – STOC '09 |date=2009-01-01 |publisher=ACM |isbn=9781605585062 |pages=333–342 |chapter=Public-key cryptosystems from the worst-case shortest vector problem |citeseerx=10.1.1.168.270 |doi=10.1145/1536414.1536461 |s2cid=1864880}}</ref><ref>{{Cite book |last=Brakerski |first=Zvika |title=Proceedings of the 45th annual ACM symposium on Symposium on theory of computing – STOC '13 |last2=Langlois |first2=Adeline |last3=Peikert |first3=Chris |last4=Regev |first4=Oded |last5=Stehlé |first5=Damien |date=2013-01-01 |publisher=ACM |isbn=9781450320290 |pages=575–584 |chapter=Classical hardness of learning with errors |doi=10.1145/2488608.2488680 |arxiv=1306.0281 |s2cid=6005009}}</ref> and improving the efficiency of the original scheme.<ref name=":4">{{Cite book |last=Lyubashevsky |first=Vadim |title=Advances in Cryptology – EUROCRYPT 2010 |last2=Peikert |first2=Chris |last3=Regev |first3=Oded |date=2010-05-30 |isbn=978-3-642-13189-9 |series=Lecture Notes in Computer Science |volume=6110 |pages=1–23 |language=en |chapter=On Ideal Lattices and Learning with Errors over Rings |citeseerx=10.1.1.352.8218 |doi=10.1007/978-3-642-13190-5_1}}</ref><ref name=":0" /><ref>{{Cite journal |last=Alkim |first=Erdem |last2=Ducas |first2=Léo |last3=Pöppelmann |first3=Thomas |last4=Schwabe |first4=Peter |date=2015-01-01 |title=Post-quantum key exchange – a new hope |url=http://eprint.iacr.org/2015/1092 |journal=Cryptology ePrint Archive}}</ref><ref>{{Cite journal |last=Bos |first=Joppe |last2=Costello |first2=Craig |last3=Ducas |first3=Léo |last4=Mironov |first4=Ilya |last5=Naehrig |first5=Michael |last6=Nikolaenko |first6=Valeria |last7=Raghunathan |first7=Ananth |last8=Stebila |first8=Douglas |date=2016-01-01 |title=Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE |url=http://eprint.iacr.org/2016/659 |journal=Cryptology ePrint Archive}}</ref> Much more work has been devoted to constructing additional cryptographic primitives based on LWE and related problems. For example, in 2009, [[Craig Gentry (computer scientist)|Craig Gentry]] introduced the first [[Homomorphic encryption|fully homomorphic encryption]] scheme, which was based on a lattice problem.<ref name=":5">{{Cite thesis |last=Gentry |first=Craig |title=A Fully Homomorphic Encryption Scheme |date=2009-01-01 |publisher=Stanford University |url=http://dl.acm.org/citation.cfm?id=1834954 |place=Stanford, CA, USA}}</ref>

== Mathematical background ==
In [[linear algebra]], a [[lattice (group)|lattice]] <math>L \subset \mathbb{R}^n</math> is the set of all integer linear combinations of vectors from a [[basis (algebra)|basis]] <math>\{\mathbf{b}_1, \ldots, \mathbf{b}_n\}</math> of <math>\mathbb{R}^n</math>. In other words, 
<math>L = \Big\{ \sum a_i \mathbf{b}_i : a_i \in \mathbb{Z} \Big\}.</math>
For example, <math>\mathbb{Z}^n</math> is a lattice, generated by the [[standard basis]] for <math>\mathbb{R}^n</math>. Crucially, the basis for a lattice is not unique. For example, the vectors <math>(3, 1, 4)</math>, <math>(1, 5, 9)</math>, and <math>(2, -1, 0)</math> form an alternative basis for <math>\mathbb{Z}^3</math>.

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 <math>n</math>, 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.<ref name="nguyen199900">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.</ref>
* [[NTRUEncrypt]].

===Homomorphic encryption===
Selected schemes for the purpose of [[homomorphic encryption]]:

* Gentry's original scheme.<ref name=":5" />
* Brakerski and Vaikuntanathan.<ref>{{Cite journal |last=Brakerski |first=Zvika |last2=Vaikuntanathan |first2=Vinod |date=2011 |title=Efficient Fully Homomorphic Encryption from (Standard) LWE |url=https://eprint.iacr.org/2011/344 |journal=Cryptology ePrint Archive}}</ref><ref>{{Cite journal |last=Brakerski |first=Zvika |last2=Vaikuntanathan |first2=Vinod |date=2013 |title=Lattice-Based FHE as Secure as PKE |url=https://eprint.iacr.org/2013/541 |journal=Cryptology ePrint Archive}}</ref>

===Hash functions===
Selected lattice-based cryptographic schemes for the purpose of hashing:

* [[SWIFFT]].
* Lattice Based Hash Function (LASH).<ref>{{Cite web |title=LASH: A Lattice Based Hash Function |url=http://www.cs.bris.ac.uk/~page/research/lash.html |url-status=dead |archive-url=https://web.archive.org/web/20081016235719/http://www.cs.bris.ac.uk/~page/research/lash.html |archive-date=October 16, 2008 |access-date=2008-07-31}}</ref><ref>{{Cite book |last=Contini |first=Scott |title=Fast Software Encryption |last2=Matusiewicz |first2=Krystian |last3=Pieprzyk |first3=Josef |last4=Steinfeld |first4=Ron |last5=Guo |first5=Jian |last6=Ling |first6=San |last7=Wang |first7=Huaxiong |year=2008 |isbn=978-3-540-71038-7 |series=Lecture Notes in Computer Science |volume=5086 |pages=207–223 |chapter=Cryptanalysis of LASH |doi=10.1007/978-3-540-71039-4_13 |chapter-url=https://eprint.iacr.org/2007/430.pdf |s2cid=6207514}}</ref>

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

* [[Kyber|CRYSTALS-Kyber]],<ref name="avanzietal202100">AVANZI, R. et al. CRYSTALS-KYBER Algorithm Specifications And Supporting Documentation. CRYSTALS Team, 2021. Available from the Internet on <https:
//www.pq-crystals.org/>, accessed on November 4th, 2022.
</ref> which is built upon module learning with errors (module-LWE). Kyber was selected for standardization by the NIST in 2023.<ref name="csrc201900" /> In August 2023, NIST published FIPS 203 (Initial Public Draft), and started referring to their Kyber version as Module-Lattice-based Key Encapsulation Mechanism (ML-KEM).<ref name="raimondoandlocascio202301">Raimondo, Gina M., and Locascio, Laurie E., FIPS 203 (Draft) Federal Information Processing Standards Publication – Module-Lattice-based Key-Encapsulation Mechanism Standard. August 24, 2023. Information Technology Laboratory, National Institute of Standards and Technology. Gaithersburg, MD, United States of America. DOI 10.6028/NIST.FIPS.203.ipd. Available from the Internet on <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf>, accessed in October 30th, 2023.</ref>
* FrodoKEM,<ref name="frodokemteam202200">FrodoKEM team. FrodoKEM. 2022. Available from the Internet on <https://frodokem.org/>, accessed on November 2nd, 2022.</ref><ref name="alkimetal202000">ALKIM, E. et al. FrodoKEM learning with errors key encapsulation algorithm specifications and supporting documentation. 2020. Available from the Internet on <https://frodokem.org/files/FrodoKEM-specification-20200930.pdf>, accessed in November 1st, 2022</ref> a scheme based on the learning with errors (LWE) problem. FrodoKEM joined the standardization call conducted by the [[National Institute of Standards and Technology|National Institute of Standards and Technology (NIST)]],<ref name="csrc201900">CSRC, National Institute of Standards and Technology. Post-Quantum Cryptography. 2019. Available from the Internet on <https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/>, accessed in November 2nd, 2022.</ref> and lived up to the 3rd 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.<ref name="bernstein202200">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 <https://twitter.com/hashbreaker/status/1587184970258255872>, accessed in November 2nd, 2022.</ref>
* [[NewHope]] is based on the ring learning with errors (RLWE) problem.<ref name="schwabeetal202200">SCHWABE, Peter et al. NewHope's Web site. 2022. Available from the Internet on <https://newhopecrypto.org/>, accessed in December 6th, 2022.</ref>
* NTRU Prime.<ref name="bernsteinetal202000">Bernstein, Daniel J. et al., NTRU Prime: round 3. 2020. Available from the Internet on <https://ntruprime.cr.yp.to/>, accessed in November 8th, 2022.</ref>
* [[Ring learning with errors key exchange|Peikert's work]], which is based on the ring learning with errors (RLWE) problem.<ref name=":0">{{Cite web |last=Peikert |first=Chris |date=2014-07-16 |title=Lattice cryptography for the Internet |url=https://eprint.iacr.org/2014/070.pdf |access-date=2017-01-11 |publisher=[[International Association for Cryptologic Research|IACR]]}}</ref>
* Saber,<ref>D'ANVERS, Jan-Pieter, KARMAKAR, Angshuman, ROY, Sujoy Sinha, and VERCAUTEREN, Frederik. Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM. 2018. Available from Internet on <https://eprint.iacr.org/2018/230>, accessed in November 5th, 2022.</ref> which is based on the module learning with rounding (module-LWR) problem.

=== Signing ===
This section lists a selection of lattice-based schemes for the purpose of digital signatures.

* CRYSTALS-Dilithium,<ref name="baietal202100">BAI, S. et al. CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation (Version 3.1). CRYSTALS Team, 2021. Available from the Internet on <https://www.pq-crystals.org/>, accessed in November 2nd, 2021.
</ref><ref name="seileretal202200">SEILER, Gregor et al. pq-crystals/dilithium (Dilithium at GitHub), 2022. Available from the Internet on <https://github.com/pq-crystals/dilithium>, accessed in December 29th, 2022.</ref> which is built upon module learning with errors (module-LWE) and module short integer solution (module-SIS). Dilithium was selected for standardization by the NIST.<ref name="csrc201900" /> According to a message from Ray Perlner, writing on behalf of the NIST PQC team, the NIST module-LWE signing standard is to be based on version 3.1 of the Dilithium specification.

* [[Falcon (signature scheme)|Falcon]], which is built upon short integer solution (SIS) over NTRU. Falcon was selected for standardization by the NIST.<ref name="fouqueetal202000">FOUQUE, Pierre-Alain et al. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. 2020. Available from the Internet on <https://falcon-sign.info/>, accessed in November 8th, 2020.</ref><ref name="csrc201900" />
* [[GGH signature scheme]].
* Güneysu, Lyubashevsky, and Pöppelmann's work, which is based on ring learning with errors (RLWE).<ref>{{Cite book |last=Güneysu |first=Tim |title=Cryptographic Hardware and Embedded Systems – CHES 2012 |last2=Lyubashevsky |first2=Vadim |last3=Pöppelmann |first3=Thomas |publisher=IACR |year=2012 |isbn=978-3-642-33026-1 |series=Lecture Notes in Computer Science |volume=7428 |pages=530–547 |chapter=Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems |doi=10.1007/978-3-642-33027-8_31 |chapter-url=https://www.iacr.org/archive/ches2012/74280529/74280529.pdf |accessdate=2017-01-11}}</ref>

* MITAKA, a variant of Falcon.<ref name="espitauetal202100">ESPITAU, Thomas et al. MITAKA: A Simpler, Parallelizable, Maskable Variant of Falcon. 2021.</ref>
* [[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|National Institute of Standards and Technology (NIST)]].<ref name="alkim201900">ALKIM, E. et al. The Lattice-Based Digital Signature Scheme qTESLA. IACR, 2019. Cryptology ePrint Archive, Report 2019/085. Available from Internet on <https://eprint.iacr.org/2019/085>, accessed in NOVEMBER 1st, 2022.</ref><ref name="csrc201900" />

==== CRYSTALS-Dilithium ====
CRYSTALS-Dilithium or simply Dilithium <ref name="baietal202100" /><ref name="seileretal202200" /> is built upon module-LWE and module-SIS. Dilithium was selected by the NIST as the basis for a digital signature standard.<ref name="csrc201900" /> According to a message from Ray Perlner, writing on behalf of the NIST PQC team, the NIST module-LWE signing standard is to be based on version 3.1 of the Dilithium specification. NIST's changes on Dilithium 3.1 intend to support additional randomness in signing (hedged signing) and other improvements.<ref name ="perlner202300">Perlner, Ray A.. Planned changes to the Dilithium spec. April 20th, 2023. Google Groups. Available from the Internet on <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/3pBJsYjfRw4/m/GjJ2icQkAQAJ>, accessed in June 14th, 2023.</ref>

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).<ref name="raimondoandlocascio202300">Raimondo, Gina M., and Locascio, Laurie E., FIPS 204 (Draft) Federal Information Processing Standards Publication – Module-Lattice-Based Digital Signature Standard. August 24, 2023. Information Technology Laboratory, National Institute of Standards and Technology. Gaithersburg, MD, United States of America. DOI 10.6028/NIST.FIPS.204.ipd. Available from the Internet on <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf>, accessed in September 2nd, 2023.</ref>

As of October 2023, ML-DSA was being implemented as a part of [[Libgcrypt]], according to Falco Strenzke.<ref name="gcrypt-devel202300">Gcrypt-devel mailing list. Dilithium Implementation in Libgcrypt. October 24th, 2023. Available from the Internet on <https://lists.gnupg.org/pipermail/gcrypt-devel/2023-October/005572.html>, accessed on October 24th, 2023.</ref>

In August 2024, [[National Institute of Standards and Technology|NIST]] officially standardized CRYSTALS-Dilithium under the name ML-DSA, establishing it as the primary standard (FIPS 204<ref>{{Cite report |url=https://csrc.nist.gov/pubs/fips/204/final |title=Module-Lattice-Based Digital Signature Standard |last=Technology |first=National Institute of Standards and |date=2024-08-13 |publisher=U.S. Department of Commerce |issue=Federal Information Processing Standard (FIPS) 204 |language=en}}</ref>) for quantum-resistant digital signatures.<ref>{{Cite journal |date=2024-08-13 |title=NIST Releases First 3 Finalized Post-Quantum Encryption Standards |url=https://www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards |journal=NIST |language=en}}</ref>

== Security ==
Lattice-based cryptographic constructions hold a great promise for [[Public-key cryptography|public-key]] [[post-quantum cryptography]].<ref>{{Cite journal |last=Micciancio |first=Daniele |last2=Regev |first2=Oded |date=2008-07-22 |title=Lattice-based cryptography |url=https://www.cims.nyu.edu/~regev/papers/pqc.pdf |journal=Nyu.edu |accessdate=2017-01-11}}</ref> Indeed, the main alternative forms of public-key cryptography are schemes based on the hardness of [[Integer factorization|factoring]] and [[RSA (cryptosystem)|related problems]] and schemes based on the hardness of the [[discrete logarithm]] and [[Diffie–Hellman problem|related problems]]. However, both factoring and the discrete logarithm problem are known to be solvable in [[BQP|polynomial time on a quantum computer]].<ref>{{Cite journal |last=Shor |first=Peter W. |date=1997-10-01 |title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer |journal=SIAM Journal on Computing |volume=26 |issue=5 |pages=1484–1509 |arxiv=quant-ph/9508027 |doi=10.1137/S0097539795293172 |issn=0097-5397 |s2cid=2337707}}</ref> Furthermore, algorithms for factorization tend to yield algorithms for discrete logarithm, and conversely. 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 complexity|worst-case]]'' hardness of certain lattice problems.<ref name=":1" /><ref name=":2" /><ref name=":3" /> 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. However, for the practical lattice-based constructions (such as schemes based on NTRU and even schemes based on LWE with efficient parameters), meaningful reduction-based guarantees of security are not known.

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''.<ref>{{Citation |last=Bellare |first=Mihir |title=Practice-Oriented Provable-Security |volume=1396 |pages=221–231 |year=1998 |series=Lecture Notes in Computer Science |publisher=Springer-Verlag |doi=10.1007/BFb0030423}}</ref> Authors who have investigated concrete security for lattice-based cryptosystems have found that the provable security results for such systems do not provide any meaningful concrete security for practical values of the parameters.<ref>{{Cite journal |last=Koblitz |first=Neal |last2=Samajder |first2=Subhabrata |last3=Sarkar |first3=Palash |last4=Singha |first4=Subhadip |year=2022 |title=Concrete analysis of approximate ideal-SIVP to decision ring-LWE reduction |url=https://www.aimsciences.org/article/doi/10.3934/amc.2022082 |journal=Advances in the Mathematics of Communications |doi=10.3934/amc.2022082 |doi-access=free}}</ref><ref>{{Citation |last=Gärtner |first=Joel |title=Concrete Security from Worst-Case to Average-Case Lattice Reductions |volume=14064 |pages=344–369 |year=2023 |url=https://link.springer.com/chapter/10.1007/978-3-031-37679-5_15 |series=Lecture Notes in Computer Science |publisher=Springer-Verlag |isbn=978-3-031-37678-8}}</ref>

== Functionality ==
For many cryptographic primitives, the only known constructions are based on lattices or closely related objects. These primitives include [[Homomorphic encryption|fully homomorphic encryption]],<ref name=":5" /> [[indistinguishability obfuscation]],<ref name=":6">{{Cite journal |last=Garg |first=Sanjam |last2=Gentry |first2=Craig |last3=Halevi |first3=Shai |last4=Raykova |first4=Mariana |last5=Sahai |first5=Amit |last6=Waters |first6=Brent |date=2013-01-01 |title=Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits |url=https://eprint.iacr.org/2013/451 |journal=Cryptology ePrint Archive |citeseerx=10.1.1.400.6501}}</ref> [[cryptographic multilinear map]]s, and [[functional encryption]].<ref name=":6" />

== See also ==
* [[Lattice problems]]
* [[Learning with errors]]
* [[Homomorphic encryption]]
* [[Post-quantum cryptography]]
* [[Ring learning with errors]]
* [[Ring learning with errors key exchange|Ring learning with Errors Key Exchange]]

== References ==
<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.

{{Cryptography public-key}}
{{Cryptography navbox}}

{{DEFAULTSORT:Lattice Based Cryptography}}
[[Category:Lattice-based cryptography| ]]
[[Category:Post-quantum cryptography]]