The paper presents a novel approach to fully homomorphic encryption (FHE) that significantly improves performance and bases security on weaker assumptions. The authors introduce a new method to construct leveled FHE schemes capable of evaluating arbitrary polynomial-size circuits without using Gentry's bootstrapping procedure. They offer two main constructions:
1. **FHE Scheme Based on Ring LWE (RLWE):** This scheme can evaluate depth-$L$ arithmetic circuits using $\tilde{O}(\lambda \cdot L^3)$ per-gate computation, which is quasi-linear in the security parameter $\lambda$. Security is based on RLWE for an approximation factor exponential in $L$. This construction does not use the bootstrapping procedure.
2. **FHE Scheme Based on LWE:** This scheme can evaluate depth-$L$ arithmetic circuits using $\tilde{O}(\lambda^2)$ per-gate computation, which is independent of $L$. Security is based on RLWE for quasi-polynomial factors. This construction uses bootstrapping as an optimization.
The authors also introduce optimizations based on the Ring LWE assumption, such as batched bootstrapping, which reduces the per-gate computation to $\tilde{O}(\lambda)$ for circuits with large width. The core of their construction is a noise management technique that effectively controls the noise level of lattice-based ciphertexts during homomorphic operations, using techniques introduced by Brakerski and Vaikuntanathan. This technique allows for efficient evaluation of arbitrary polynomial-size arithmetic circuits without relying on bootstrapping.The paper presents a novel approach to fully homomorphic encryption (FHE) that significantly improves performance and bases security on weaker assumptions. The authors introduce a new method to construct leveled FHE schemes capable of evaluating arbitrary polynomial-size circuits without using Gentry's bootstrapping procedure. They offer two main constructions:
1. **FHE Scheme Based on Ring LWE (RLWE):** This scheme can evaluate depth-$L$ arithmetic circuits using $\tilde{O}(\lambda \cdot L^3)$ per-gate computation, which is quasi-linear in the security parameter $\lambda$. Security is based on RLWE for an approximation factor exponential in $L$. This construction does not use the bootstrapping procedure.
2. **FHE Scheme Based on LWE:** This scheme can evaluate depth-$L$ arithmetic circuits using $\tilde{O}(\lambda^2)$ per-gate computation, which is independent of $L$. Security is based on RLWE for quasi-polynomial factors. This construction uses bootstrapping as an optimization.
The authors also introduce optimizations based on the Ring LWE assumption, such as batched bootstrapping, which reduces the per-gate computation to $\tilde{O}(\lambda)$ for circuits with large width. The core of their construction is a noise management technique that effectively controls the noise level of lattice-based ciphertexts during homomorphic operations, using techniques introduced by Brakerski and Vaikuntanathan. This technique allows for efficient evaluation of arbitrary polynomial-size arithmetic circuits without relying on bootstrapping.