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.
