Lattice-based FHE as secure as PKE

By Zvika Brakerski, Vinod Vaikuntanathan. IACR Cryptology ePrint Archive, 2014

300 citations recorded by the source corpus.

We show that (leveled) fully homomorphic encryption (FHE) can be based on the hardness of O(n1.5+ε)-approximation for lattice problems (such as GapSVP) under quantum reductions for any ε 〉 0 (or O(n2+ε)-approximation under classical reductions). This matches the best known hardness for "regular" (non-homomorphic) lattice based public-key encryption up to the ε 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.

View Paper: https://www.semanticscholar.org/paper/0109f31986502b1f2b55907a808d48bc7f3ff87a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

TFHE: Fast Fully Homomorphic Encryption Over the Torus (2019, methodology): “Due to an asymmetry in the noise propagation, it was noticed in [8,15,35] that GSW ciphertext is particularly suited to evaluate long chains of products, or branching programs.”
Function Secret Sharing (2015, background): “…constructions to date of homomorphic encryption and reusable garbled circuits (even for the restricted class AC 0 ), such as those from [11, 10, 33], rely on Learning With Errors (LWE) [42] or similar lattice-based assumptions; a construction under weaker or signiﬁcantly different…”
Faster Bootstrapping with Polynomial Error (2014, methodology): “To further improve the assumptions at a (high) cost in efficiency, we can let n = λ to directly yield Õ(n ) factors for any ∈ (0, 1), or we can use the successive dimension/modulus-reduction technique from [7] to obtain Õ(n ) factors.”
Compressible FHE with Applications to PIR (2019, methodology): “Following [GSW13,BV14b], when using GSW with fresh-ciphertext noise of size α and ciphertext matrices of dimension n 1 × m , we can perform arbitrary computation and then bootstrap the result, and the noise after bootstrapping is bounded below αm 2 .”
A Survey on Homomorphic Encryption Schemes (2017, methodology): “For instance, it does not implement modern techniques (e.g., modulus reduction and re-linearization techniques [Brakerski and Vaikuntanathan 2014a]) to handle the noise level or it also does not support the SIMD techniques introduced in [Smart and Vercauteren 2014].”
Homomorphic Encryption (2017, methodology): “The second generation began in 2011 with the works of Brakerski-Vaikuntanathan [19] and Brakerski et al. [16], and was characterized by much better techniques for controlling the noise, resulting in improved efficiency while at the same time basing security on well-established hardness assumptions.”
SHIELD: Scalable Homomorphic Implementation of Encrypted Data-Classifiers (2015, background): “It is the mapping of the LWE problem from the vectors over Zq to polynomial rings over Rq .”
Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds (2016, background): “The last corollary describes exactly the classical internal product between two TGSW samples, already presented in [10, 19, 3, 16, 14] with adapted notations.”
Improving TFHE: faster packed homomorphic operations and efficient circuit bootstrapping (2017, methodology): “that all the bootstrapping uses (Ring) instantiations of TRGSW, the design in [8] based on the expansion of the decryption circuit via Barrington theorem, as well as the expression as a minimal deterministic automata of the same function in [19] require a quadratic number of internal level 2 TRGSW p”
A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem (2012, background): “Many lattice-based primitives based on LWE have been discovered, such as public-key encryption [25,16,20], (hierarchical) identity-based encryption [16,1,12], functional encryption [3,2,5,17] and fully homomorphic encryption [9,7,6,10].”
A High-Speed Accelerator for Homomorphic Encryption using the Karatsuba Algorithm (2017, background): “138:2 V. Migliore et al. Most promising Fully Homomorphic Encryption (FHE) schemes base their arithmetic on a ring of polynomials with integer coefficients [5], [6], [7], [8], [9], [10].”