Valeria Nikolaenko: 2014 Security Workshop


Monday, April 14, 2014
Location: Fisher Conference Center, Arrillaga Alumni Center

"Fully Key-Homomorphic Encryption and Applications"


The concept of Fully-Homomorphic Encryption (FHE) was first introduced in 1978. The first construction discovered by ?. Gentry in 2009 was a major breakthrough in the world of cryptography. FHE is a public key encryption system that allows to carry arbitrary computations on encrypted data. We introduced a new concept that we called Fully Key-Homomorphic Encryption (FKHE) which is an Identity-Based Encryption system* (IBE) scheme where anyone can carry out computations on the public key. We built such a primitive based on a hard lattice problem called learning with errors (LWE).

We showed that our FKHE implies the most efficient Attribute Based Encryption** (ABE) known to date. Our construction gives secret keys that are linear in the depth of the circuit (not its size as in the previous constructions), it provides full delegation capabilities, and supports arithmetic circuits (not just boolean circuits as in previous constructions). Our efficient ABE scheme can be used in a compiler of Goldwasser et al. to create a succinct reusable garbled circuit, which asymptotically gives the most efficient multiparty computation protocol in terms of communication known to date. This work will appear in Eurocrypt 2014.

* IBE is an encryption scheme where the public key of the user is his/her the identity, i.e. an email or a name ** ABE is an encryption scheme where the ciphertexts are labeled with sets of attributes and private keys are associated with access structures that control which ciphertexts a user is able to decrypt.


Valeria Nikolaenko is a PhD student in Computer Science advised by Prof. Boneh. Her research focuses on theoretical foundations of cryptography and practical applications. In the first area she develops new tools in lattice-based cryptography. In the second she studies the problem of running machine learning algorithms on gigabytes of encrypted user data. The resulting learned model is available to applications in the clear, but nothing else is revealed about the underlying user data.