We present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits),  without Gentry's bootstrapping procedure .   Specifically, we offer a choice of FHE schemes based on the learning with error (LWE) or ring-LWE (RLWE) problems that have 2 λ  security against known attacks. For RLWE, we have:   • A leveled FHE scheme that can evaluate  L -level arithmetic circuits with  O (λ ·  L  3 ) per-gate computation -- i.e., computation  quasi-linear  in the security parameter. Security is based on RLWE for an approximation factor exponential in  L . This construction does not use the bootstrapping procedure.   • A leveled FHE scheme that uses bootstrapping  as an optimization , where the per-gate computation (which includes the bootstrapping procedure) is  O (λ 2 ),  independent of L . Security is based on the hardness of RLWE for  quasi-polynomial  factors (as opposed to the sub-exponential factors needed in previous schemes).   We obtain similar results to the above for LWE, but with worse performance.   Based on the Ring LWE assumption, we introduce a number of further optimizations to our schemes. As an example, for circuits of large width -- e.g., where a constant fraction of levels have width at least λ -- we can reduce the per-gate computation of the bootstrapped version to  O (λ), independent of  L , by  batching the bootstrapping operation . Previous FHE schemes all required Ω(λ 3.5 ) computation per gate.   At the core of our construction is a much more effective approach for managing the noise level of lattice-based ciphertexts as homomorphic operations are performed, using some new techniques recently introduced by Brakerski and Vaikuntanathan (FOCS 2011).
['Zvika Brakerski', 'Craig Gentry', 'Vinod Vaikuntanathan']
Leveled) fully homomorphic encryption without bootstrapping