D-2.9 Homomorphic Rotation of Input Vector Slots

In this section, we will explain how to homomorphically rotate the elements of an input vector $\overrightarrow{v}$ after it is already encoded as a polynomial and encrypted as an RLWE ciphertext. In §A-5.2, we learned how to rotate the coefficients of a polynomial. However, rotating the plaintext polynomial $M(X)$ or RLWE ciphertext polynomials $(A(X),B(X))$ does not necessarily rotate the input vector, which is the source of them.

The key requirement of homomorphic rotation of input vector slots (i.e., input vector) is that this operation should be performed on the RLWE ciphertext such that after this operation, if we decrypt the RLWE ciphertext and decode it, the recovered input vector will be in a rotated state as we expect. We will divide this task into the following two sub-problems:

1.

How to indirectly rotate the input vector by updating the plaintext polynomial $M$ to $M^{\prime }$?

2.

How to indirectly update the plaintext polynomial $M$ to $M^{\prime }$ by updating the RLWE ciphertext polynomials $(A,B)$ to $(A^{\prime },B^{\prime })$?

D-2.9.1 Rotating Input Vector Slots by Updating the Plaintext Polynomial

In this task, our goal is to modify the plaintext polynomial $M(X)$ such that the first-half elements of the input vector $\overrightarrow{v}$ are shifted to the left by $h$ positions in a wrapping manner among them, and the second-half elements of $\overrightarrow{v}$ are also shifted to the left by $h$ positions in a wrapping manner among them. Specifically, if $\overrightarrow{v}$ is defined as follows:

$\overrightarrow{v}=(v_0,v_1,\cdots ,v_{n-1})$

Then, we will denote the $h$-shifted vector ${\overrightarrow{v}}^{⟨h⟩}$ as follows:

${\overrightarrow{v}}^{⟨h⟩}=(\underset{\text{The first-half }{\displaystyle \frac{n}{2}}\text{ elements }h\text{-rotated to the left}}{\underbrace{v_h,v_{h+1},\cdots ,v_0,v_1,\cdots ,v_{h-2},v_{h-1},}}\underset{\text{The second-half }{\displaystyle \frac{n}{2}}\text{ elements }h\text{-rotated to the left}}{\underbrace{v_{\frac{n}{2}+h},v_{\frac{n}{2}+h+1},\cdots ,v_{\frac{n}{2}+h-2},v_{\frac{n}{2}+h-1}}})$

Remember from §D-2.2 that the BFV encoding scheme’s components are as follows:

$\overrightarrow{v}=(v_0,v_1,v_2,\cdots ,v_{n-1})$ # $n$-dimensional input vector

$W=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill \\ \hfill (\omega )\hfill & \hfill ({\omega }^3)\hfill & \hfill ({\omega }^5)\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{2n-1})\hfill \\ \hfill {(\omega )}^2\hfill & \hfill {({\omega }^3)}^2\hfill & \hfill {({\omega }^5)}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{2n-1})}^2\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill {(\omega )}^{n-1}\hfill & \hfill {({\omega }^3)}^{n-1}\hfill & \hfill {({\omega }^5)}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{2n-1})}^{n-1}\hfill \end{array}\right]$

$=\left[\begin{array}{cccccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill & \hfill 1\hfill \\ \hfill (\omega )\hfill & \hfill ({\omega }^3)\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{\frac{n}{2}-1})\hfill & \hfill ({\omega }^{-(\frac{n}{2}-1)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{-3})\hfill & \hfill ({\omega }^{-1})\hfill \\ \hfill {(\omega )}^2\hfill & \hfill {({\omega }^3)}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{\frac{n}{2}-1})}^2\hfill & \hfill {({\omega }^{-(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{-3})}^2\hfill & \hfill {({\omega }^{-1})}^2\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill {(\omega )}^{n-1}\hfill & \hfill {({\omega }^3)}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{\frac{n}{2}-1})}^{n-1}\hfill & \hfill {({\omega }^{-(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{-3})}^{n-1}\hfill & \hfill {({\omega }^{-1})}^{n-1}\hfill \end{array}\right]$

, where $\omega =g^{\frac{t-1}{2n}}modt$ ($g$ is a generator of ${\mathbb{Z}}_t^{\times }$)

# The encoding matrix that converts $\overrightarrow{v}$ into $\overrightarrow{m}$ ( i.e., $n$ coefficients of the plaintext polynomial $M(X)$ )

$\mathrm{\Delta }\overrightarrow{m}=n^{-1}\cdot \mathrm{\Delta }W\cdot I_n^R\cdot \overrightarrow{v}$

# A vector containing the scaled $n$ integer coefficients of the plaintext polynomial

$\mathrm{\Delta }M=\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(\mathrm{\Delta }{m}_i{X}^i)$

# The integer polynomial that isomorphically encodes the input vector $\overrightarrow{v}$

We learned from §A-10.6 that decoding the polynomial $M(X)$ back to $\overrightarrow{v}$ is equivalent to evaluating $M(X)$ at the following $n$ distinct primitive $(\mu =2n)$-th root of unity: $\{\omega ,{\omega }^3,{\omega }^5,\cdots ,{\omega }^{2n-3},{\omega }^{2n-1}\}$. Thus, the above decoding process is equivalent to the following:

$\overrightarrow{v}={\displaystyle \frac{W^T\mathrm{\Delta }\overrightarrow{m}}{\mathrm{\Delta }}}=(W_0^T\cdot \overrightarrow{m},W_1^T\cdot \overrightarrow{m},W_2^T\cdot \overrightarrow{m},\cdots ,W_{n-1}^T\cdot \overrightarrow{m})$

$=(M(\omega ),M({\omega }^3),M({\omega }^5),\cdots ,M({\omega }^{2n-3}),M({\omega }^{2n-1}))$

$=(M(\omega ),M({\omega }^3),M({\omega }^5),\cdots ,M({\omega }^{n-3}),M({\omega }^{n-1}),M({\omega }^{-(n-1)}),M({\omega }^{-(n-3)}),\cdots ,M({\omega }^{-3}),M(\omega -1))$

Now, our next task is to modify $M(X)$ to $M^{\prime }(X)$ such that decoding $M^{\prime }(X)$ will give us a modified input vector ${\overrightarrow{v}}^{⟨h⟩}$ that is a rotation of the first half elements of $\overrightarrow{v}$ by $h$ positions to the left (in a wrapping manner among them), and the second half elements of it also rotated by $h$ positions to the left (in a wrapping manner among them). To accomplish this rotation, we will take a 2-step solution:

1.

To convert $M(X)$ into $M^{\prime }(X)$, we will define the new mapping ${\sigma }_M$ as follows:

${\sigma }_M:(M(X),h)\in (R_{⟨n,t⟩},{\mathbb{Z}}_n)\to M^{\prime }(X)\in R_{⟨n,t⟩}$

, where $h$ is the number of rotation positions to be applied to $\overrightarrow{v}$.

2.

To decode $M^{\prime }(X)$ into the rotated input vector ${\overrightarrow{v}}^{⟨h⟩}$, we need to re-design our decoding scheme by modifying Encoding₁’s (§D-2.2.1) isomorphic mapping $\sigma :M(X)\in R_{⟨n,t⟩}\to \overrightarrow{v}\in {\mathbb{Z}}^n$

Converting $𝐌(𝐗)$ into ${𝐌}^{\prime }(𝐗)$: Our first task is to convert $M(X)$ into $M^{\prime }(X)$, which is equivalent to applying our new mapping ${\sigma }_M:(M(X),h)\in (R_{⟨n,t⟩},{\mathbb{Z}}_n)\to M^{\prime }(X)\in R_{⟨n,t⟩}$, such that decoding $M^{\prime }(X)$ gives a rotated input vector ${\overrightarrow{v}}^{⟨h⟩}$ whose first half of the elements in $\overrightarrow{v}$ are rotated by $h$ positions to the left (in a wrapping manner among them), and the second half of the elements are also rotated by $h$ positions to the left (in a wrapping manner among them). To design ${\sigma }_M$ that satisfies this requirement, we will use the number $5^j$ which has the following two special properties (based on number theory):

• $(5^{j}mod2n)$ and $(-5^{j}mod2n)$ generate all odd numbers between $[0,2n)$ for the integer $j$ where $0\le j<{\displaystyle \frac{n}{2}}$.
• For each integer $j$ where $0\le j<{\displaystyle \frac{n}{2}}$, $(5^{j}mod2n)+(-5^{j}mod2n)\equiv 0mod2n$.

For example, suppose the modulus $2n=16$. Then,

As shown above, $0\le j<4$ generate all odd numbers between $[0,16)$. Also, for each $j$ in $0\le j<4$, $(5^{j}mod16)+(-5^{j}mod16)=16$.

Let’s define $J(h)=5^{h}mod2n$, and $J_{\ast }(h)=-5^{h}mod2n$. Based on $J(h)$ and $J_{\ast }(h)$, we will define the mapping ${\sigma }_M:M(X)\to M^{\prime }(X)$ as follows:

${\sigma }_M:M(X)\to M(X^{J(h)})$

Given a plaintext polynomial $M(X)$, in order to give its decoded version of input vector $\overrightarrow{v}$ the effect of the first half of the elements being rotated by $h$ positions to the left (in a wrapping manner) and the second half of the elements also being rotated by $h$ positions to the left (in a wrapping manner), we update the current plaintext polynomial $M(X)$ to a new polynomial $M^{\prime }(X)=M(X^{J(h)})=M(X^{5^h})$ by applying the ${\sigma }_M$ mapping, where $h$ is the number of positions for left rotations for the first half and second half of the elements of $\overrightarrow{v}$.

Decoding ${𝐌}^{\prime }(𝐗)$ into ${\overrightarrow{v}}^{⟨h⟩}$: Our second task is to modify our original decoding scheme in order to successfully decode $M^{\prime }(X)$ into the rotated input vector ${\overrightarrow{v}}^{⟨h⟩}$. For this, we will modify our original isomorphic mapping $\sigma :M(X)\to \overrightarrow{v}$, from:

$\sigma :M(X)\in R_{⟨n,q⟩}\to (M(\omega ),M({\omega }^3),M({\omega }^5),\cdots ,M({\omega }^{2n-1}))\in {\mathbb{Z}}^n$ # designed in §A-10.6

, to the following:

${\sigma }_J:M(X)\in R_{⟨n,t⟩}\to (M({\omega }^{J(0)}),M({\omega }^{J(1)}),M({\omega }^{J(2)}),\cdots ,M({\omega }^{J(\frac{n}{2}-1)}),$

${\sigma }_J:M(X)\in R_{⟨n,q⟩}\to ($ $M({\omega }^{J_{\ast }(0)}),M({\omega }^{J_{\ast }(1)}),M({\omega }^{J_{\ast }(2)}),\cdots ,M({\omega }^{J_{\ast }(\frac{n}{2}-1}))\in {\mathbb{Z}}^n$

The common aspect between $\sigma$ and ${\sigma }_J$ is that they both evaluate the polynomial $M(X)$ at $n$ distinct primitive $(\mu =2n)$-th roots of unity (i.e., $w^i$ for all odd $i$ between $[0,2n]$ ). In the case of the ${\sigma }_J$ mapping, note that $J(j)=5^{j}mod2n$ and $J_{\ast }(j)=-5^{j}mod2n$ for each $j$ in $0\le j<{\displaystyle \frac{n}{2}}$ cover all odd numbers between $[0,2n]$. Therefore, ${\omega }^{J(j)}$ and ${\omega }^{J_{\ast }(j)}$ between $0\le j<\frac{n}{2}$ cover all $n$ distinct primitive $(\mu =2n)$-th roots of unity.

Meanwhile, the difference between $\sigma$ and ${\sigma }_J$ is the order of the output vector elements. In the $\sigma$ mapping, the order of evaluated coordinates for $M(X)$ is $\omega ,{\omega }^3,\cdots ,{\omega }^{2n-1}$, whereas in the ${\sigma }_J$ mapping, the order of evaluated coordinates is ${\omega }^{J(0)},{\omega }^{J(1)},\cdots ,{\omega }^{J(\frac{n}{2}-1)},{\omega }^{J_{\ast }(0)},{\omega }^{J_{\ast }(1)},\cdots ,{\omega }^{J_{\ast }(\frac{n}{2}-1)}$. We will later explain why we modified the ordering like this.

In the original Decoding₂ process (§D-2.2), applying the $\sigma$ mapping to a plaintext polynomial $M(X)$ was equivalent to computing the following:

${\overrightarrow{v}}_{{}^{\prime }}=(M(\omega ),M({\omega }^3),M({\omega }^5),\cdots ,M({\omega }^{2n-3}),M({\omega }^{2n-1}))$

$=(M(\omega ),M({\omega }^3),M({\omega }^5),\cdots ,M({\omega }^{n-1}),M({\omega }^{-(n-1)}),\cdots ,M({\omega }^{-3}),M({\omega }^{-1}))$

$=(W_0^T\cdot \overrightarrow{m},W_1^T\cdot \overrightarrow{m},W_2^T\cdot \overrightarrow{m},\cdots ,W_{n-1}^T\cdot \overrightarrow{m})$ $$ # where $W_i^T$ is the $(i+1)$-th row of $W^T$

$=W^T\overrightarrow{m}$

Similarly, the modified ${\sigma }_J$ mapping to the plaintext polynomial $M(X)$ is equivalent to computing the following:

${\overrightarrow{v}}_{{}^{\prime }}=(M({\omega }^{J(0)}),M({\omega }^{J(1)}),M({\omega }^{J(2)}),\cdots ,M({\omega }^{J(\frac{n}{2}-1)}),M({\omega }^{J_{\ast }(0)}),M({\omega }^{J_{\ast }(1)}),\cdots ,M({\omega }^{J_{\ast }(\frac{n}{2}-1)}))$

$=({\tilde{W}}_0^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_1^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_2^{\ast }\cdot \overrightarrow{m},\cdots ,{\tilde{W}}_{n-1}^{\ast }\cdot \overrightarrow{m})$

$={\tilde{W}}^{\ast }\overrightarrow{m}$, where

${\tilde{W}}^{\ast }=\left[\begin{array}{ccccc}\hfill 1\hfill & \hfill ({\omega }^{J(0)})\hfill & \hfill {({\omega }^{J(0)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(1)})\hfill & \hfill {({\omega }^{J(1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(2)})\hfill & \hfill {({\omega }^{J(2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(2)})}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J(\frac{n}{2}-1)})\hfill & \hfill {({\omega }^{J(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(\frac{n}{2}-1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(0)})\hfill & \hfill {({\omega }^{J_{\ast }(0)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(1)})\hfill & \hfill {({\omega }^{J_{\ast }(1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(1)})}^{n-1}\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(2)})\hfill & \hfill {({\omega }^{J_{\ast }(2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(2)})}^{n-1}\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill \\ \hfill 1\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-1)})\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^{n-1}\hfill \end{array}\right]$

$\tilde{W}=\left[\begin{array}{cccccccc}\hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill 1\hfill & \hfill \cdots \hfill & \hfill 1\hfill \\ \hfill ({\omega }^{J(\frac{n}{2}-1)})\hfill & \hfill ({\omega }^{J(\frac{n}{2}-2)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{J(0)})\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-1)})\hfill & \hfill ({\omega }^{J_{\ast }(\frac{n}{2}-2)})\hfill & \hfill \cdots \hfill & \hfill ({\omega }^{J_{\ast }(0)})\hfill \\ \hfill {({\omega }^{J(\frac{n}{2}-1)})}^2\hfill & \hfill {({\omega }^{J(\frac{n}{2}-2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^2\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^2\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-2)})}^2\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^2\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \ddots \hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill ⋮\hfill \\ \hfill {({\omega }^{J(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill {({\omega }^{J(\frac{n}{2}-2)})}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J(0)})}^{n-1}\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-1)})}^{n-1}\hfill & \hfill {({\omega }^{J_{\ast }(\frac{n}{2}-2)})}^{n-1}\hfill & \hfill \cdots \hfill & \hfill {({\omega }^{J_{\ast }(0)})}^{n-1}\hfill \end{array}\right]$

From this point, we will replace $W$ in the Encoding₁ process (§D-2.2) by $\tilde{W}$, and $W^T$ in the Decoding₂ process by ${\tilde{W}}^{\ast }$.

To demonstrate that $\tilde{W}$ is a valid encoding matrix like $W$ and ${\tilde{W}}^{\ast }$ is a valid decoding matrix like $W^T$, we need to prove the following 2 aspects:

• $\widetilde{𝐖}$ is a basis of the $𝐧$-dimensional vector space: This is true, because $\tilde{W}$ is simply a row-wise re-ordering of $W$, which is still a basis of the $𝐧$-dimensional vector space.

• ${\tilde{W}}^{\ast }\cdot \tilde{W}=n\cdot I_n^R$ (to satisfy Theorem A-11.4 in §A-11.4): This proof is split into 2 sub-proofs:

  1.

  ${\tilde{W}}^{\ast }\cdot \tilde{W}$ has value $𝐧$ along the anti-diagonal line: Each element along the anti-diagonal line of ${\tilde{W}}^{\ast }\cdot \tilde{W}$ is computed as $\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2\mathit{𝑛𝑖𝑘}}=n$ where $k$ is some integer.

  2.

  ${\tilde{W}}^{\ast }\cdot \tilde{W}$ has value 0 at all other coordinates: All other elements except for the ones along the anti-diagonal lines are $\underset{i=0}{\overset{n-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{\omega }^{2i}{\displaystyle \frac{{\omega }^n-1}{\omega -1}}=0$ (by Geometric Sum).

  We provide the Python script that empirically demonstrates this.

Therefore, ${\tilde{W}}^{\ast }$ and $\tilde{W}$ are valid encoding & decoding matrices that transform $\overrightarrow{v}$ into $M(X)$.

Now, let’s think about what will be the structure of ${\overrightarrow{v}}^{⟨h⟩}$ (i.e., the first-half elements of $\overrightarrow{v}$ being rotated $h$ positions to the left in a wrapping manner among them and the second-half elements of it also being rotated $h$ positions to the left in a wrapping manner among them). Remember that $\overrightarrow{v}$ is as follows:

$\overrightarrow{v}=(M({\omega }^{J(0)}),M({\omega }^{J(1)}),\cdots ,M({\omega }^{J(\frac{n}{2}-1)}),M({\omega }^{J_{\ast }(0)}),M({\omega }^{J_{\ast }(1)}),\cdots ,M({\omega }^{J_{\ast }(\frac{n}{2}-1)}))$

$=({\tilde{W}}_0^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_1^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_2^{\ast }\cdot \overrightarrow{m},\cdots ,{\tilde{W}}_{n-1}^{\ast }\cdot \overrightarrow{m})$

Thus, the state of ${\overrightarrow{v}}^{⟨h⟩}$ which is equivalent to rotating $\overrightarrow{v}$ by $h$ positions to the left for the first-half and second-half element groups will be the following:

${\overrightarrow{v}}^{⟨h⟩}=(M({\omega }^{J(h)}),M({\omega }^{J(h+1)}),\cdots ,M({\omega }^{J(\frac{n}{2}-1)}),M({\omega }^{J(0)}),M({\omega }^{J(1)}),\cdots ,M({\omega }^{J(h-2)}),M({\omega }^{J(h-1)}),$

$M({\omega }^{J_{\ast }(h)}),M({\omega }^{J_{\ast }(h+1)}),\cdots ,M({\omega }^{J_{\ast }(\frac{n}{2}-1)}),M({\omega }^{J_{\ast }(0)}),M({\omega }^{J_{\ast }(1)}),\cdots ,M({\omega }^{J_{\ast }(h-2)}),M({\omega }^{J_{\ast }(h-1)}))$

Notice that the above computation of ${\overrightarrow{v}}^{⟨h⟩}$ is equivalent to vertically rotating the upper $\frac{n}{2}$ rows of ${\tilde{W}}^{\ast }$ by $h$ positions upward (in a wrapping manner among them), rotating the lower $\frac{n}{2}$ rows of ${\tilde{W}}^{\ast }$ by $h$ positions upward (in a wrapping manner among them), and multiplying the resulting matrix with $\overrightarrow{m}$. However, it is not desirable to directly modify the decoding matrix ${\tilde{W}}^{\ast }$ like this in practice, because then the decoding matrix loses its consistency. Therefore, instead of directly modifying ${\tilde{W}}^{\ast }$, we will modify $\overrightarrow{m}$ to ${\overrightarrow{m}}_{{}^{\prime }}$ (i.e., modify $M(X)$ to $M^{\prime }(X)$) such that the relation ${\overrightarrow{v}}^{⟨h⟩}={\tilde{W}}^{\ast }\cdot {\overrightarrow{m}}_{{}^{\prime }}$ holds. Let’s extract the upper-half rows of ${\tilde{W}}^{\ast }$ and denote this ${\displaystyle \frac{n}{2}}\times n$ matrix as ${\tilde{H}}_1^{\ast }$. Then, ${\tilde{H}}_1^{\ast }$ is equivalent to a Vandermonde matrix (Definition A-10.2 in §A-10.2) in the form of $V({\omega }^{J(0)},{\omega }^{J(1)},\cdots ,{\omega }^{J(\frac{n}{2}-1)})$. Similarly, let’s extract the lower-half rows of ${\tilde{W}}^{\ast }$ and denote this ${\displaystyle \frac{n}{2}}\times n$ matrix as ${\tilde{H}}_2^{\ast }$. Then, ${\tilde{H}}_2^{\ast }$ is equivalent to a Vandermonde matrix (Definition A-10.2 in §A-10.2) in the form of $V({\omega }^{J_{\ast }(0)},{\omega }^{J_{\ast }(1)},\cdots ,{\omega }^{J_{\ast }(\frac{n}{2}-1)})$.

Now, let’s vertically rotate the rows of ${\tilde{H}}_1^{\ast }$ by $h$ positions upward and denote it as ${\tilde{H}}_1^{\ast ⟨h⟩}$; and vertically rotate the rows of ${\tilde{H}}_2^{\ast }$ by $h$ positions upward and denote it as ${\tilde{H}}_2^{\ast ⟨h⟩}$. And let’s denote the ${\displaystyle \frac{n}{2}}$-dimensional vector comprising the first-half elements of ${\overrightarrow{v}}^{⟨h⟩}$ as ${\overrightarrow{v}}_1^{⟨h⟩}$, and the ${\displaystyle \frac{n}{2}}$-dimensional vector comprising the second-half elements of ${\overrightarrow{v}}^{⟨h⟩}$ as ${\overrightarrow{v}}_2^{⟨h⟩}$. Then, computing (i.e., decoding) ${\overrightarrow{v}}_1^{⟨h⟩}={\tilde{H}}_1^{\ast ⟨h⟩}\cdot \overrightarrow{m}$ is equivalent to modifying $M(X)$ to $M^{\prime }(X)=M(X^{J(h)})$ (whose coefficient vector is ${\overrightarrow{m}}^{⟨h⟩}$) and then computing (i.e., decoding) ${\overrightarrow{v}}_1^{⟨h⟩}={\tilde{H}}_1^{\ast }\cdot {\overrightarrow{m}}^{⟨h⟩}$. This is because:

${\overrightarrow{v}}_1^{⟨h⟩}={\tilde{H}}_1^{\ast ⟨h⟩}\cdot \overrightarrow{m}$

$=({\tilde{W}}_h^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_{h+1}^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_{h+2}^{\ast }\cdot \overrightarrow{m},\cdots ,{\tilde{W}}_{\frac{n}{2}-1}^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_0^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_1^{\ast }\cdot \overrightarrow{m},\cdots ,{\tilde{W}}_{h-2}^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_{h-1}^{\ast }\cdot \overrightarrow{m})$

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

# This is equivalent to evaluating the polynomial $M(X^{J(h)})$ at the following ${\displaystyle \frac{n}{2}}$ distinct $(\mu =2n)$-th roots of unity: ${\omega }^{J(0)},{\omega }^{J(1)},{\omega }^{J(2)},\cdots ,{\omega }^{J(\frac{n}{2}-1)}$

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

$=(M({\omega }^{5^h\cdot 5^0}),M({\omega }^{5^h\cdot 5^1}),M({\omega }^{5^h\cdot 5^2}),\cdots ,M({\omega }^{5^h\cdot 5^{n∕2-1}}))$

$=(M({\omega }^{5^h}),M({\omega }^{5^{h+1}}),M({\omega }^{5^{h+2}}),\cdots ,M({\omega }^{5^{h+n∕2-1}}))$ # note that $5^{\frac{n}{2}}mod2n=1$

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

$\cdots ,M({\omega }^{J(h-2)}),M({\omega }^{J(h-1)}))$

$={\tilde{H}}_1^{\ast }\cdot {\overrightarrow{m}}^{⟨h⟩}$ # where ${\overrightarrow{m}}^{⟨h⟩}$ contains the $n$ coefficients of the polynomial $M(X^{J(h)})$

Similarly, computing (i.e., decoding) ${\overrightarrow{v}}_2^{⟨h⟩}={\tilde{H}}_2^{\ast ⟨h⟩}\cdot \overrightarrow{m}$ is equivalent to modifying $M(X)$ to $M^{\prime }(X)=M(X^{J(h)})$ (whose coefficient vector is ${\overrightarrow{m}}^{⟨h⟩}$) and then computing (i.e., decoding) ${\overrightarrow{v}}_2^{⟨h⟩}={\tilde{H}}_2^{\ast }\cdot {\overrightarrow{m}}^{⟨h⟩}$. This is because,

${\overrightarrow{v}}_2^{⟨h⟩}={\tilde{H}}_2^{\ast ⟨h⟩}\cdot \overrightarrow{m}$

$=({\tilde{W}}_{\frac{n}{2}+h}^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_{\frac{n}{2}+h+1}^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_{\frac{n}{2}+h+2}^{\ast }\cdot \overrightarrow{m},\cdots ,{\tilde{W}}_{n-1}^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_{\frac{n}{2}}^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_{\frac{n}{2}+1}^{\ast }\cdot \overrightarrow{m},\cdots ,$

${\tilde{W}}_{\frac{n}{2}+h-2}^{\ast }\cdot \overrightarrow{m},{\tilde{W}}_{\frac{n}{2}+h-1}^{\ast }\cdot \overrightarrow{m})$

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

# This is equivalent to evaluating the polynomial $M(X^{J(h)})$ at the following ${\displaystyle \frac{n}{2}}$ distinct $(\mu =2n)$-th roots of unity: ${\omega }^{J_{\ast }(0)},{\omega }^{J_{\ast }(1)},{\omega }^{J_{\ast }(2)},\cdots ,{\omega }^{J_{\ast }(\frac{n}{2}-1)}$

$=(M({\omega }^{J(h)\cdot J_{\ast }(0)}),M({\omega }^{J(h)\cdot J_{\ast }(1)}),M({\omega }^{J(h)\cdot J_{\ast }(2)}),\cdots ,M({\omega }^{J(h)\cdot J_{\ast }(\frac{n}{2}-1)}))$

$=(M({\omega }^{5^h\cdot -5^0}),M({\omega }^{5^h\cdot -5^1}),M({\omega }^{5^h\cdot -5^2}),\cdots ,M({\omega }^{5^h\cdot -5^{n∕2-1}}))$

$=(M({\omega }^{-5^h}),M({\omega }^{-5^{h+1}}),M({\omega }^{-5^{h+2}}),\cdots ,M({\omega }^{-5^{h+n∕2-1}}))$ # note that $-(5^{\frac{n}{2}}mod2n)=-1$

$=(M({\omega }^{J_{\ast }(h)}),M({\omega }^{J_{\ast }(h+1)}),M({\omega }^{J_{\ast }(h+2)}),\cdots ,M({\omega }^{J_{\ast }(\frac{n}{2}-1)}),M({\omega }^{J_{\ast }(0)}),M({\omega }^{J_{\ast }(1)}),$

$\cdots ,M({\omega }^{J_{\ast }(h-2)}),M({\omega }^{J_{\ast }(h-1)}))$

$={\tilde{H}}_2^{\ast }\cdot {\overrightarrow{m}}^{⟨h⟩}$

The above derivations demonstrate that ${\overrightarrow{v}}_1^{⟨h⟩}={\tilde{H}}_1^{\ast }\cdot {\overrightarrow{m}}^{⟨h⟩}$, and ${\overrightarrow{v}}_2^{⟨h⟩}={\tilde{H}}_2^{\ast }\cdot {\overrightarrow{m}}^{⟨h⟩}$. Combining these two findings, we reach the conclusion that ${\overrightarrow{v}}^{⟨h⟩}={\tilde{W}}^{\ast }\cdot {\overrightarrow{m}}^{⟨h⟩}$: rotating the first-half elements of the input vector $\overrightarrow{v}$ by $h$ positions to the left and the second-half elements of it by $h$ positions also to the left is equivalent to updating the plaintext polynomial $M(X)$ to $M(X^{J(h)})$ and then decoding it with the decoding matrix ${\tilde{W}}^{\ast }$.

However, now a new problem is that we cannot directly update the plaintext $M(X)$ to $M(X^{J(h)})$, because $M(X)$ is encrypted as an RLWE ciphertext. Therefore, we need to instead update the RLWE ciphertext components $(A,B)$ to indirectly by updating $M(X)$ to $M(X^{J(X)})$. We will explain this in the next subsection.

D-2.9.2 Updating the Plaintext Polynomial by Updating the Ciphertext Polynomials

Given an RLWE ciphertext $\mathsf{\text{𝖼𝗍}}=(A,B)$, our goal is to update $\mathsf{\text{𝖼𝗍}}=(A,B)$ to $C^{⟨h⟩}=(A^{⟨h⟩},B^{⟨h⟩})$ such that decrypting it gives the input vector ${\overrightarrow{v}}^{⟨h⟩}$. That is, the following relation should hold:

${\mathsf{\text{𝖱𝖫𝖶𝖤}}}_{S,\sigma }^{-1}(C^{⟨h⟩}=(A^{⟨h⟩},B^{⟨h⟩}))=\mathrm{\Delta }M(X^{J(h)})+E^{\prime }$

Remember that in the RLWE cryptosystem (§B-3)’s alternative version (§B-4.4), the plaintext and ciphertext pair have the following relation:

$\mathrm{\Delta }M(X)+E(X)=A(X)\cdot S(S)+B(X)\approx \mathrm{\Delta }M(X)$

If we apply $X=X^{J(h)}$ in the above relation, we can derive the following relation:

$\mathrm{\Delta }M(X^{J(h)})+E(X^{J(h)})=A(X^{J(h)})\cdot S(X^{J(h)})+B(X^{J(h)})\approx \mathrm{\Delta }M(X^{J(h)})$

This relation implies that if we decrypt the ciphertext $C^{⟨h⟩}=(A(X^{J(h)}),B(X^{J(h)}))$ with $S(X^{J(h)})$ as the secret key, then we get $\mathrm{\Delta }M(X^{J(h)})$. Therefore, $C^{⟨h⟩}=(A(X^{J(h)}),B(X^{J(h)}))$ is the RLWE ciphertext we are looking for, because decrypting it and then decoding its plaintext $M(X^{J(h)})$ will give us the input vector ${\overrightarrow{v}}^{⟨h⟩}$.