International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

Details

Vadim Lyubashevsky (#336)
Name Vadim Lyubashevsky
Personal Homepage http://www.di.ens.fr/~lyubash/
Topic of his/her doctorate. Towards Practical Lattice-Based Cryptography
Category public-key cryptography
Keywords lattice techniques,public-key cryptography,hash functions,digital signatures,
Ph.D. Supervisor(s) Daniele Micciancio
Year of completion 2008
Abstract 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 ineĀ±cient 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 ide- als 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 construc- tions that have no provable security. We also give constructions of provably-secure identification and signature schemes whose asymptotic running times are almost lin- ear (up to poly-logarithmic factors), and so these schemes are much more eĀ±cient 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 nearly optimal efficiency.
Last Change 2011-04-16 11:36:15
To provide an update on this entry, please click .

Contact: phds (at) iacr.org

[ IACR home page ] [ IACR PhDs page ] © IACR