Lattice-Based FHE as Secure as PKE

Zvika Brakerski; Vinod Vaikuntanathan

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

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}
}