Towards practical lattice-based cryptography
- Author(s): Lyubashevsky, Vadim
- et al.
Lattice-based cryptography began with the seminal work of Ajtai (Ajtai '96) who showed that it is possible to build families of cryptographic functions in which breaking a randomly chosen element of the family is as hard as solving worst-case instances of lattice problems. This work generated great interest and resulted in constructions of many other cryptographic protocols with security based on worst-case lattice problems. An additional advantage of lattice-based primitives is that, unlike their counterparts based on factoring and discrete log, they are conjectured to be secure in the advent of quantum computing. The main disadvantage of lattice-based constructions is that they generally involve operations on, and storage of, large n x n matrices. This resulted in the schemes being rather inefficient and unsuitable for practical use. To cope with this inherent inefficiency, Micciancio proposed to build lattice-based primitives based on the worst-case hardness of lattices that have some additional structure. In (Micciancio '02), he showed how to build one-way functions, computable in almost linear time, with security based on worst-case problems on such lattices. While interesting from a theoretical perspective, one-way functions are not very useful in practice. Our goal in this thesis is to present constructions of practical and efficient cryptographic protocols whose security is based on worst-case hardness of lattice problems. We first show how to build collision- resistant hash functions whose security is based on the hardness of lattice problems in all lattices with a special structure. The special structure that the lattices possess is that they are ideals of certain polynomial rings. The hash functions that we build have almost linear running time, and in practice turn out to be essentially as efficient as ad-hoc constructions that have no provable security. We also give constructions of provably-secure identification and signature schemes whose asymptotic running times are almost linear (up to poly-logarithmic factors), and so these schemes are much more efficient than comparable primitives with security based on factoring and discrete log. Thus our work implies that by considering ideal lattices, it is possible to have the best of both worlds: security based on worst-case problems and optimal efficiency