Definition
Lattice-based cryptography is a generic term used to encompass a wide range of cryptographic functions whose security is based on the conjectured intractability of Lattice problems, like (variants of) the Shortest Vector Problem and the Closest Vector Problems.
For applications of lattices in cryptanalysis, Lattice Reduction.
Background
The study of lattice-based cryptography was pioneered by Ajtai in 1996 [1], who proved that certain variants of the knapsack cryptographic schemes are at least as hard to break on the average as approximating(the length estimation variant of) theShortest Vector Problem(GapSVP)within factors that grow only polynomially in the dimensionn of thelattice. Two distinguishing features of Ajtai’s result, and lattice-basedcryptography in general, are that:
-
Breaking the cryptographic functions is...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Ajtai M (1996) Generating hard instances of lattice problems (extended abstract). In: Proceedings of the twenty-eighth annual ACM Symposium on the Theory of Computing (STOC’96), Philadelphia, 22–24 May 1996. ACM Press, New York, pp 99–108
Ajtai M, Dwork C (1997) A public-key cryptosystem with worstcase/average-case equivalence. In: Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing (STOC ’97), E1 Paso, 4–6 May 1997. ACM Press, New York, pp 284–293
Gentry C, Peikert C, Vaikuntanathan V (2008) Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of STOC ’08, Victoria, 17–20 May 2008. ACM Press, New York, pp 197–206
Lyubashevsky V, Micciancio D (2008) Asymptotically efficient lattice-based digital signatures. In: Proceedings of TCC ’08, New York, 19–21 March 2008. Lecture notes in computer science, vol 4948. Springer, Berlin, pp 37–54
Lyubashevsky V, Micciancio D (2009) On bounded distance decoding, unique shortest vectors, and the minimum distance problem. In: Proceedings of CRYPTO 2009, Santa Barbara, 16–20 August 2009. Lecture notes in computer science, vol 5677. Springer, Berlin, pp 577–594
Lyubashevsky V, Micciancio D, Peikert C, Rosen A (2008) Swifft: a modest proposal for FFT hashing. In: Proceedings of FSE ’08, Lausanne, 10–13 February 2008. Lecture notes in computer science, vol 5086. Springer, Berlin, pp 54–72
Micciancio D (2007) Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput Complex 16(4):365–411
Micciancio D, Regev O (2007) Worst-case to average-case reductions based on Gaussian measure. SIAM J Comput 37(1):267–302
Micciancio D, Regev O (2008) Lattice-based cryptography. In: Bernstein DJ, Buchmann J, Dahmén E (eds) Post-quantum cryptography. Springer, Berlin
Peikert C, Vaikuntanathan V (2008) Noninteractive statistical zeroknowledge proofs for lattice problems. In: Proceedings of CRYPTO ’08, Santa Barbara, 17–21 August 2008. Lecture notes in computer science, vol 5157. Springer, Berlin, pp 536–553
Peikert C, Vaikuntanathan V, Waters B (2008) A framework for efficient and composable oblivious transfer. In: Proceedings of CRYPTO ’08, Santa Barbara, 17–21 August 2008. Lecture notes in computer science, vol 5157. Springer, Berlin, pp 554–571
Peikert C, Waters B (2008) Lossy trapdoor functions and their applications. In: Proceedings of STOC ’08, Victoria, 17–20 May 2008. ACM Press, New York, pp 187–196
Regev O (2004) New lattice based cryptographic constructions. J ACM 51(6):899–942
Regev O (2005) On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of STOC ’05, Baltimore, 22–24 May 2005. ACM Press, New York, pp 84–93
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer Science+Business Media, LLC
About this entry
Cite this entry
Micciancio, D. (2011). Lattice-Based Cryptography. In: van Tilborg, H.C.A., Jajodia, S. (eds) Encyclopedia of Cryptography and Security. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-5906-5_417
Download citation
DOI: https://doi.org/10.1007/978-1-4419-5906-5_417
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4419-5905-8
Online ISBN: 978-1-4419-5906-5
eBook Packages: Computer ScienceReference Module Computer Science and Engineering