Abstract
Traditional homomorphic encryption (HE) schemes are designed for exact integer arithmetic, where encryption noise is a barrier to be minimized. This paper introduces a paradigm shift by proposing a scheme optimized for approximate arithmetic, commonly known as the CKKS scheme. By treating encryption noise as part of the rounding error inherent in floating-point calculations and introducing a novel "rescaling" procedure, the authors achieve linear ciphertext growth. This enables the efficient evaluation of complex, real-world functions such as logistic regressions and signal processing tasks on encrypted data.
Introduction
Homomorphic Encryption (HE) allows computations to be performed directly on encrypted data. However, standard schemes like BGV or FV focus on exact arithmetic over finite fields. For real-world applications—such as medical data analysis or machine learning—data is often represented as approximate floating-point numbers. In these traditional schemes, managing noise is computationally expensive, and the bit-size of messages grows exponentially with the number of multiplications, necessitating massive and inefficient moduli.
Methodology
The CKKS scheme addresses these challenges through three primary innovations:
1. Noise as Rounding Error
Instead of viewing noise $e$ as a nuisance to be eliminated, the authors incorporate it into the message structure. Decryption is defined as $\langle c, sk \rangle = m + e \pmod q$, where $e$ is interpreted as the precision error of an approximate value $m' = m + e$.
2. The Rescaling Procedure
The "killer feature" of this scheme is the Rescale (RS) procedure. In standard HE, multiplication increases the magnitude of the plaintext. RS divides both the ciphertext and the modulus by a scaling factor $p$. This operation effectively shifts the decimal point and "rounds" the plaintext by removing the least significant bits (LSBs) that have become inaccurate due to noise.
3. Complex Packing
Using a canonical embedding map, the scheme packs vectors of complex numbers into single polynomials. This map is an isometry, ensuring that errors do not amplify during encoding and decoding, thereby preserving the precision of the underlying data.
Evaluation and Results
The scheme was evaluated using the HEAAN library across several functional benchmarks, including power functions, Taylor series expansions for transcendental functions (e.g., $exp(x)$, $1/x$, and logistic functions), and signal processing tasks like the Discrete Fourier Transform (DFT).
Key results include:
- Efficiency: A degree-7 Taylor polynomial for a logistic function was evaluated in 0.54 seconds, or 0.13 milliseconds per data slot with batching. This is orders of magnitude faster than previous exact-arithmetic HE approaches.
- High Depth: The scheme successfully computed $x^{1024}$ with 36-bit precision in under 8 seconds.
- Precision: The authors demonstrated that precision loss is nearly optimal, losing at most one bit more than unencrypted floating-point arithmetic.
Conclusion
The CKKS scheme represents a significant advancement in practical HE by moving from exponential to linear ciphertext growth relative to circuit depth. While the current "leveled" implementation requires a pre-defined modulus depth, it paves the way for efficient approximate computing. Future work remains in optimizing bootstrapping—the process of refreshing ciphertexts for infinite computation—within this approximate framework.
Summary updated