This paper presents a novel approach to fully homomorphic encryption (FHE) that significantly improves performance and reduces security assumptions. The authors introduce a leveled FHE scheme that can evaluate arbitrary polynomial-size circuits without bootstrapping, based on the Learning With Errors (LWE) or Ring LWE (RLWE) problems. The key contributions include:
1. A leveled FHE scheme that evaluates depth-L arithmetic circuits with per-gate computation of $ \tilde{O}(\lambda \cdot L^3) $, based on RLWE with exponential approximation factors. This scheme does not use bootstrapping.
2. A leveled FHE scheme that evaluates depth-L arithmetic circuits with per-gate computation of $ \tilde{O}(\lambda^2) $, based on RLWE with quasi-polynomial approximation factors. This scheme uses bootstrapping as an optimization.
The authors also introduce a noise management technique called modulus switching, which allows for efficient noise reduction without bootstrapping. This technique involves iteratively reducing the modulus size while maintaining a constant noise level. The scheme leverages the properties of RLWE and uses a ladder of moduli to manage noise effectively.
The paper also discusses the efficiency of FHE schemes, highlighting the limitations of previous schemes that relied on bootstrapping and sub-exponential hardness assumptions. The authors propose a new approach that reduces the per-gate computation to $ \tilde{O}(\lambda \cdot L^3) $ for non-bootstrapped schemes and $ \tilde{O}(\lambda^2) $ for bootstrapped schemes.
The authors also introduce batching as an optimization, which allows multiple plaintexts to be encrypted into a single ciphertext, reducing the per-gate computation for circuits of large width. This technique is particularly effective for RLWE-based schemes.
The paper concludes with a discussion of related work and future directions, including the potential for further improvements in efficiency and security assumptions. The authors' approach represents a significant advancement in FHE, offering more efficient schemes with weaker security assumptions.This paper presents a novel approach to fully homomorphic encryption (FHE) that significantly improves performance and reduces security assumptions. The authors introduce a leveled FHE scheme that can evaluate arbitrary polynomial-size circuits without bootstrapping, based on the Learning With Errors (LWE) or Ring LWE (RLWE) problems. The key contributions include:
1. A leveled FHE scheme that evaluates depth-L arithmetic circuits with per-gate computation of $ \tilde{O}(\lambda \cdot L^3) $, based on RLWE with exponential approximation factors. This scheme does not use bootstrapping.
2. A leveled FHE scheme that evaluates depth-L arithmetic circuits with per-gate computation of $ \tilde{O}(\lambda^2) $, based on RLWE with quasi-polynomial approximation factors. This scheme uses bootstrapping as an optimization.
The authors also introduce a noise management technique called modulus switching, which allows for efficient noise reduction without bootstrapping. This technique involves iteratively reducing the modulus size while maintaining a constant noise level. The scheme leverages the properties of RLWE and uses a ladder of moduli to manage noise effectively.
The paper also discusses the efficiency of FHE schemes, highlighting the limitations of previous schemes that relied on bootstrapping and sub-exponential hardness assumptions. The authors propose a new approach that reduces the per-gate computation to $ \tilde{O}(\lambda \cdot L^3) $ for non-bootstrapped schemes and $ \tilde{O}(\lambda^2) $ for bootstrapped schemes.
The authors also introduce batching as an optimization, which allows multiple plaintexts to be encrypted into a single ciphertext, reducing the per-gate computation for circuits of large width. This technique is particularly effective for RLWE-based schemes.
The paper concludes with a discussion of related work and future directions, including the potential for further improvements in efficiency and security assumptions. The authors' approach represents a significant advancement in FHE, offering more efficient schemes with weaker security assumptions.