D-3.12 Sparsely Packing Ciphertexts

In §D-3.1, we learned the CKKS encoding scheme, which encodes an input vector with ${\displaystyle \frac{n}{2}}$ slots (i.e., ${\displaystyle \frac{n}{2}}$-slot input vector) into an $(n-1)$-degree polynomial. While the polynomial ring’s degree $n$ is fixed at the setup stage of CKKS as a security parameter, some applications may only need to use fewer than ${\displaystyle \frac{n}{2}}$ input vector slots. Suppose we only need to use $\frac{n^{\prime }}{2}$ slots out of $\frac{n}{2}$ slots, where $n^{\prime }$ is some number that divides $n$. Then, the corresponding input vector and encoded polynomial acquire a special property as described below:

We could show both directions of proof: (1) the forward (decoding-direction) proof; and (2) the backward (encoding-direction) proof. However, it is sufficient to prove only either direction because the encoding (${\sigma }^{-1}$) and decoding ($\sigma$) processes are isomorphic. Among these two, we will show only the forward proof for simplicity.

D-3.12.1 Forward Proof: Decoding of Sparsely Packed Ciphertext

We will prove that for each $M_Y(Y)\in ℝ[Y]∕(Y^{n^{\prime }}+1)$ (i.e., a polynomial in $ℝ[X]∕(X^n+1)$ that has non-zero constants only at those terms with a power that is a multiple of ${\displaystyle \frac{n}{n^{\prime }}}$ and zero constants in all other terms), the polynomial is decoded into some ${\displaystyle \frac{n}{2}}$-slot input vector which comprises ${\displaystyle \frac{n}{n^{\prime }}}$ repetitions of the first ${\displaystyle \frac{n^{\prime }}{2}}$ consecutive slot values.

To decode $M(X)$ into an input vector, we need to evaluate $M(X)$ at $\frac{n}{2}$ distinct roots of $X^n+1$ (i.e., $n$ distinct primitive $(\mu =2n)$-th roots of unity), which are:

$(M({\omega }^{J(0)}),M({\omega }^{J(1)}),\cdots ,M({\omega }^{J(\frac{n}{2}-1)}))$

$▹$where $\omega =e^{\frac{\mathit{𝑖𝜋}}{n}}$, the base and generator of the primitive ($\mu =2n$)-th roots of unity

But since $M(X)=M_Y(X^{\frac{n}{n^{\prime }}})$, the above evaluation is equivalent to evaluating:

$(M_Y({({\omega }^{J(0)})}^{\frac{n}{n^{\prime }}}),M_Y({({\omega }^{J(1)})}^{\frac{n}{n^{\prime }}}),\cdots ,M_Y({({\omega }^{J(\frac{n}{2}-1)})}^{\frac{n}{n^{\prime }}}))$

$=(M_Y({({\omega }^{\frac{n}{n^{\prime }}})}^{J(0)}),M_Y({({\omega }^{\frac{n}{n^{\prime }}})}^{J(1)}),\cdots ,M_Y({({\omega }^{\frac{n}{n^{\prime }}})}^{J(\frac{n}{2}-1)}))$

$=(M_Y({\xi }^{J(0)}),M_Y({\xi }^{J(1)}),\cdots ,M_Y({\xi }^{J(\frac{n}{2}-1)}))$

$▹$where $\xi =e^{\frac{\mathit{𝑖𝜋}}{n^{\prime }}}$, the base and generator of the primitive $(\mu =2n^{\prime })$-th roots of unity

Notice that $\xi ={\omega }^{\frac{n}{n^{\prime }}}$. Therefore, the above evaluation of $M_Y(Y)$ outputs ${\displaystyle \frac{n}{n^{\prime }}}$ repeated values of $M_Y(Y)$ evaluated at $\frac{n^{\prime }}{2}$ distinct primitive $(\mu =2n^{\prime })$-th roots of unity.