D-3.10 Contemplation on CKKS Encoding

Why CKKS’s Encoding Uses the $(𝛍=2𝐧)$-th Cyclotomic Polynomial: At this point, it becomes clear why the CKKS encoding and decoding scheme uses the (power-of-2)-th cyclotomic polynomial (i.e., $X^n+1$) over $X\in ℂ$ (complex numbers) (§D-3.1). The first reason is that CKKS’s first requirement for designing a valid encoding and decoding formula for an input complex vector is to isomorphically convert it into a unique real number vector (and we scale this real number vector as an integer vector and use it as a list of coefficients for polynomial encoding, because CKKS’s homomorphic encryption and decryption are supported only based on polynomials with integer coefficients). As for the decoding formula of an input complex vector, our high-level idea was to treat the encoded real number vector as coefficients of an $(n-1)$-degree polynomial and evaluate this polynomial at $n$ distinct $X$ coordinates, whose resulting set of $n$ distinct $Y$ values is guaranteed to be unique within the $n$-th degree polynomial ring. Based on this insight, we designed a decoding matrix (§D-3.1) in the form of a Vandermonde matrix (§A-10.2). Then, the encoding formula is equivalent to multiplying the input complex vector by the inverse of this decoding matrix. However, in linear algebra, not all matrices are guaranteed to have a counterpart inverse matrix. Therefore, for the guarantee of the existence of a valid encoding matrix (i.e., an inverse of the decoding matrix), we leveraged the following arithmetic property: if a Vandermonde matrix $V=\mathrm{𝑉𝑎𝑛𝑑𝑒𝑟}(x_0,x_1,\cdots ,x_{n-1})$ is made of $n$ distinct primitive $(\mu =2n)$-th roots of unity (where $n$ is a power of 2), then such a Vandermonde matrix is guaranteed to have an inverse (§A-11.4) counterpart. In fact, the $(\mu =2n)$-th roots of unity are $n$ distinct roots of the $(\mu =2n)$-th cyclotomic polynomial: $X^n+1$ (§A-8.1). Therefore, CKKS uses $X^n+1$ as the polynomial ring of its subsequent encryption and decryption scheme (§D-3.2) as well.

The CKKS encoding’s second reason for using the $(\mu =2n)$-th cyclotomic polynomial is to design a valid input vector slot rotation scheme (§D-3.9). In this rotation scheme, updating the encoded polynomial $M(X)$ to $M(X^{J(h)})$ (where $J(h)=5^{h}mod2n$) is equivalent to updating the CKKS decoding process’s each evaluation coordinate of $M(X)$ from $x_i$ to $x_i^{J(h)}$ (where each $x_i$ is the primitive $(\mu =2n)$-th roots of unity), which gives the same effect as vertically rotating the encoding matrix (i.e., the inverse of the Vandermonde matrix whose roots are the primitive $(\mu =2n)$-th roots of unity) upward by $h$ positions. And this vertical rotation of the encoding matrix (while the input vector is fixed) gives the same effect of rotating the input vector $\overrightarrow{v}$ by $h$ positions to the left (without modifying the encoding matrix). Therefore, the $(\mu =2n)$-th cyclotomic polynomial $X^2+1$ is an ideal tool to design input vector slot rotation.