Lattice-Based FHE as Secure as PKE

Zvika Brakerski; Vinod Vaikuntanathan

Paper 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: public key encryption fully homomorphic encryption lattice based cryptography LWE
Contact author(s): zvika brakerski @ weizmann ac il
History: 2013-08-30: received
Short URL: https://ia.cr/2013/541
License: CC BY

BibTeX

@misc{cryptoeprint:2013/541,
      author = {Zvika Brakerski and Vinod Vaikuntanathan},
      title = {Lattice-Based FHE as Secure as PKE},
      howpublished = {Cryptology ePrint Archive, Paper 2013/541},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/541}},
      url = {https://eprint.iacr.org/2013/541}
}