Efficient Fully Homomorphic Encryption from (Standard) LWE

Efficient Fully Homomorphic Encryption from (Standard) LWE

2011 | Zvika Brakerski, Vinod Vaikuntanathan
This paper presents a fully homomorphic encryption (FHE) scheme based solely on the learning with errors (LWE) assumption. The security of the scheme is grounded in the worst-case hardness of solving short vector problems on arbitrary lattices. The construction improves upon previous works in two key aspects: (1) it shows that "somewhat homomorphic" encryption can be based on LWE using a new re-linearization technique, avoiding the need for ideal lattice assumptions. (2) it deviates from the "squashing paradigm" by introducing a dimension-modulus reduction technique that shortens ciphertexts and reduces decryption complexity without additional assumptions. The scheme has very short ciphertexts, enabling the construction of an asymptotically efficient LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of the protocol is $ k \cdot \text{polylog}(k) + \log |\text{DB}| $ bits per single-bit query, where $ k $ is a security parameter and $ |\text{DB}| $ is the size of the database. The paper introduces a re-linearization technique to achieve somewhat homomorphic encryption without ideal lattice assumptions. This technique allows the evaluation of linear functions and enables the construction of a fully homomorphic encryption scheme through dimension-modulus reduction. The reduction technique allows the conversion of a ciphertext with parameters $ (n, \log q) $ into one with parameters $ (k, \log p) $, significantly reducing the size of the ciphertext and enabling efficient homomorphic evaluation. The scheme is used to construct a PIR protocol with near-optimal communication complexity. The paper also discusses related work, including other fully homomorphic encryption schemes and their security assumptions. The paper concludes with an overview of the paper's organization and a discussion of preliminary concepts, including the LWE problem and symmetric encryption. The main technical section presents the new FHE scheme, its security analysis, and performance evaluation. The paper demonstrates that the scheme is secure under the LWE assumption and has efficient homomorphic properties, enabling the construction of a fully homomorphic encryption scheme based on LWE.This paper presents a fully homomorphic encryption (FHE) scheme based solely on the learning with errors (LWE) assumption. The security of the scheme is grounded in the worst-case hardness of solving short vector problems on arbitrary lattices. The construction improves upon previous works in two key aspects: (1) it shows that "somewhat homomorphic" encryption can be based on LWE using a new re-linearization technique, avoiding the need for ideal lattice assumptions. (2) it deviates from the "squashing paradigm" by introducing a dimension-modulus reduction technique that shortens ciphertexts and reduces decryption complexity without additional assumptions. The scheme has very short ciphertexts, enabling the construction of an asymptotically efficient LWE-based single-server private information retrieval (PIR) protocol. The communication complexity of the protocol is $ k \cdot \text{polylog}(k) + \log |\text{DB}| $ bits per single-bit query, where $ k $ is a security parameter and $ |\text{DB}| $ is the size of the database. The paper introduces a re-linearization technique to achieve somewhat homomorphic encryption without ideal lattice assumptions. This technique allows the evaluation of linear functions and enables the construction of a fully homomorphic encryption scheme through dimension-modulus reduction. The reduction technique allows the conversion of a ciphertext with parameters $ (n, \log q) $ into one with parameters $ (k, \log p) $, significantly reducing the size of the ciphertext and enabling efficient homomorphic evaluation. The scheme is used to construct a PIR protocol with near-optimal communication complexity. The paper also discusses related work, including other fully homomorphic encryption schemes and their security assumptions. The paper concludes with an overview of the paper's organization and a discussion of preliminary concepts, including the LWE problem and symmetric encryption. The main technical section presents the new FHE scheme, its security analysis, and performance evaluation. The paper demonstrates that the scheme is secure under the LWE assumption and has efficient homomorphic properties, enabling the construction of a fully homomorphic encryption scheme based on LWE.
Reach us at info@futurestudyspace.com