[Busec] MIT, 4:15PM Tomorrow - Efficient Fully Homomorphic Encryption from (Standard) LWE , S

Sharon Goldberg goldbe at cs.bu.edu
Mon May 9 09:17:24 EDT 2011

Hi BUsec,

I'm heading to this talk at MIT from BU tomorrow around 3:15PM.  Come
by my office if you'd like to join me for the trip over to MIT.  This
could be a very big result.


---------- Forwarded message ----------
From: Be Blackburn <be at csail.mit.edu>
Date: Mon, May 9, 2011 at 8:34 AM
Subject: [Theory-seminars] did you catch it? 4:15 to 5:15: Efficient
Fully Homomorphic Encryption from (Standard) LWE , S
To: theory-seminars at csail.mit.edu

Talk:      Efficient Fully Homomorphic Encryption from (Standard) LWE
Speaker: Zvika Brakerski, Weizmann Institute of Science and CSAIL, MIT
Date:      Tuesday, May 10 2011
Time:      4:15 pm to 5:15 pm
Snacks    3:45 pm
Where:    32-155
Host:       Scott Aaronson, CSAIL, MIT

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

Our construction improves upon previous works in two aspects:

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

2. More importantly, we deviate from the ``squashing paradigm'' used
in all previous works. We introduce a new {\em 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 \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
$\poly(k, \log|DB|)$ based on LWE.

Joint work with Vinod Vaikuntanathan.

Theory-seminars mailing list
Theory-seminars at lists.csail.mit.edu

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list