Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


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 quit e 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 {\em re-linearization} technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings. 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.

Questions and Answers

You need to be logged in to be able to post here.