2012 | OriginalPaper | Chapter
Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
Author : Zvika Brakerski
Published in: Advances in Cryptology – CRYPTO 2012
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a new tensoring technique for LWE-based fully homomorphic encryption. While in all previous works, the ciphertext noise grows quadratically (
B
→
B
2
·poly(
n
)) with every multiplication (before “refreshing”), our noise only grows linearly (
B
→
B
·poly(
n
)).
We use this technique to construct a
scale-invariant
fully homomorphic encryption scheme, whose properties only depend on the ratio between the modulus
q
and the initial noise level
B
, and not on their absolute values.
Our scheme has a number of advantages over previous candidates: It uses the same modulus throughout the evaluation process (no need for “modulus switching”), and this modulus can take arbitrary form. In addition, security can be
classically
reduced from the worst-case hardness of the GapSVP problem (with quasi-polynomial approximation factor), whereas previous constructions could only exhibit a quantum reduction from GapSVP.