Zvika Brakerski (Theory Seminar Sp12)

"Fully Homomorphic Encryption from LWE"
Zvika Brakerski
Stanford University
Monday, April 30, 2012, 2:00 pm
EBU3B, Room 4140
Abstract:

A fully homomorphic encryption (FHE) scheme is a method of encryption that supports computation on encrypted data. More precisely, for any efficient function f, it is possible to convert an encryption of a (unknown) message m into an encryption of f(m) using solely public information. FHE enables a multitude of cryptographic applications, such as outsourcing computation to third parties without compromising data privacy, and is thus a sought-after tool for cloud applications.

Developing an FHE scheme has been a goal in cryptography since the late 70s. Three years ago, in a breakthrough work, Gentry presented the first candidate construction; however, the initial schemes were quite complicated to explain, prove, and implement. Last year, we showed how to base FHE on the learning with errors (LWE) assumption, yielding a construction with simplified presentation and improved efficiency and security. Since then, a new generation of candidate constructions has evolved.

In the talk, I will present the current state of the art in constructing fully homomorphic encryption from LWE. It will be based on my recent paper, and also on previous joint works with Vinod Vaikuntanathan and with Vinod Vaikuntanathan and Craig Gentry.