CKKS Scheme

Unlike exact schemes like BFV, CKKS natively operates on approximate real numbers by treating plaintexts as scaled integers. It views a ciphertext as encoding a value with an inherent least significant bit error, similar to floating-point representations. This design choice is critical for machine learning, where operations like sigmoid or ReLU activations produce irrational numbers that cannot be represented exactly. The scheme accepts a small, controllable precision loss in exchange for the ability to perform polynomial approximations of non-linear functions efficiently.

CKKS manages noise through a unique operation called rescaling, which is the approximate analogue of modulus switching in exact schemes. After every homomorphic multiplication, the ciphertext modulus is divided by a scaling factor, truncating both the message and the accumulated noise. This maintains a stable scale and prevents exponential noise growth. The process is deeply integrated with the leveled structure of the scheme: each multiplication consumes one level, and the total multiplicative depth of a circuit must be known before encryption.

CKKS leverages the Chinese Remainder Theorem to pack up to thousands of plaintext values into a single ciphertext. This Single Instruction, Multiple Data (SIMD) packing enables component-wise addition and multiplication on encrypted vectors in parallel. For machine learning, this means an entire layer of neurons can be processed simultaneously, dramatically amortizing the computational cost. A single homomorphic multiplication can evaluate thousands of scalar multiplications at once, making batched encrypted inference highly efficient.

CKKS is typically deployed as a leveled scheme, meaning it can evaluate circuits of a predetermined multiplicative depth without the expensive bootstrapping operation. Each multiplication reduces the ciphertext's level, and once the level reaches zero, no further multiplications are possible. This requires the computation—such as the number of layers in a neural network—to be known in advance. The leveled approach avoids the massive computational overhead of bootstrapping, making CKKS the most performant choice for fixed-depth ML inference pipelines.

A homomorphic multiplication in CKKS increases the ciphertext size from two ring elements to three. Without intervention, subsequent multiplications would cause exponential growth, making computation infeasible. Relinearization is a key-switching procedure that reduces the ciphertext back to two elements after each multiplication. This operation uses a public evaluation key and is essential for maintaining compact ciphertexts and manageable computational overhead throughout deep circuits like convolutional neural networks.

CKKS natively supports only addition and multiplication on encrypted data. To evaluate non-linear activation functions like ReLU, sigmoid, or tanh, these must be replaced with low-degree polynomial approximations. Techniques like Chebyshev approximation or minimax optimization are used to find polynomials that closely match the target function over a specific input range. The degree of the polynomial directly determines the multiplicative depth consumed, creating a trade-off between approximation accuracy and computational cost.

The CKKS-specific operation that divides the ciphertext by a scaling factor after multiplication to maintain a stable scale and manage noise. It is analogous to truncating floating-point precision.

• Mechanism: Divides the ciphertext modulus and plaintext scale by a factor Δ after each multiplication.
• Purpose: Prevents the scale from growing exponentially with multiplicative depth.
• Impact: Consumes one 'level' from the modulus chain, limiting the total number of multiplications before bootstrapping is required.

The mathematical technique of replacing non-linear functions like sigmoid, ReLU, or softmax with low-degree polynomials, enabling their evaluation within CKKS which natively supports only addition and multiplication.

• Chebyshev polynomials are commonly used to minimize the maximum approximation error over an interval.
• Minimax approximation finds the polynomial with the smallest maximum absolute error.
• The degree of the polynomial directly impacts the multiplicative depth and thus the performance of the encrypted inference.

A technique that encodes multiple plaintext values into a single ciphertext using the Chinese Remainder Theorem, enabling parallel homomorphic operations and amortizing computational cost across data vectors.

• CKKS supports packing up to N/2 complex numbers into one ciphertext, where N is the ring dimension.
• Enables slot-wise addition and multiplication, processing entire vectors in a single instruction.
• Critical for achieving practical throughput in neural network inference where thousands of neurons must be evaluated simultaneously.

The finite amount of cryptographic noise a ciphertext can tolerate before decryption fails. Each homomorphic operation consumes a portion of this budget.

• Addition consumes a small, additive amount of noise.
• Multiplication consumes significantly more noise and causes quadratic growth.
• In CKKS, the noise budget is managed through rescaling and ultimately refreshed via bootstrapping when exhausted.
• Monitoring the remaining noise budget is essential for determining how many more operations can be performed.

A computationally intensive procedure that refreshes a ciphertext's noise budget by homomorphically evaluating the decryption circuit, enabling unlimited computation in fully homomorphic encryption.

• In CKKS, bootstrapping also performs a modulus raise to restore the ciphertext to the top of the modulus chain.
• It is the most expensive operation in FHE, often dominating the total computation time.
• Recent optimizations have reduced CKKS bootstrapping latency to under 1 second on modern hardware.

The process of evaluating a pre-trained machine learning model on encrypted input data to produce an encrypted prediction, ensuring the client's query remains private from the server hosting the model.

• CKKS is the preferred scheme for this application due to its native support for real-number arithmetic.
• The model must be converted to use only polynomial operations, replacing activations like ReLU with polynomial approximations.
• The server never sees the raw input, and the client never sees the model weights—only the encrypted result.