[Resource Topic] 2013/541: Lattice-Based FHE as Secure as PKE

Welcome to the resource topic for 2013/541

Lattice-Based FHE as Secure as PKE

Authors: Zvika Brakerski, Vinod Vaikuntanathan


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.

ePrint: https://eprint.iacr.org/2013/541

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .