Key generation, encryption, and decryption

Behind the scenes, the CKKS pipeline has more pieces than just encrypt, compute, and decrypt. Because encryption operates on polynomials rather than vectors, the client also runs encoding and decoding steps that bracket the standard encrypt/decrypt loop. After a one-time key generation step, the end-to-end pipeline looks like this:

As a reminder from Section 3.1, we've fixed a ring dimension of $65536$, a chain of primes $q_0, q_1, \ldots, q_{17}$ with $q_0 \approx 2^{55}$ and $q_1 \approx \cdots \approx q_{17} \approx 2^{40}$, and the polynomial rings $R_\ell = \bigl(\mathbb{Z}/(q_0 \cdots q_\ell)\mathbb{Z}\bigr)[X]/(X^{65536} + 1)$ and $R_\infty = \mathbb{Z}[X]/(X^{65536} + 1)$.

Encoding vectors

The encoding step converts a plaintext vector in $\mathbb{C}^{32768}$ into a plaintext polynomial in $R_\ell$, since encryption operates on polynomials, not vectors. Plaintext polynomials carry two pieces of metadata: a level $\ell \in \{0, 1, \ldots, 17\}$ and a scale factor $\Delta_\ell$ that depends on the level but is always very close to $2^{40}$. The scale factor is determined by the recurrence

The polynomial itself is an element $m(X) \in R_\ell$, where the modulus is $q = q_0 q_1 \cdots q_\ell \approx 2^{55 + 40\ell}$.

To encode a vector $\mathbf{v} = (v_0, v_1, \ldots, v_{32767}) \in \mathbb{C}^{32768}$ as a plaintext polynomial:

1. Find the unique real polynomial $P(X) \in \mathbb{R}[X]/(X^{65536} + 1)$ such that $$ P(\zeta) = v_0, \quad P(\zeta^5) = v_1, \quad P(\zeta^{25}) = v_2, \quad \ldots, \quad P(\zeta^{5^{32767}}) = v_{32767}, $$ where $\zeta = e^{2\pi i / 131072}$ is a primitive $131072$-th root of unity. (This complex $\zeta$ is unrelated to the primitive $131072$-th root of unity in $\mathbb{Z}/(q_0 \cdots q_{17})\mathbb{Z}$ that appears in Section 3.1.)
   Exercise: convince yourself such a $P$ exists and is unique. (You'll need the fact that $\{-1, 5\}$ generates $(\mathbb{Z}/131072\mathbb{Z})^\times$.) Then show how to compute the coefficients of $P$ efficiently using a modification of the inverse Fast Fourier Transform.
2. Multiply every coefficient of $P(X)$ by $\Delta_\ell$ and round to the nearest integer.
3. Reinterpret the resulting integer coefficients modulo $q$ to obtain $m(X) \in R_\ell$.

To decode a plaintext polynomial $m(X)$, lift each coefficient from $\mathbb{Z}/q\mathbb{Z}$ to its balanced representative in $\left\{ -\frac{q-1}{2}, \ldots, \frac{q-1}{2} \right\}$, evaluate the resulting polynomial at $\zeta, \zeta^5, \zeta^{25}, \ldots, \zeta^{5^{32767}}$, and divide by $\Delta_\ell$.

Three things to keep in mind:

1. The encoding introduces noise. The rounding step means every entry of the recovered vector picks up an error on the order of $\Delta_\ell^{-1} \approx 2^{-40}$.
2. Vector entries can't be arbitrarily large. If any coefficient of $\Delta_\ell \cdot P(X)$ exceeds $q/2$ in magnitude, the reduction modulo $q$ can no longer be inverted, and the original $P(X)$ is unrecoverable. A safe bound that guarantees no overflow is $|v_i| \le \frac{1}{2} \cdot \frac{q_0}{\Delta_0} \approx 2^{14} = 16384$ for every $i$.
   Exercise: why is $\frac{1}{2} \cdot \frac{q_0}{\Delta_0}$ a safe bound?
3. The lifted coefficients of $m(X)$ should be small. This is another way to think about point 2 above: corruption happens when encrypted computations lead to overflow of the underlying plaintext polynomial coefficients. Specifically, the lifted coefficients of $m(X)$ should not exceed $q_0 / 2$ in magnitude; a plaintext polynomial whose coefficients fail this check at decode time is corrupted and cannot be meaningfully decoded. (It's possible for a plaintext polynomial to pass this check and still be corrupted; e.g., a level-0 plaintext polynomial that was the encryption of a vector with very large entries.)

Key generation

Before encrypting anything, we need to generate a key set, which consists of a secret key and a public key.

The secret key is a polynomial $s(X) \in R_\infty$ with coefficients in $\{-1, 0, 1\}$. It is chosen uniformly at random from the set of all such polynomials with exactly $512$ coefficients equal to $+1$ and exactly $512$ equal to $-1$ (the remaining $64512$ coefficients are zero). The number of nonzero coefficients of $s$ is called its Hamming weight, which for this $s$ is $h = 1024$.

The public key is a pair of polynomials $(a(X), b(X)) \in R_{17} \times R_{17}$, generated from $s(X)$ as follows:

1. Sample $b(X)$ uniformly at random from $R_{17}$.
2. Sample an error polynomial $e(X) \in R_\infty$ whose coefficients are drawn independently from a discrete Gaussian with standard deviation $3.2$.
3. Set $a(X) = -b(X)\, s(X) + e(X)$.

Encrypting plaintext polynomials

Ciphertexts, like plaintexts, carry two pieces of metadata: a level $\ell$ and a scale factor $\Delta_\ell$. Both are preserved by encryption and decryption, and they always match the level and scale factor of the underlying plaintext polynomial.

A level-$\ell$ ciphertext is a pair of polynomials $(c_0(X), c_1(X)) \in R_\ell \times R_\ell$. To encrypt a level-$\ell$ plaintext polynomial $m(X)$:

1. Sample a small mask $v(X) \in R_\infty$ and two error polynomials $e_0(X), e_1(X) \in R_\infty$, all with coefficients drawn independently from a discrete Gaussian of standard deviation $3.2$.
2. Compute $$ \begin{aligned} c_0(X) &= v(X)\, a(X) + m(X) + e_0(X), \\ c_1(X) &= v(X)\, b(X) + e_1(X). \end{aligned} $$

To decrypt a ciphertext $(c_0(X), c_1(X))$ using the secret key $s(X)$, simply compute $c_0(X) + c_1(X)\, s(X)$. Substituting the definitions:

The residual term $v\, e + e_0 + e_1\, s$ contributes only an $O(1)$ error to each coefficient of $m(X)$, small enough that dividing by $\Delta_\ell$ during decoding wipes it out.

The RLWE assumption

The security of CKKS rests on a single hardness assumption, the Ring Learning With Errors (RLWE) assumption. It's what makes recovering the secret key from the public key, or the plaintext from a ciphertext, computationally infeasible.

Roughly stated: fix a level $\ell$ and a secret polynomial $s(X) \in R_\infty$. Consider two ways of producing a pair $(a(X), b(X)) \in R_\ell \times R_\ell$:

• Distribution A. Sample $b(X)$ uniformly at random from $R_\ell$. Sample $e(X) \in R_\infty$ from a discrete Gaussian with standard deviation $3.2$. Set $a(X) = b(X)\, s(X) + e(X)$.
• Distribution B. Sample $a(X)$ and $b(X)$ independently and uniformly at random from $R_\ell$.

The RLWE assumption says that Distribution A and Distribution B are computationally indistinguishable: no efficient algorithm can tell, given a set of $(a(X), b(X))$, which procedure produced it. From this, it follows that the secret key cannot be recovered from the public key, and the plaintext cannot be recovered from a ciphertext.

For more on this assumption and the attacks against it, see Part 5.