Abstract
Cryptographic schemes based on lattices first emerged in the mid-1990s, and have developed rapidly in the past few years. At the outset, works in this area fell into two very distinct types:
-
Heuristic proposals such as NTRU, which lacked any formal security justification but were very practical;
-
Schemes building on Ajtai’s breakthrough work, which were highly impractical but came with provable ‘worst-case’ security guarantees.
More recently, the line between efficiency and rigorous security has been blurred significantly (though not yet obliterated completely).
This talk will survey several examples of early proposals that lacked any rigorous security analysis — and in some cases, turned out to be completely insecure — but which later inspired theoretically sound and efficient solutions. Even better, these solutions have opened the door to unexpected and far more advanced cryptographic applications than were originally envisioned.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Peikert, C. (2010). Heuristics and Rigor in Lattice-Based Cryptography. In: Garay, J.A., De Prisco, R. (eds) Security and Cryptography for Networks. SCN 2010. Lecture Notes in Computer Science, vol 6280. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15317-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-15317-4_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15316-7
Online ISBN: 978-3-642-15317-4
eBook Packages: Computer ScienceComputer Science (R0)