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.
Vadim Lyubashevsky (#336)
Topic of his/her doctorate.
Towards Practical Lattice-Based Cryptography
lattice techniques,public-key cryptography,hash functions,digital signatures,
Year of completion
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
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.