D-3.9 Homomorphic Rotation of Input Vector Slots

CKKS’s batch encoding scheme (Summary D-3.1 in §D-3.1) implicitly supports homomorphic rotation of input slot vectors like that of BFV’s homomorphic rotation (Summary D-2.9.3 in §D-2.9.3). This is because CKKS uses the same encoding and decoding matrices ($\tilde{W}$ and ${\tilde{W}}^{\ast }$) designed for the BFV encoding and decoding scheme that supports homomorphic rotation of input vector slots. Although the roots of the $(\mu =2n)$-th cyclotomic polynomial $X^n+1$ are different for the BFV and CKKS schemes (as one is designed over $X\in {\mathbb{Z}}_t$ and the other is over $X\in ℝ$), CKKS still can use the same $\tilde{W}$ (and ${\tilde{W}}^{\ast }$) matrices as BFV, because the $(\mu =2n)$-th cyclotomic polynomial over $X\in {\mathbb{Z}}_t$ exhibits the same essential properties as the $(\mu =2n)$-th cyclotomic polynomial over $X\in ℝ$ (as explained in §A-9). Especially, the roots of both $(\mu =2n)$ cyclotomic polynomials are the primitive $(\mu =2n)$-th roots of unity having the order $2n$, and those $n$ distinct roots are defined as ${\omega }^1,{\omega }^3,\cdots ,{\omega }^{2n-1}$, where $\omega$ can be any root. Therefore, substituting CKKS’s $(\mu =2n)$-th roots of unity into the $\omega$ terms in BFV’s encoding matrix $\tilde{W}$ (and decoding matrix ${\tilde{W}}^{\ast }$) preserves the same computational correctness for the encoding and decoding schemes, as well as for input vector slot rotation.

Importantly, the $\tilde{W}$ and ${\tilde{W}}^{\ast }$ matrices in both the BFV and CKKS schemes satisfy the exact requirement for supporting input vector slot rotation. That is, given the following relations:

• The $\overrightarrow{v}\to \overrightarrow{m}$ encoding formula: $\overrightarrow{m}=n^{-1}\cdot I_n^R\cdot \tilde{W}\cdot \overrightarrow{v}$
• The $\overrightarrow{m}\to \overrightarrow{v}$ decoding formula: $\overrightarrow{v}={\tilde{W}}^{\ast }\cdot \overrightarrow{m}$
• The encoded polynomial $M(X)=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{m}_i{X}^i$

, updating the polynomial $M(X)$ to $M(X^{J(h)})$ results in the effect of rotating the first half of the $n$-dimensional input vector slots ($\overrightarrow{v}\in {\mathbb{Z}}_p^n$ in the case of BFV, and the forward-ordered Hermitian vector ${\overrightarrow{v}}_{{}^{\prime }}\in {\widehat{ℂ}}^n\to {ℂ}^{\frac{n}{2}}$ in the case of CKKS) by $h$ positions to the left (in a wrapping manner among them) and the second half of the slots also by $h$ positions to the right (in a wrapping manner among them).

BFV uses CKKS’s same rotation scheme described in Summary D-2.9.3 (in §D-2.9.3) as follows:

Rotation within Half Slots: Like BFV, CKKS rotates the first half of the forward-ordered Hermitian input vector slots ${\overrightarrow{v}}_{{}^{\prime }}\in {\widehat{ℂ}}^n$ and the second half of its slots separately in a partitioned manner. This is because the first half rows of ${\tilde{W}}^{\ast }$ comprise the terms ${\omega }^{J(h)}$ for $h=\{0,1,\cdots ,{\displaystyle \frac{n}{2}}-1\}$ (i.e., evaluates $M(X)$ at $X=\{{\omega }^{J(0)},{\omega }^{J(1)},\cdots ,{\omega }^{J(\frac{n}{2}-1)}\}$), whereas the second half rows of ${\tilde{W}}^{\ast }$ comprise the terms ${\omega }^{J_{\ast }(h)}$ (i.e., evaluates $M(X)$ at $X=\{{\omega }^{J_{\ast }(0)},{\omega }^{J_{\ast }(1)},\cdots ,{\omega }^{J_{\ast }(\frac{n}{2}-1)}\}$), and the computed values of $J(h)$ and $J_{\ast }(h)$ repeat (i.e., rotate) within their own rotation group across $h=\{0,1,\cdots ,{\displaystyle \frac{n}{2}}-1\}$. Because of this structure of $\tilde{W}$ and ${\tilde{W}}^{\ast }$, BFV and CKKS cannot design a wrapping rotation scheme across all $n$ slots of the input vector homogeneously, but can instead design a wrapping rotation scheme across each group of the first-half and the second-half ${\displaystyle \frac{n}{2}}$ slots of the input vector in a partitioned manner. That being said, CKKS can meaningfully only use the first ${\displaystyle \frac{n}{2}}$ slots for homomorphic computations anyway, because the latter ${\displaystyle \frac{n}{2}}$ slots are conjugates of the first ${\displaystyle \frac{n}{2}}$ slots which cannot be chosen by the user but are deterministically configured based on the first ${\displaystyle \frac{n}{2}}$. On the other hand, in BFV, the user can choose the entire ${\displaystyle \frac{n}{2}}$ according to his/her needs, so BFV’s utility of slots is full $n$. Therefore, the user can use BFV’s first-half slots and second-half slots together to perform parallel computations.

D-3.9.1 Example

In this subsection, we will show the following 2 examples:

1.

Encode an input vector $\overrightarrow{v}$ into a plaintext polynomial $M(X)$ based on our updated updated encoding & decoding matrices $\tilde{W}$ and ${\tilde{W}}^{\ast }$

2.

Rotate all elements of the input vector $\overrightarrow{v}$ $h$ positions to the left by updating the encoded plaintext $M(X)$ to $M(X^{J(h)})$

We will use the same example of the input vector $\overrightarrow{v}$ used in §D-3.1.1: ${\overrightarrow{v}}^{⟨h=1⟩}=(1.1+4.3i,3.5-1.4i)$.

Remember that the encoded plaintext polynomial of $\overrightarrow{v}$ is as follows:

$\mathrm{\Delta }M(X)=2355+1195X+1485X^2+2933X^3\in R_{⟨4⟩}\in ℝ[X]∕X^4+1$

Suppose we want to rotate the input vector $\overrightarrow{v}$ by 1 position to the left as follows:

${\overrightarrow{v}}^{⟨h=1⟩}=(3.5-1.4i,1.1+4.3i)$

Therefore, we update $\mathrm{\Delta }M(X)$ to $\mathrm{\Delta }M(X^{J(1)})$ as follows:

$\mathrm{\Delta }M(X^{J(1)})=\mathrm{\Delta }M(X^5)=2355+1195(X^5)+1485{(X^5)}^2+2933{(X^5)}^3$

$=2355+1195X^5+1485X^{10}+2933X^{15}$

$=2355+1195X\cdot (-1)+1485X^2\cdot (-1)\cdot (-1)+2933X^3\cdot (-1)\cdot (-1)\cdot (-1)$

$=2355-1195X+1485X^2-2933X^3$

The rotated forward-ordered Hermitian input vector is computed as follows:

${\displaystyle \frac{{\tilde{W}}^{\ast }\cdot \mathrm{\Delta }\overrightarrow{m}}{\mathrm{\Delta }}}=\left[\begin{array}{c}\hfill 1,\omega ,{\omega }^2,{\omega }^3\hfill \\ \hfill 1,{\omega }^3,{\omega }^6,\omega \hfill \\ \hfill 1,\overline{\omega },\overline{{\omega }^2},\overline{{\omega }^3}\hfill \\ \hfill 1,\overline{{\omega }^3},\overline{{\omega }^6},\overline{\omega }\hfill \end{array}\right]$

$\cdot \left[\begin{array}{c}\hfill 2355\hfill \\ \hfill -1195\hfill \\ \hfill 1485\hfill \\ \hfill -2933\hfill \end{array}\right]\cdot {\displaystyle \frac{1}{1024}}$

$=\left[\begin{array}{c}\hfill 1,{\displaystyle \frac{\sqrt{2}}{2}}+{\displaystyle \frac{i\sqrt{2}}{2}},i,-{\displaystyle \frac{\sqrt{2}}{2}}+{\displaystyle \frac{i\sqrt{2}}{2}}\hfill \\ \hfill 1,-{\displaystyle \frac{\sqrt{2}}{2}}-{\displaystyle \frac{i\sqrt{2}}{2}},i,{\displaystyle \frac{\sqrt{2}}{2}}-{\displaystyle \frac{i\sqrt{2}}{2}}\hfill \\ \hfill 1,-{\displaystyle \frac{\sqrt{2}}{2}}+{\displaystyle \frac{i\sqrt{2}}{2}},-i,{\displaystyle \frac{\sqrt{2}}{2}}+{\displaystyle \frac{i\sqrt{2}}{2}}\hfill \\ \hfill 1,{\displaystyle \frac{\sqrt{2}}{2}}-{\displaystyle \frac{i\sqrt{2}}{2}},-i,-{\displaystyle \frac{\sqrt{2}}{2}}-{\displaystyle \frac{i\sqrt{2}}{2}}\hfill \end{array}\right]$ $\cdot \left[\begin{array}{c}\hfill 2.2998046875\hfill \\ \hfill -1.1669921875\hfill \\ \hfill 1.4501953125\hfill \\ \hfill -2.8642578125\hfill \end{array}\right]$

$\approx (3.500-1.4003i,1.0997+4.3007i,3.500+1.4003i,1.0997-4.3007i)$

Extract the first ${\displaystyle \frac{n}{2}}=2$ elements in the above Hermitian vector to recover the input vector:

$(3.500-1.4003i,1.0997+4.3007i)$

$\approx (3.5-1.4i,1.1+4.3i)$ $={\overrightarrow{v}}^{⟨h=1⟩}$ # The original input vector $\overrightarrow{v}$ rotated by 1 position to the left

In practice, we do not directly update $\mathrm{\Delta }M(X)$ to $\mathrm{\Delta }M(X^{J(1)})$, because we would not have access to the plaintext polynomial $M(X)$ unless we have the secret key $S(X)$. Therefore, we instead update $\mathsf{\text{𝖼𝗍}}=(A(X),B(X))$ to ${\mathsf{\text{𝖼𝗍}}}^{⟨h=1⟩}=(A(X^{J(1)}),B(X^{J(1)}))$, which is equivalent to homomorphically rotating the encrypted input vector slots. Then, decrypting ${\mathsf{\text{𝖼𝗍}}}^{⟨h=1⟩}$ and decoding it would output ${\overrightarrow{v}}^{⟨h=1⟩}$.

Source Code: Examples of CKKS’s homomorphic input vector slot rotation can be executed by running this Python script.