Cryptology ePrint Archive: Report 2013/541
Lattice-Based FHE as Secure as PKE
Zvika Brakerski and Vinod Vaikuntanathan
Abstract: We show that (leveled) fully homomorphic encryption (FHE) can be based on the hardness of $\otild(n^{1.5+\epsilon})$-approximation for lattice problems (such as GapSVP) under quantum reductions for any $\epsilon>0$ (or $\otild(n^{2+\epsilon})$-approximation under classical reductions). This matches the best known hardness for ``regular'' (non-homomorphic) lattice based public-key encryption up to the $\epsilon$ factor. A number of previous methods had hit a roadblock at quasipolynomial approximation. (As usual, a circular security assumption can be used to achieve a non-leveled FHE scheme.)
Our approach consists of three main ideas: Noise-bounded sequential evaluation of
high fan-in operations; Circuit sequentialization using Barrington's Theorem; and finally,
successive dimension-modulus reduction.
Category / Keywords: public-key cryptography / public key encryption, fully homomorphic encryption, lattice based cryptography, LWE
Date: received 27 Aug 2013
Contact author: zvika brakerski at weizmann ac il
Available format(s): PDF | BibTeX Citation
Version: 20130830:130301 (All versions of this report)
Short URL: ia.cr/2013/541
[ Cryptology ePrint archive ]