The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


             Walmart Lecture Series in Cryptography and Complexity

                     Lecture Hall, Room 1, Ziskind Building
                          on Wednesday, June 15, 2011
                                 14:00 - 16:00





                                Zvika Brakerski



                                 will speak on


                     Efficient Fully Homomorphic Encryption
                              from (Standard) LWE

Abstract:
In fully homomorphic encryption, it is possible to transform an encryption of a
message, $m$, into an encryption of any (efficient) function of that message,
$f(m)$, without knowing the secret key. This property makes it into a very
useful cryptographic building block.

We present a fully homomorphic encryption scheme that is based solely on the
(standard) learning with errors (LWE) assumption. Applying known results on
LWE, the security of our scheme is based on the worst-case hardness of short
vector problems on arbitrary lattices.  As icing on the cake, our scheme is
quite efficient, and has very short ciphertexts.

Our construction improves upon previous works in two aspects:

1.  We show that ``somewhat homomorphic'' encryption can be based on LWE,
   using a new {\it re-linearization} technique. In contrast, all previous
   schemes relied on complexity assumptions related to ideals in various
   rings.

2.  We deviate from the ``squashing paradigm'' used
   in all previous works. We introduce a new {\it dimension reduction}
  technique, which shortens the ciphertexts and reduces the decryption
  complexity of our scheme, without introducing additional assumptions.
   In contrast, all previous works required an additional, very strong
  assumption (namely, the sparse subset sum assumption).

Since our scheme has very short ciphertexts, we use it to construct an
asymptotically-efficient LWE-based single-server private information retrieval
(PIR) protocol. The communication complexity of our protocol (in the public-key
model) is $k \cdot {\rm polylog}\,k+\log |DB|$ bits per single-bit query, which
is better than any known scheme. Previously, it was not known how to achieve a
communication complexity of even ${\rm poly}(k, \log|DB|)$ based on LWE.

Joint work with Vinod Vaikuntanathan.