Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP

Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP

2012 | Zvika Brakerski
This paper presents a new tensoring technique for LWE-based fully homomorphic encryption (FHE), which reduces the noise growth from quadratic to linear with each multiplication. The technique allows for a scale-invariant FHE scheme, where the security and properties depend only on the ratio between the modulus q and the initial noise level B, not their absolute values. The scheme uses a single modulus throughout the evaluation process, eliminating the need for "modulus switching" and enabling more efficient and simpler implementations. Security can be classically reduced from the worst-case hardness of the GapSVP problem with quasi-polynomial approximation factor, unlike previous constructions that relied on quantum reductions. The scheme is based on Regev's original LWE-based encryption, with additional auxiliary information for homomorphic evaluation. It achieves scale invariance by working in an invariant perspective where only the ratio q/B matters. This approach allows for efficient homomorphic addition and multiplication, with noise growing polynomially rather than exponentially. The scheme also supports any modulus q, including powers of two, which can simplify arithmetic operations. It does not require specific secret key distributions and can be used with any distribution that satisfies the LWE assumption. The paper also discusses the implications of the scheme, including the ability to achieve fully homomorphic encryption using bootstrapping and without it. It shows that the scheme can be used to construct a leveled fully homomorphic encryption scheme based on the classical worst-case hardness of the GapSVP problem. The scheme is also efficient and can be implemented with practical optimizations, such as reducing the size of the evaluation key and truncating ciphertexts without significant loss of accuracy. The paper concludes that the scheme has significant theoretical and practical implications for FHE, offering a simpler and more efficient approach to homomorphic encryption.This paper presents a new tensoring technique for LWE-based fully homomorphic encryption (FHE), which reduces the noise growth from quadratic to linear with each multiplication. The technique allows for a scale-invariant FHE scheme, where the security and properties depend only on the ratio between the modulus q and the initial noise level B, not their absolute values. The scheme uses a single modulus throughout the evaluation process, eliminating the need for "modulus switching" and enabling more efficient and simpler implementations. Security can be classically reduced from the worst-case hardness of the GapSVP problem with quasi-polynomial approximation factor, unlike previous constructions that relied on quantum reductions. The scheme is based on Regev's original LWE-based encryption, with additional auxiliary information for homomorphic evaluation. It achieves scale invariance by working in an invariant perspective where only the ratio q/B matters. This approach allows for efficient homomorphic addition and multiplication, with noise growing polynomially rather than exponentially. The scheme also supports any modulus q, including powers of two, which can simplify arithmetic operations. It does not require specific secret key distributions and can be used with any distribution that satisfies the LWE assumption. The paper also discusses the implications of the scheme, including the ability to achieve fully homomorphic encryption using bootstrapping and without it. It shows that the scheme can be used to construct a leveled fully homomorphic encryption scheme based on the classical worst-case hardness of the GapSVP problem. The scheme is also efficient and can be implemented with practical optimizations, such as reducing the size of the evaluation key and truncating ciphertexts without significant loss of accuracy. The paper concludes that the scheme has significant theoretical and practical implications for FHE, offering a simpler and more efficient approach to homomorphic encryption.
Reach us at info@study.space
Understanding Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP