Floating-Point Homomorphic Encryption

Jung Hee Cheon, Andrey Kim, Miran Kim, Yong Soo SongIACR ePrint 2016

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.

The Rescaling (RS) procedure in the CKKS scheme.

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

BibTeX
@article{cheon2016floating,
  author = {Jung Hee Cheon and Andrey Kim and Miran Kim and Yong Soo Song},
  title = {{Floating-Point Homomorphic Encryption}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2016},
}
Figure