Fundamental operations

This section explains how the five fundamental ciphertext operations from Section 2.1 — addition, subtraction, plaintext–ciphertext multiplication, ciphertext–ciphertext multiplication, rotation, and conjugation — are combinations of the ten polynomial operations from Section 3.1. Several of these operations share two internal subroutines, level dropping and key switching, which are introduced in their own subsections below. The composite ciphertext operations — dot product, matrix multiplication, and polynomial evaluation — are covered in Section 3.4, and bootstrapping gets its own treatment in Section 3.5.

Three of these operations — ciphertext–ciphertext multiplication, conjugation, and rotation — each require a new public key generated alongside the key set from Section 3.2. These are the relinearization key, conjugation key, and rotation keys, introduced in their respective subsections below. In this section and future sections, the explicit $X$ will be dropped from polynomial names; for example, we'll write $s, a, b, c_0, c_1, m$ instead of $s(X), a(X), b(X), c_0(X), c_1(X), m(X)$.

Dropping levels

A level drop converts a level-$\ell$ ciphertext $(c_0, c_1) \in R_\ell \times R_\ell$ (with modulus $q = q_0 \cdots q_\ell$) into a level-$\ell'$ ciphertext $(c_0', c_1') \in R_{\ell'} \times R_{\ell'}$ (with modulus $q' = q_0 \cdots q_{\ell'}$) encrypting the same vector, where $\ell' < \ell$. This operation is purely internal; it's not exposed through the CKKS interface.

To implement level-dropping using the polynomial operations, one naive approach is to set $c_0' = c_0 \bmod q'$ and $c_1' = c_1 \bmod q'$. However, this doesn't work; the level-$\ell$ ciphertext encrypts the vector with scale factor $\Delta_\ell$, but the result is interpreted with scale factor $\Delta_{\ell'}$, so the resulting encrypted vector picks up a spurious multiplicative factor of $\Delta_\ell / \Delta_{\ell'}$. Even though that ratio is very close to $1$, errors can compound across many operations.

Exercise: it seems like reducing $c_0$ and $c_1$ modulo the smaller modulus $q'$ should destroy information about the underlying plaintext. Why does it not?

One fix is to first multiply $c_0$ and $c_1$ by $\mathrm{round}\bigl(q_{\ell'+1} \cdots q_\ell \cdot \Delta_{\ell'} / \Delta_\ell\bigr) \approx 2^{40(\ell - \ell')}$, then rescale from modulus $q$ to modulus $q'$. However, rescaling costs scale with the number of primes dropped, so it's cheaper to do almost all the work via modulus reduction (which is free) and rescale just once at the end:

$$ \begin{aligned} c_0' &= \underset{q_0 \cdots q_{\ell'+1} \,\to\, q_0 \cdots q_{\ell'}}{\mathrm{rescale}_{\mathrm{approx}}}\!\bigl(c \cdot (c_0 \bmod q_0 \cdots q_{\ell'+1})\bigr), \\ c_1' &= \underset{q_0 \cdots q_{\ell'+1} \,\to\, q_0 \cdots q_{\ell'}}{\mathrm{rescale}_{\mathrm{approx}}}\!\bigl(c \cdot (c_1 \bmod q_0 \cdots q_{\ell'+1})\bigr), \end{aligned} $$

where $c = \mathrm{round}\bigl(q_{\ell'+1} \cdot \Delta_{\ell'} / \Delta_\ell\bigr) \approx 2^{40}$. This reduces the cost to a single rescaling through one prime. The precision loss on each coefficient of the underlying plaintext is $O(1)$, so the loss in the decoded vector is on the order of $\Delta_\ell^{-1} \approx 2^{-40}$.

Exercise: work out where the $O(1)$ coefficient error comes from, and convince yourself that the decoded vector picks up an error on the order of $2^{-40}$.

Addition and subtraction

To add or subtract two ciphertexts $(c_0, c_1)$ and $(d_0, d_1)$ encrypting vectors $\mathbf{u}, \mathbf{v} \in \mathbb{C}^{32768}$, first make sure they are at the same level $\ell$ by level-dropping the higher one. Then the ciphertext

$$ (c_0 \pm d_0,\; c_1 \pm d_1) \in R_\ell \times R_\ell $$

encrypts $\mathbf{u} \pm \mathbf{v}$, with error at most the sum of the errors on the two inputs. To see why, note that plaintext polynomials are linear in the encoded vector: if $m$ encodes $\mathbf{u}$ and $n$ encodes $\mathbf{v}$, then $m \pm n$ encodes $\mathbf{u} \pm \mathbf{v}$. Decryption is also linear in the ciphertext, so adding the two pairs componentwise encrypts the sum of the underlying vectors.

Exercise: convince yourself that decryption is linear in the ciphertext.

Adding or subtracting a plaintext $m$ to a ciphertext $(c_0, c_1)$ is similar. First, re-encode the plaintext at the level $\ell$ of the ciphertext, if needed. Then, if $(c_0, c_1)$ encrypts $\mathbf{v} \in \mathbb{C}^{32768}$ and $m$ encodes $\mathbf{u} \in \mathbb{C}^{32768}$, the ciphertext

$$ (c_0 \pm m,\; c_1) \in R_\ell \times R_\ell $$

encrypts $\mathbf{v} \pm \mathbf{u}$.

Plaintext–ciphertext multiplication

To multiply a level-$\ell$ ciphertext $(c_0, c_1)$ by a plaintext $m$, first re-encode $m$ at level $\ell$ if needed. Then compute

$$ \begin{aligned} c_0' &= \underset{q_0 \cdots q_\ell \,\to\, q_0 \cdots q_{\ell - 1}}{\mathrm{rescale}_{\mathrm{approx}}}(m\, c_0), \\ c_1' &= \underset{q_0 \cdots q_\ell \,\to\, q_0 \cdots q_{\ell - 1}}{\mathrm{rescale}_{\mathrm{approx}}}(m\, c_1). \end{aligned} $$

The scale factors line up because $\Delta_\ell^{\,2} / q_\ell = \Delta_{\ell - 1}$ by construction: the product $m\, c_i$ has scale $\Delta_\ell^{\,2}$, and rescaling by $q_\ell$ brings it down to $\Delta_\ell^{\,2} / q_\ell = \Delta_{\ell - 1}$, exactly the scale factor of a level-$(\ell - 1)$ ciphertext.

The error on the result grows by at most a factor of $\|\mathbf{u}\|_\infty$, the largest-magnitude entry of the vector $\mathbf{u}$ encoded by $m$, and the ciphertext's level drops by one, except when the plaintext is a scalar integer $k$. In that case, no rescaling is needed: the result is simply $(k c_0,\, k c_1)$ at the original level, with error scaled by at most $|k|$.

Interlude: key-switching

The remaining ciphertext operations — multiplication, rotation, and conjugation — share a common subroutine: key-switching. Given a secret $s'$, a public key-switching key $\mathrm{ksk}_{s'}$ lets us take any polynomial $p \in R_\ell$ and produce a level-$\ell$ ciphertext $(k_0, k_1)$ that decrypts to $p\, s'$. All of the key-switching keys are generated at the same time as the secret key and public key from Section 3.2.

The key-switching key

Pick a decomposition parameter $d = 3$ and $d$ auxiliary primes $p_0, p_1, p_2 \approx 2^{60}$ that are $1$ modulo $131072$. Define the extended ring

$$ \tilde{R}_\ell = \bigl(\mathbb{Z}/(q_0 \cdots q_\ell\, p_0 p_1 p_2)\mathbb{Z}\bigr)[X]/(X^{65536} + 1). $$

Group the prime chain into $\lceil 18 / d \rceil = 6$ consecutive blocks of size $d = 3$: $G_0 = \{q_0, q_1, q_2\},\, G_1 = \{q_3, q_4, q_5\},\, \ldots,\, G_5 = \{q_{15}, q_{16}, q_{17}\}$. Write $Q_i = \prod_{q \in G_i} q$ for the product of primes in block $G_i$, so $Q_0 = q_0 q_1 q_2,\, Q_1 = q_3 q_4 q_5,\, \ldots,\, Q_5 = q_{15} q_{16} q_{17}$. For each block, let $u_i \in \mathbb{Z}/(q_0 \cdots q_{17})\mathbb{Z}$ be the element that is $1$ modulo each prime in $G_i$ and $0$ modulo each prime outside $G_i$. The key $\mathrm{ksk}_{s'}$ consists of $6$ pairs of polynomials $(a_0, b_0), (a_1, b_1), \ldots, (a_5, b_5) \in \tilde{R}_{17} \times \tilde{R}_{17}$, generated as follows:

Sample each $b_i$ uniformly at random from $\tilde{R}_{17}$.
Sample error polynomials $e_0, \ldots, e_5 \in R_\infty$ with coefficients drawn independently from a discrete Gaussian of standard deviation $3.2$.
Set $a_i = -b_i\, s + e_i + p_0 p_1 p_2\, s'\, u_i$ for $i = 0, 1, \ldots, 5$.

Intuitively, $(a_i, b_i)$ is an RLWE-style encryption of $p_0 p_1 p_2\, s'\, u_i$.

The key-switch

Given the key $\mathrm{ksk}_{s'}$ and an input polynomial $p \in R_\ell$, the key-switch produces a level-$\ell$ ciphertext encrypting $p\, s'$ in three steps. First, for each $i \in \{0, 1, \ldots, \lfloor \ell/3 \rfloor\}$, compute the lift

$$ p^{(i)} = \underset{Q_i \,\to\, q_0 \cdots q_\ell\, p_0 p_1 p_2}{\mathrm{modraise}_{\mathrm{approx}}}\!\bigl(p \bmod Q_i\bigr), $$

which lives in $\tilde{R}_\ell$. Then define

$$ \begin{aligned} \tilde k_0 &= \displaystyle\sum_{i=0}^{\lfloor \ell/3 \rfloor} p^{(i)}\, (a_i \bmod q_0 \cdots q_\ell\, p_0 p_1 p_2) \in \tilde{R}_\ell, \\ \tilde k_1 &= \displaystyle\sum_{i=0}^{\lfloor \ell/3 \rfloor} p^{(i)}\, (b_i \bmod q_0 \cdots q_\ell\, p_0 p_1 p_2) \in \tilde{R}_\ell. \end{aligned} $$

The pair $(\tilde k_0, \tilde k_1)$ is an encryption of $p_0 p_1 p_2\, p\, s'$ in $\tilde{R}_\ell$:

$$ \begin{aligned} \tilde k_0 + \tilde k_1\, s &= \textstyle\sum_i p^{(i)} (a_i + b_i\, s) \\ &= \textstyle\sum_i p^{(i)} \bigl(e_i + p_0 p_1 p_2\, s'\, u_i\bigr) \\ &= \textstyle\sum_i p^{(i)}\, e_i \;+\; p_0 p_1 p_2\, s' \textstyle\sum_i p^{(i)}\, u_i \\ &\approx p_0 p_1 p_2\, p\, s', \end{aligned} $$

where the last step uses $\sum_i p^{(i)}\, u_i \equiv p \pmod{q_0 \cdots q_\ell}$. Finally, rescale away the auxiliary primes to drop the factor of $p_0 p_1 p_2$:

$$ \begin{aligned} k_0 &= \underset{q_0 \cdots q_\ell\, p_0 p_1 p_2 \,\to\, q_0 \cdots q_\ell}{\mathrm{rescale}_{\mathrm{approx}}}(\tilde k_0), \\ k_1 &= \underset{q_0 \cdots q_\ell\, p_0 p_1 p_2 \,\to\, q_0 \cdots q_\ell}{\mathrm{rescale}_{\mathrm{approx}}}(\tilde k_1). \end{aligned} $$

Then $(k_0, k_1)$ is a level-$\ell$ encryption of $p\, s'$.

Exercise: explain why an arbitrary lift of $p \bmod Q_i$ to $\tilde{R}_\ell$ does not work for correctness, while the approximate modulus raising does work.

Exercise: what changes if $d = 2$?

Exercise: there is a lot of flexibility in the choice of $p_0, \ldots, p_{d-1}$. However, their product should always be at least $2^{40 d}$; explain why.

Ciphertext–ciphertext multiplication

To multiply two ciphertexts $(c_0, c_1)$ and $(d_0, d_1)$ encrypting plaintext polynomials $m$ and $n$, first level-drop the higher one, if necessary, so that both are at the same level $\ell$. Then define

$$ c_0' = c_0\, d_0, \qquad c_1' = c_0\, d_1 + c_1\, d_0, \qquad c_2' = c_1\, d_1. $$

Given the secret key $s$, a decryptor could recover the product $mn$ from the triple $(c_0', c_1', c_2')$ by computing

$$ \begin{aligned} c_0' + c_1'\, s + c_2'\, s^2 &= (c_0 + c_1\, s)(d_0 + d_1\, s) \\ &\approx (m + O(1))(n + O(1)) \\ &= m n + O(2^{40}), \end{aligned} $$

which is an approximation of $mn$ with relative error $O(2^{-40})$. And if $m$ encodes $\mathbf{u}$ and $n$ encodes $\mathbf{v}$, then $m n$ encodes $\Delta_\ell\, \mathbf{u} \odot \mathbf{v}$ with $O(1)$ coefficient error, so rescaling away one prime produces a plaintext at level $\ell - 1$ encoding $\mathbf{u} \odot \mathbf{v}$ with error on the order of $2^{-40}$.

Exercise: show that if $m, n \in R_\ell$ encode vectors $\mathbf{u}, \mathbf{v}$ at scale $\Delta_\ell$, then $mn$ encodes $\Delta_\ell\, \mathbf{u} \odot \mathbf{v}$ with $O(1)$ coefficient error.

However, the triple $(c_0', c_1', c_2')$ isn't a ciphertext. To turn this into a ciphertext, the key idea is to fold the $c_2'\, s^2$ term into $(c_0', c_1')$ using the key-switching key $\mathrm{rlk} = \mathrm{ksk}_{s^2}$; this key is called the relinearization key.

Applying the key-switch to $c_2'$ with $\mathrm{rlk}$ yields a level-$\ell$ encryption $(k_0, k_1)$ of $c_2'\, s^2$. Adding this back into the pair $(c_0', c_1')$ and rescaling once more produces the final ciphertext:

$$ \begin{aligned} c_0'' &= \underset{q_0 \cdots q_\ell \,\to\, q_0 \cdots q_{\ell - 1}}{\mathrm{rescale}_{\mathrm{approx}}}(c_0' + k_0), \\ c_1'' &= \underset{q_0 \cdots q_\ell \,\to\, q_0 \cdots q_{\ell - 1}}{\mathrm{rescale}_{\mathrm{approx}}}(c_1' + k_1). \end{aligned} $$

The pair $(c_0'', c_1'') \in R_{\ell - 1} \times R_{\ell - 1}$ decrypts to $\underset{q_0 \cdots q_\ell \to q_0 \cdots q_{\ell - 1}}{\mathrm{rescale}_{\mathrm{approx}}}(mn)$, which encodes $\mathbf{u} \odot \mathbf{v}$ at level $\ell - 1$.

Rotation

To rotate a ciphertext $(c_0, c_1)$ encrypting a plaintext polynomial $m \in R_\ell$ by $i \in \{1, 2, \ldots, 32767\}$ slots, it suffices to obtain a ciphertext encrypting $\tau_{5^i}(m)$, where $\tau_j: R_\ell \to R_\ell$ is the automorphism $X \mapsto X^j$ from Section 3.1.

Exercise: show that if $m$ encodes the vector $(v_0, v_1, \ldots, v_{32767}) \in \mathbb{C}^{32768}$, then $\tau_{5^i}(m)$ encodes the cyclic shift $(v_i, v_{i+1}, \ldots, v_{32767}, v_0, v_1, \ldots, v_{i-1})$.

Define $c_0' = \tau_{5^i}(c_0)$ and $c_1' = \tau_{5^i}(c_1)$. Given the secret key $s$, a decryptor could recover $\tau_{5^i}(m)$ from the pair $(c_0', c_1')$ by computing

$$ c_0' + c_1'\, \tau_{5^i}(s) = \tau_{5^i}(c_0 + c_1\, s) \approx \tau_{5^i}(m). $$

However, the pair $(c_0', c_1')$ isn't a standard ciphertext under $s$. To turn it into one, the key idea is to fold the $c_1'\, \tau_{5^i}(s)$ term into $c_0'$ using the key-switching key $\mathrm{rot}_i = \mathrm{ksk}_{\tau_{5^i}(s)}$; this key is called a rotation key.

Applying the key-switch to $c_1'$ with $\mathrm{rot}_i$ yields a level-$\ell$ encryption $(k_0, k_1)$ of $c_1'\, \tau_{5^i}(s)$, and the ciphertext

$$ c_0'' = c_0' + k_0, \qquad c_1'' = k_1 $$

encrypts $\tau_{5^i}(m)$.

Remark: storing $\mathrm{rot}_i$ for every $i \in \{1, 2, \ldots, 32767\}$ would consume too much memory, so in practice only the rotation keys that are actually needed for a given computation are generated.

Exercise: compute the amount of memory that one rotation key takes up, in megabytes.

Conjugation

Pointwise conjugation follows the same pattern as rotation, but with the automorphism $\tau_{-1}$ from Section 3.1, mapping $X \mapsto X^{-1}$. The corresponding key-switching key $\mathrm{conj} = \mathrm{ksk}_{\tau_{-1}(s)}$ is called the conjugation key, and applying it to $\tau_{-1}(c_1)$ yields $(k_0, k_1)$ such that the ciphertext $\bigl(\tau_{-1}(c_0) + k_0,\; k_1\bigr)$ encrypts $\tau_{-1}(m)$.

Exercise: show that if $m$ encodes the vector $\mathbf{v} \in \mathbb{C}^{32768}$, then $\tau_{-1}(m)$ encodes its pointwise complex conjugate $\overline{\mathbf{v}}$.