Only two number-theoretic assumptions --- hardness of factoring and of
computing discrete logarithms --- underlie essentially all public-key
cryptosystems in widespread use today. For lower-level primitives
such as hash functions, random number generators, and stream ciphers,
the situation is even worse: existing provably-secure constructions
are too inefficient to compete with practical alternatives such as
SHA-1 or AES, and so the primitives in use today have no rigorous
justification for their security.
This research will investigate new classes of computational
assumptions based on lattices. Based on these assumptions, the
investigators will seek to design cryptographic primitives that are
both provably secure and comparably efficient to existing, deployed
schemes. The research will explore the use of lattices to construct
basic cryptographic primitives, including hash functions, pseudorandom
generators, shared-key authentication protocols, public-key encryption
schemes (including those secure against chosen-ciphertext attacks),
and digital signatures. The educational component of this work will
focus on educating graduate students as well as developing
introductory-level surveys of lattice-based cryptography.
