International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 30 August 2013

Zvika Brakerski, Vinod Vaikuntanathan
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.