Adriana López-Alt
New York University

Efficient Fully Homomorphic Encryption From (Standard) LWE

We present a fully homomorphic encryption scheme that is based
solely on the (standard) learning with errors (LWE) assumption.
Our construction improves on previous works in two aspects:

1. We show that ``somewhat homomorphic'' encryption can be based on
 LWE, using a new 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 dimension-modulus 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).

Work by:
Zvika Brakerski and Vinod Vaikuntanathan