Polynomials

This section introduces the polynomial rings CKKS works over, the operations on them that CKKS needs, and how each operation is computed efficiently.

To start, let $N = 2^{16} = 65536$ be the ring dimension, and fix a chain of distinct primes $q_0, q_1, \ldots, q_{17}$, all congruent to $1$ modulo $2^{17} = 131072$, with $q_0 \approx 2^{55}$ and $q_1 \approx q_2 \approx \cdots \approx q_{17} \approx 2^{40}$. The rings we care about are

so $R_\ell$ is the polynomial ring at level $\ell \in \{0, 1, \ldots, 17\}$, and $R_\infty$ is the underlying integer-coefficient ring.

Everything in CKKS is built on top of polynomials in $R_\ell$ for $\ell \in \{0, 1, \ldots, 17\}$ (polynomials in $R_\infty$ are stored in the highest-level ring). Each such polynomial has two representations: coefficient form and evaluation form.

On top of these representations, CKKS uses ten operations on polynomials:

• Two operations convert between the two representations:
  • The number-theoretic transform (NTT) takes a polynomial $p \in R_\ell$ in coefficient form and returns the same polynomial in evaluation form.
  • The inverse number-theoretic transform (iNTT) takes a polynomial $p \in R_\ell$ in evaluation form and returns the same polynomial in coefficient form.
• Five operations keep polynomials in $R_\ell$:
  • Addition takes two polynomials $p_1, p_2 \in R_\ell$ and returns their sum $p_1 + p_2$.
  • Subtraction takes two polynomials $p_1, p_2 \in R_\ell$ and returns their difference $p_1 - p_2$.
  • Scalar multiplication takes a polynomial $p \in R_\ell$ and a scalar $k \in \mathbb{Z}$, and returns the product $k\, p$.
  • Polynomial multiplication takes two polynomials $p_1, p_2 \in R_\ell$ and returns their product $p_1 p_2$.
  • Automorphisms take a polynomial $p(X) \in R_\ell$ and an odd integer $i$, and return $p(X^i)$.
• Two operations drop the polynomial to a lower-level ring:
  • Modulus reduction takes a polynomial $p \in R_\ell$ and a target level $\ell' < \ell$, and returns the image of $p$ under the natural ring homomorphism $R_\ell \to R_{\ell'}$ that reduces each coefficient modulo $q_0 \cdots q_{\ell'}$.
  • Rescaling takes a polynomial $p \in R_\ell$ and a target level $\ell' < \ell$, and returns a polynomial in $R_{\ell'}$ whose coefficients are approximately $p$'s coefficients divided by $q_{\ell' + 1} \cdots q_\ell$.
• One operation raises the polynomial to a higher-level ring:
  • Modulus raising takes a polynomial $p \in R_\ell$ and a target level $\ell' > \ell$, and returns the polynomial in $R_{\ell'}$ obtained by lifting each coefficient of $p$ to its centered integer representative in $\left\{-\tfrac{q_0 \cdots q_\ell - 1}{2},\, \ldots,\, \tfrac{q_0 \cdots q_\ell - 1}{2}\right\}$ and reinterpreting it modulo $q_0 \cdots q_{\ell'}$.

Representing integers

Before describing the two representations of polynomials in $R_\ell$, we first need to describe how the underlying integers modulo $q_0 \cdots q_\ell$ are represented. An integer modulo $q_0 \cdots q_\ell$ is represented in residue number system (RNS) form: the RNS representation of $r \in \mathbb{Z}/(q_0 \cdots q_\ell)\mathbb{Z}$ is the tuple

The reason for using RNS form is twofold:

• Arithmetic is pointwise. Adding, subtracting, multiplying, or dividing two integers modulo $q_0 \cdots q_\ell$ in RNS form is just a componentwise application of the corresponding operation modulo each $q_i$.
• Each $q_i$ fits in a machine word. Every $q_i$ is less than $2^{64}$, so the operations map directly onto fast hardware instructions.

Representing polynomials

A polynomial in $R_\ell$ has two equivalent representations: coefficient form and evaluation form. Both store the polynomial as a tuple of $65536$ integers modulo $q_0 \cdots q_\ell$, each in RNS form; the two representations differ in what those integers mean.

Coefficient form

Lift $p(X) \in R_\ell$ to its unique representative $c_0 + c_1 X + \cdots + c_{65535} X^{65535}$ in $\bigl(\mathbb{Z}/(q_0 \cdots q_\ell)\mathbb{Z}\bigr)[X]$ of degree at most $65535$. The coefficient form of $p(X)$ is the tuple $(c_0, c_1, \ldots, c_{65535})$, with each $c_j \in \mathbb{Z}/(q_0 \cdots q_\ell)\mathbb{Z}$ represented in RNS form.

Evaluation form

Let $\zeta \in \mathbb{Z}/(q_0 \cdots q_{17})\mathbb{Z}$ be a fixed primitive $131072$-th root of unity — that is, a root of $X^{65536} + 1$.

The evaluation form of $p(X)$ is the tuple

with each $p(\zeta^{2i+1}) \in \mathbb{Z}/(q_0 \cdots q_\ell)\mathbb{Z}$ represented in RNS form. The evaluation $p(\zeta^{2i+1})$ is well-defined because $\zeta^{2i+1}$ is itself a root of $X^{65536} + 1$, so the value doesn't depend on which representative of $p(X)$ in $\bigl(\mathbb{Z}/(q_0 \cdots q_\ell)\mathbb{Z}\bigr)[X]$ we plug in. (When evaluating $p \in R_\ell$, $\zeta$ is implicitly reduced modulo $q_0 \cdots q_\ell$ first.)

The evaluation form map can be understood as the ring isomorphism $\varphi_\ell : R_\ell \to \bigl(\mathbb{Z}/(q_0 \cdots q_\ell)\mathbb{Z}\bigr)^{65536}$ given by $p(X) \mapsto \bigl(p(\zeta), p(\zeta^3), \ldots, p(\zeta^{131071})\bigr)$.

Number-theoretic transform

The negacyclic number-theoretic transform (NTT) converts a polynomial from coefficient form to evaluation form, and the inverse negacyclic number-theoretic transform (iNTT) converts back. The NTT is the matrix transformation

modulo $q_0 \cdots q_\ell$, and the iNTT is the matrix transformation

modulo $q_0 \cdots q_\ell$.

The NTT is, in essence, a discrete Fourier transform over a finite ring. The "negacyclic" qualifier is because the usual discrete Fourier transform is built from the roots of $X^N - 1$, whereas here we use the roots of $X^N + 1$.

Addition and subtraction

Adding or subtracting two polynomials in $R_\ell$ is componentwise, provided both inputs are in the same representation. If $(a_0, \ldots, a_{65535})$ and $(b_0, \ldots, b_{65535})$ are the tuples (in either coefficient or evaluation form), the sum and difference are

The output polynomial has the same representation as the input polynomials.

Scalar multiplication

Multiplying a polynomial $p(X) \in R_\ell$ by a scalar $k \in \mathbb{Z}$ is componentwise multiplication by $k$ in either representation: $(a_0, \ldots, a_{65535}) \mapsto (k\, a_0, \ldots, k\, a_{65535})$.

Polynomial multiplication

Multiplying two polynomials $a(X), b(X)$ in $R_\ell$ requires both inputs to be in evaluation form. Because $a(\zeta^i)\, b(\zeta^i) = (ab)(\zeta^i)$ for every odd integer $i$, the evaluation form of their product is the pointwise product of their evaluation forms.

If either input is in coefficient form, it must be converted to evaluation form via NTT first.

Automorphism

Given an odd integer $i$, the automorphism map is the map $\tau_i : R_\ell \to R_\ell$ given by $p(X) \mapsto p(X^i)$. The automorphism by $i$ can be computed efficiently in either representation.

In coefficient form. The image of $p(X) = c_0 + c_1 X + \cdots + c_{65535} X^{65535}$ is

Since $i$ is odd, the map $j \mapsto ij \bmod 65536$ is a permutation, so applying $\tau_i$ amounts to permuting the coefficient tuple and flipping the signs of some of its entries.

In evaluation form. Since

automorphism in evaluation form is the permutation of $\{0, 1, \ldots, 65535\}$ sending $j$ to $\bigl(i(2j+1) \bmod 131072 - 1\bigr)/2$.

Modulus reduction

Given a target level $\ell' < \ell$, the modulus reduction operation is the natural ring homomorphism

induced by reducing every coefficient modulo $q_0 \cdots q_{\ell'}$. In RNS form, this is essentially free: every integer modulo $q_0 \cdots q_\ell$ is already stored as the tuple $(r_0, r_1, \ldots, r_\ell)$, and its image modulo $q_0 \cdots q_{\ell'}$ is just the prefix $(r_0, r_1, \ldots, r_{\ell'})$. This applies in both coefficient and evaluation form.

Modulus raising

Given a target level $\ell' > \ell$, the modulus raising operation maps $R_\ell$ to $R_{\ell'}$ by lifting each coefficient to its centered integer representative and then reinterpreting modulo the larger product. Concretely, a polynomial $c_0 + c_1 X + \cdots + c_{65535} X^{65535} \in R_\ell$ with $-\tfrac{1}{2} q_0 \cdots q_\ell < c_0, c_1, \ldots, c_{65535} < \tfrac{1}{2} q_0 \cdots q_\ell$ maps to the same polynomial, now interpreted in $R_{\ell'}$. This map is not a ring homomorphism: there's no algebraic relationship between $R_\ell$ and $R_{\ell'}$ being preserved.

To modulus raise efficiently, the polynomial must be in coefficient form, since the algorithm works one coefficient at a time. Let $r$ be an integer modulo $q = q_0 \cdots q_\ell$ whose RNS form is $(r_0, r_1, \ldots, r_\ell)$, and we want the RNS components of $\underset{q_0 \cdots q_\ell \,\to\, q_0 \cdots q_{\ell'}}{\mathrm{modraise}}(r)$ at $q_j$ for each $j \in \{\ell + 1, \ldots, \ell'\}$. First, precompute the modular inverses

and the cross-residues

along with

Then, given $(r_0, \ldots, r_\ell)$, compute

and

By the Chinese remainder theorem,

so the centered representative of $r$ is

Therefore, for each new prime $q_j$ with $j > \ell$,

The RNS form of $\underset{q_0 \cdots q_\ell \,\to\, q_0 \cdots q_{\ell'}}{\mathrm{modraise}}(r)$ modulo $q_0 \cdots q_{\ell'}$ is then obtained by appending these new components to the original tuple $(r_0, \ldots, r_\ell)$.

Approximate modulus raising

In applications where the lifted coefficients need to be small but do not need to lie exactly in the range $-\tfrac{1}{2} q_0 \cdots q_\ell$ to $\tfrac{1}{2} q_0 \cdots q_\ell$, the carry $v$ can be skipped. The result then becomes

for each $j \in \{\ell + 1, \ldots, \ell'\}$. The result differs from the exact modulus raising by an integer multiple of $q_0 \cdots q_\ell$ of magnitude at most $\lfloor(\ell + 1)/2\rfloor\, q_0 \cdots q_\ell$.

Approximate rescaling

Given a target level $\ell' < \ell$, the rescaling operation maps $R_\ell$ to $R_{\ell'}$ by dividing every coefficient by $Q = q_{\ell'+1} \cdots q_\ell$ and rounding to the nearest integer:

The algorithm given in this subsection approximates the true rescaling operation; the result differs from the exact rescaling by an integer of magnitude at most $\lfloor(\ell - \ell')/2\rfloor$ per coefficient.

Remark: exact rescaling is also possible, using a carry computation analogous to the one in modulus raising, but it is not needed for CKKS: at every place rescaling is used, the approximate version suffices.

Like modulus raising, rescaling is not a ring homomorphism. However, it approximately preserves additive structure in the sense that

To rescale efficiently, the polynomial must be in coefficient form, since the algorithm works one coefficient at a time. Let $r$ be an integer modulo $q_0 \cdots q_\ell$ whose RNS form is $(r_0, r_1, \ldots, r_\ell)$; the goal is to get the RNS form of an integer within $\lfloor(\ell - \ell')/2\rfloor$ of $\mathrm{round}(r/Q)$ modulo $q_0 \cdots q_{\ell'}$. First, precompute the modular inverses

and the cross-residues

Then, given $(r_{\ell' + 1}, \ldots, r_\ell)$, compute

for each $i \in \{\ell' + 1, \ldots, \ell\}$. By the Chinese remainder theorem,

and as an integer the right-hand side satisfies

so it differs from $r$ by at most $\lfloor(\ell - \ell')/2\rfloor$ multiples of $Q$. The RNS component of the rescaled coefficient at $q_j$ is then

for $j \in \{0, 1, \ldots, \ell'\}$. Collecting these components over $j \in \{0, 1, \ldots, \ell'\}$ gives the RNS form of some number within $\lfloor(\ell - \ell')/2\rfloor$ of $\mathrm{round}(r/Q)$ modulo $q_0 \cdots q_{\ell'}$.