Efficient Homomorphic Integer Computer from CKKS
This talk introduces Discrete CKKS, a framework that extends the approximate FHE scheme CKKS to support exact integer arithmetic. It achieves this through a hybrid bootstrapping technique that both cleans noise and raises the modulus, enabling a high-throughput, vectorized engine for general-purpose discrete computations on encrypted data.
Fully Homomorphic Encryption (FHE) is a privacy-enhancing technology that allows for arbitrary computations on encrypted data without requiring interaction, offering strong cryptographic confidentiality. While powerful, its primary drawback is performance, with computations often being three to four orders of magnitude slower than on plaintext. FHE is maturing and seeing real-world deployment in applications like Apple’s privacy-preserving visual search and in providing confidentiality for blockchain transactions.
The Evolution of FHE Schemes
Since Gentry’s foundational work in 2009, FHE has branched into several families of schemes, each with different strengths:
- BGV/BFV: These schemes perform vectorized operations over finite fields (i.e., exact modular arithmetic).
- TFHE: This family is optimized for fast, bit-wise operations on individual ciphertexts and features a rapid “programmable” bootstrapping mechanism.
- CKKS: A popular scheme that performs vectorized, approximate arithmetic over real/complex numbers. Its natural alignment with the mathematics of machine learning has led to its wide adoption in that domain.
The focus of this work is on a recent development that bridges the gap between approximate and exact computation within the CKKS framework.
The Core Challenge: Managing Noise in FHE
At a high level, lattice-based FHE can be understood as performing arithmetic on noisy integers. Every multiplication operation accumulates additional noise, which, if left unchecked, will eventually corrupt the underlying message and render the ciphertext undecryptable. The central challenge in FHE is to manage this noise growth.
BFV: Separating Message and Error
The BFV approach handles noise by cleanly separating the message from the error. The message is encoded into the most significant bits (MSB) of a large integer, while the noise resides in the least significant bits (LSB).
- Computation: During multiplication, the noise term grows, but as long as it doesn’t “overflow” into the MSB, the message remains intact.
- Bootstrapping: This is a bounded system; after a certain number of operations, the noise must be reduced. BFV bootstrapping is a homomorphic operation that reduces the noise by effectively extracting the MSB of the noisy integer, resulting in a “fresh” ciphertext with the same message but minimal noise.
CKKS: Living with Error
The CKKS scheme, designed for approximate arithmetic, takes a different approach. It encodes the message (a real number) and the error together in the least significant bits.
- Computation: This model resembles fixed-point arithmetic. With each multiplication, the available space for the message (the modulus) shrinks, effectively reducing precision.
- Bootstrapping: Like BFV, this is also a bounded system. CKKS bootstrapping is a homomorphic operation that raises the modulus, extending the available space and allowing for further computations.
Discrete CKKS: A Hybrid for Exact Computation
Discrete CKKS is a novel framework that combines principles from both BFV and CKKS to enable exact, discrete computation using the efficient CKKS structure. It can be seen as a hybrid where the message is located between the LSB and MSB, maintaining a clear separation from the error (like BFV) while operating within the CKKS paradigm.
The key innovation is a new discrete bootstrapping technique that accomplishes two goals simultaneously:
- Noise Cleaning: It reduces the noise associated with the message, similar to BFV bootstrapping. This is achieved by homomorphically evaluating a real-valued function (e.g.,
f(x) = 3x² - 2x³) which has fixed points (e.g., at 0 and 1) with vanishing derivatives. This property causes values already close to the fixed points to become even closer, effectively “cleaning” the message. - Modulus Raising: It simultaneously raises the modulus, just like standard CKKS bootstrapping, to restore computational capacity.
Programmable Bootstrapping and Performance
A powerful feature of Discrete CKKS bootstrapping is that it can evaluate an arbitrary function on the encrypted message “for free” during the refresh process. This is analogous to the programmable bootstrapping in TFHE but has the significant advantage of being vectorized.
This enables the creation of a general-purpose arithmetic logic unit (ALU) for encrypted data. By representing large integers as a series of smaller, 8-bit chunks, one can perform arbitrary-precision integer arithmetic.
When compared to bit-wise FHE schemes like TFHE:
- Amortized Latency (Throughput): Discrete CKKS is two to three orders of magnitude better due to its vectorized nature, similar to the difference between a GPU and a CPU. It can pack many messages into a single ciphertext and operate on them in parallel.
- Latency: While latency for a single operation has historically been higher, recent developments are closing this gap.
This framework is particularly well-suited for applications like quantized machine learning, where it can provide efficient conversions between the approximate numbers of standard CKKS and the small integers used in quantized models.