Part 6: CKKS Scheme | Building Blocks of FHE

The CKKS (Cheon-Kim-Kim-Song) encryption scheme represents a significant improvement in FHE’s academic journey. Like its counterparts BFV and BGV, CKKS is built on the concept of Fully Homomorphic Encryption (FHE), enabling computations on encrypted data without decryption. CKKS’s main ability is to handle approximate arithmetic, making it particularly suitable for applications requiring operations on real or complex numbers. This scheme is quite helpful for privacy-preserving machine learning, secure data analysis, and other scenarios where maintaining confidentiality during computation on real numbers is important.

Plaintext and Ciphertext Rings

The plaintext ring $P$ and the ciphertext ring $C$ is usually the same and it is:$P$ and the ciphertext ring $C$ is usually the same and it is:

$$ R_q = Z_q[x]/f(x) $$

where $f(x)$ is in the form of $x^n + 1$ with $n$ is a power-of-2. Even though plaintext and ciphertext rings are the same, their formats are not.$f(x)$ is in the form of $x^n + 1$ with $n$ is a power-of-2. Even though plaintext and ciphertext rings are the same, their formats are not.

Similar to BFV/BGV, while a plaintext is represented by a single polynomial, a corresponding ciphertext is represented by a pair of two polynomials. So: 

$$ m \in R_q = Z_q[x]/(x^n + 1) $$

$$ c = (c_0, c_1) \in R_q^2 = Z_q^2[x]/(x^n + 1) $$

Message Encoding and Decoding

Encoding

Encoding in CKKS involves transforming a vector of complex numbers (they represent raw messages) into a polynomial that can be processed homomorphically. This process leverages the properties of the canonical embedding, which maps complex numbers to elements of a polynomial ring.

To encode a message, a vector of complex numbers $ (z_0, z_1, \ldots, z_{n/2-1}) $ is first scaled by a factor $ \Delta $, a large integer chosen to balance precision and noise growth. Each complex number $ z_i $ is then mapped to a polynomial using roots of unity. The real and imaginary parts of each complex number are distributed among the coefficients of the polynomial. This step ensures that the structure of the original message is preserved and can be recovered later. For example, given a message vector $ (1 + 4i, 5 - 2i) $ with a scaling factor $ \Delta = 100 $, the encoded polynomial might look like $ 300 + 71x + 100x^2 + 354x^3 $, where the coefficients represent the scaled real and imaginary parts embedded into the polynomial. $ (z_0, z_1, \ldots, z_{n/2-1}) $ is first scaled by a factor $ \Delta $, a large integer chosen to balance precision and noise growth. Each complex number $ z_i $ is then mapped to a polynomial using roots of unity. The real and imaginary parts of each complex number are distributed among the coefficients of the polynomial. This step ensures that the structure of the original message is preserved and can be recovered later. For example, given a message vector $ (1 + 4i, 5 - 2i) $ with a scaling factor $ \Delta = 100 $, the encoded polynomial might look like $ 300 + 71x + 100x^2 + 354x^3 $, where the coefficients represent the scaled real and imaginary parts embedded into the polynomial.

Decoding

Decoding in CKKS is the inverse process, where a polynomial is transformed back into a vector of complex numbers. After performing homomorphic operations on encrypted data, the resulting ciphertext is decrypted to obtain a polynomial in the plaintext space. This polynomial, which has been modified through the operations, needs to be decoded to retrieve the original or transformed message in a comprehensible form.

To decode, the polynomial coefficients are first rescaled by the factor $ 1/ \Delta $ to reverse the initial scaling. The canonical embedding is then applied in reverse, using roots of unity to map the polynomial back into the complex vector space. This process reconstructs the approximate complex numbers, which might have slight precision loss due to the nature of approximate arithmetic in CKKS. For instance, the polynomial $ 300 + 71x + 100x^2 + 354x^3 $ would be rescaled and decoded to retrieve the vector $ (1 + 4i, 5 - 2i) $ or an approximation thereof, recovering the original message with the modifications introduced by homomorphic operations. The precision and accuracy of the decoded message depend on the chosen scaling factor and the operations performed on the encrypted data. $ 1/ \Delta $ to reverse the initial scaling. The canonical embedding is then applied in reverse, using roots of unity to map the polynomial back into the complex vector space. This process reconstructs the approximate complex numbers, which might have slight precision loss due to the nature of approximate arithmetic in CKKS. For instance, the polynomial $ 300 + 71x + 100x^2 + 354x^3 $ would be rescaled and decoded to retrieve the vector $ (1 + 4i, 5 - 2i) $ or an approximation thereof, recovering the original message with the modifications introduced by homomorphic operations. The precision and accuracy of the decoded message depend on the chosen scaling factor and the operations performed on the encrypted data.

Fundamentals

Recall that BFV was a scale-invariant scheme. On the other hand, CKKS is a scale-variant one. But, what does this mean?

It means that the scheme will have a different modulus $q$ at each level. For instance, when we perform a homomorphic computation on a ciphertext, the ciphertext rescales itself down by the scaling factor $\Delta$. So as we perform operations, the modulus becomes $q_l/\Delta$. $q$ at each level. For instance, when we perform a homomorphic computation on a ciphertext, the ciphertext rescales itself down by the scaling factor $\Delta$. So as we perform operations, the modulus becomes $q_l/\Delta$.

So our moduli is an ordered set:

$q_1 < q_2 < \ldots < q_{L-1} < q_L$ where $q_L$ is the modulus of a pure ciphertext with no computation.

Key Generation

We first take a random $sk \in R_q$, usually with small coefficients like {-1, 0, 1}. $sk$ here is the secret key. $sk$ here is the secret key.

Then we derive the public key pair $(pk_1, pk_2)$ from the secret key $sk$: $(pk_1, pk_2)$ from the secret key $sk$:

$$ pk_1 = -a \cdot sk + \epsilon (mod q_L) $$

$$ pk_2 = a $$

where $a \in R_qL$ and the noise $\epsilon$ is randomly taken from an error distribution.

Encryption and Decryption

As we noted above, CKKS ciphertexts are represented by a pair of two components, $c = (c_1, c_2) \in R_q^2$. To encrypt a plaintext polynomial $m$, we sample 3 small random polynomials $u, \epsilon_1, \epsilon_2$ and we obtain:

$$ c_1 = pk_1 \cdot u + \epsilon_1 + m (mod q_l) $$

$$ c_2 = pk_2 \cdot u + \epsilon_2 (mod q_l) $$

So, $ Enc(m) = (c_1, c_2) = (pk_1 \cdot u + \epsilon_1 + m (mod q_l), pk_2 \cdot u + \epsilon_2 (mod q_l)) $

To decrypt $Enc(m) = (c_1, c_2)$, we perform the following computation:

$$ Dec(Enc(m)) = Dec((c_1, c_2)) = c_1 + c_2 \cdot sk (mod q_l) $$

Let’s see if it works! By the most fundamental principle of cryptography, our scheme must hold the following equality: $Dec(Enc(m)) = m$.

$$ Dec(Enc(m)) = c_1 + c_2 \cdot sk (modq_l) $$

$$ Dec(Enc(m)) = (pk_1 \cdot u + \epsilon_1 + m) + (pk_2 \cdot u + \epsilon_2) \cdot sk (mod q_l) $$

$$ Dec(Enc(m)) = -a \cdot sk \cdot u + \epsilon \cdot u + \epsilon_1 + m + (a \cdot sk \cdot u + \epsilon_2) \cdot sk $$

 $$ Dec(Enc(m)) = m + \epsilon \cdot u + \epsilon_1 + \epsilon_2 \cdot sk $$

$$ Dec(Enc(m)) \approx m $$

as all $$sk, u, \epsilon, \epsilon_1, \epsilon_2$$ polynomials are small.

Homomorphic Computations

Addition

Homomorphic addition combines two ciphertexts $C^{(1)}$ and $C^{(2)}$, defined with respect to the same modulus $q_l$, and produces a new ciphertext $C^{(3)}$ that encrypts the sum of the two plaintext messages. If the underlying ciphertexts are not at the same level, we need to scale down the one with higher level. Specifically, the decryption of $C^{(3)}$ using the secret key $sk$ yields $M^{(1)} + M^{(2)} \mod t$, provided the error in the resulting ciphertext is within acceptable bounds. This process involves simply adding the corresponding polynomials in each ciphertext.

$$ \text{Add}(C^{(1)}, C^{(2)}) = \left((C^{(1)}_1 + C^{(2)}_1 \mod q_l), (C^{(1)}_2 + C^{(2)}_2 \mod q_l)\right) = (C^{(3)}_1, C^{(3)}_2) = C^{(3)} $$

We have already covered why this works in the previous article. You can take a look if you want to check it out.

Multiplication

Multiplication is also quite similar to BFV, and you can see how derivation proceeds by visiting the previous article.

An important point to remember is that the resulting polynomial needs 3 polynomials to be represented, instead of 2.

$$ Mul(C^{(1)}, C^{(2)}) = (C_1^{(1)} + C_1^{(2)} mod q_l), (C_2^{(1)} + C_2^{(2)} mod q_l)) $$

$$ Mul(C^{1}, C^{2}) = (C_1^{(3)}, C_2^{(3)}) = C^{(3)} $$

To reduce the number of polynomials, we apply a procedure called rescaling. It is quite similar to modulus switching in BFV/BGV.

Rescaling

Our goal in rescaling is to reduce the scaling factor $\Delta$ after a multiplication. Simply put, we’ll provide a ciphertext $C = (C_1, C_2) \in R_{q_{l+1}}^2$ to be rescaled and the output will be a new ciphertext $C' = (C'_1, C'_2) \in R_{q_{l}}^2$.

It is worth noting that both $C$ and $C'$ must encrypt the same plaintext. The procedure is simply as follows:

$$ (C'_1, C'_2) mod q_l = \frac{1}{\Delta} \cdot (C_1, C_2) mod q_{l+1} $$

Conclusion

In this article, we have covered the fundamentals of the CKKS scheme: message encoding, key generation, plaintext encryption, ciphertext decryption, homomorphic computations, and the rescaling procedure.

In the next article, we will discuss the TFHE (Fast Fully Homomorphic Encryption over the Torus) scheme.