Abstract
This paper presents an efficient Somewhat Homomorphic Encryption (SHE) scheme based on the Approximate Greatest Common Divisor (AGCD) problem over integers. By reducing the number of public key elements to just two integers, the proposed scheme achieves a public key size complexity of $\tilde{O}(\lambda^3)$, a significant improvement over previous $\tilde{O}(\lambda^7)$ schemes. We further introduce an optimized evaluation technique to manage ciphertext growth, making integer-based HE more practical for real-world applications.
1. Introduction
Homomorphic Encryption (HE) is a critical technology for privacy-preserving computation, allowing servers to process encrypted data without decryption. However, early integer-based HE schemes, such as the 2010 work by Dijk et al., suffered from prohibitive public key sizes ($\tilde{O}(\lambda^{10})$). Even subsequent improvements reached only $\tilde{O}(\lambda^7)$, resulting in an 802MB public key for a standard security level ($\lambda=72$). This paper addresses this bottleneck by proposing a scheme with a drastically smaller footprint.
2. Methodology
The core of the proposed scheme is the reduction of the public key to just two integers, $x_0$ and $x_1$, based on the Approximate-GCD problem.
2.1 Notation
The mathematical notation used in the construction of the scheme is detailed in the table below.
2.2 Key Generation and Encryption
The scheme's efficiency stems from its simplified key structure:
- Key Generation (KG): Instead of a large list of approximate multiples of a secret prime $p$, the scheme generates only two: $x_0$ and $x_1$. This reduction in the number of public elements is the primary driver of the smaller key size.
- Encryption (Enc): A message $m$ is encrypted as $c = m + 2r + 2r_1 \cdot x_1 \pmod{x_0}$, where $r$ and $r_1$ are random noise values.
2.3 Optimized Evaluation (Opt-Eval)
To prevent exponential ciphertext growth during homomorphic operations, the authors introduce a modular reduction technique. By adding a small set of auxiliary public elements, the Eval algorithm can perform "modular reduction" on the ciphertext, maintaining its size and ensuring the scheme remains compact.
3. Results and Analysis
The scheme was evaluated using Shoup’s NTL library (v5.5.2) on an Intel CPU P8400.
3.1 Public Key Size
The most significant result is the reduction in public key complexity to $\tilde{O}(\lambda^3)$. For a security level of $\lambda=72$, the estimated key size is under 1MB, representing a nearly 1000x reduction compared to the 802MB required by previous state-of-the-art integer schemes.
3.2 Evaluation Capability
Simulations demonstrated that for $\lambda=72$, the scheme can successfully evaluate circuits with a degree $d$ between 36 and 39. The evaluating ability scales with the security parameter $\lambda$ but is independent of the message length $l$.
4. Conclusion
This work demonstrates that integer-based SHE can be made efficient enough for practical use by optimizing the number of public key elements. While the "Opt-Eval" variation introduces some additional noise, the overall gains in storage efficiency are substantial. Future work will focus on integrating these improvements into Fully Homomorphic Encryption (FHE) via efficient bootstrapping.
Summary updated