D-3 CKKS Scheme

The CKKS scheme is designed for homomorphic addition and multiplication of complex numbers that contain imaginary numbers. Therefore, unlike BFV, GBV, or TFHE, which can only compute over integers, CKKS can compute real-world floating point arithmetic, such as machine learning.

The CKKS scheme’s goal is to homomorphically compute addition and multiplication of complex numbers. However, while our targeted inputs are complex numbers, CKKS’s plaintext space is defined as a $(n-1)$-degree polynomial ring with real-number coefficients having a limited precision, that is, $R_{⟨n⟩}=ℝ[x]∕(x^n+1)$. Therefore, CKKS designs its unique encoding scheme which converts the input complex numbers into integers which can be used as coefficients of a polynomial in $R_{⟨n⟩}$.

In overall, CKKS’s encryption procedure is as follows:

1.

Encoding₁: Encode the targeted input complex number into a real number

2.

Encoding₂: Encode the real number into an integer

3.

Encryption: Encrypt the integer by RLWE

The encrypted RLWE ciphertext supports homomorphic addition and multiplication.

At the end of all homomorphic operations, CKKS’s decryption procedure is as follows:

1.

Decryption: Decrypt the RLWE ciphertext into a plaintext integer

2.

Decoding₁: Decode the integer to a real number

3.

Decoding₂: Decode the real number to a complex number

Remember that BFV is an exact encryption scheme based on rings. On the other hand, CKKS introduces a drifting error while its encoding process of rounding square-root values (included in the Euler’s formula) to the nearest integer. Therefore, its decryption is not exactly the same as before encryption. Such a small error occurring during encryption and decryption makes CKKS an approximate encryption scheme.

CKKS internally uses the same schemes as BFV for encryption, decryption, ciphertext-to-plaintext addition, ciphertext-to-ciphertext addition, and ciphertext-to-plaintext multiplication. Meanwhile, CKKS uses slightly different schemes than BFV for encoding the input vector (i.e., input vector slots) rotation (if BFV uses the batch encoding scheme), ciphertext-to-ciphertext multiplication, and bootstrapping. This difference comes from the fact that CKKS handles homomorphic operations over complex numbers as inputs, whereas BFV handles homomorphic operations over rings.