D-3.11 Homomorphic Conjugation

As explained in Summary D-3.1 (§D-3.1), given the ${\displaystyle \frac{n}{2}}$-dimensional input vector $\overrightarrow{v}=(v_0,v_1,\cdots ,v_{\frac{n}{2}-1})$, its corresponding $n$-dimensional Hermitian vector is ${\overrightarrow{v}}_{{}^{\prime }}=(v_0,v_1,\cdots ,v_{\frac{n}{2}-1},{\overline{v}}_{\frac{n}{2}-1},{\overline{v}}_{\frac{n}{2}-2},\cdots ,{\overline{v}}_1,{\overline{v}}_0)$. To compute the conjugation of $\overrightarrow{v}$, which is essentially conjugating ${\overrightarrow{v}}_{{}^{\prime }}$, we can conjugate $M(X)$ as follows:

${\overline{\overrightarrow{v}}}_{{}^{\prime }}=({\overline{v}}_0,{\overline{v}}_1,\cdots ,{\overline{v}}_{\frac{n}{2}-1},v_{\frac{n}{2}-1},\cdots ,v_1,v_0)$

$=(M(\overline{\omega })),M(\overline{{\omega }^3}),\cdots ,M(\overline{{\omega }^{n-1}}),M({\omega }^{n-1}),\cdots ,M({\omega }^3),M(\omega ))$ # where $\omega =e^{\frac{\mathit{𝑖𝜋}}{n}}$

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

# since $\overline{{\omega }^k}=e^{\overline{\frac{\mathit{𝑘𝑖𝜋}}{n}}}=e^{-\frac{\mathit{𝑘𝑖𝜋}}{n}}={\omega }^{-k}$ and ${\omega }^k={(\overline{{\omega }^k})}^{-1}$ for $k=\{1,3,\cdots ,n-1\}$

$=\{M(X^{-1})\}$ # where $X=\{\omega ,{\omega }^3,\cdots ,{\omega }^{n-1},\overline{{\omega }^{n-1}},\cdots ,\overline{{\omega }^3},\overline{\omega }\}=\{{\omega }^1,{\omega }^3,\cdots ,{\omega }^{2n-1}\}$

Therefore, homomorphic conjugation of the input vector is equivalent to updating the ciphertext $(A(X)),B(X))$ to $(A(X^{-1}),B(X^{-1}))$ and then key-switching it from $S(X^{-1})\to S(X)$.