Expressive encryption from hard lattice problems

Traditionally, in cryptography, lattices have been used for cryptanalysis, i.e. in breaking cryptosystems. However, since Ajtai's breakthrough result (in 1996) which established surprising connections between average case and worst case hardness of various lattice problems, there has been great interest in constructing cryptosystems from hard lattice problems. We will describe the first Identity Based Encryption system (in which any arbitrary string, usually name or email address, can be one's public key) from lattices in the standard model (independently discovered by Cash, Hofheinz, Kiltz, Peikert) . Next, we will present methods to substantially improve the above IBE construction to make it more space and time efficient. We will also present a new method for 'lattice basis delegation' which allows the construction of more expressive IBE (hierarchical IBE), and compare this new technique with the earlier basis delegation mechanism of CHKP. To conclude, we will discuss future directions in building even more expressive encryption systems from lattices. The material discussed is from joint work with Dan Boneh and Xavier Boyen.