D-3.11 Homomorphic Conjugation

As explained in Summary D-3.1 (§D-3.1), given the ${\displaystyle \frac{n}{2}}$-slot input vector $\overrightarrow{v}=(v_0,v_1,\cdots ,v_{\frac{n}{2}-1})$, its corresponding $n$-slot Hermitian vector is ${\overrightarrow{v}}_{{}^{\prime }}=(v_0,v_1,\cdots ,v_{\frac{n}{2}-1},{\overline{v}}_0,{\overline{v}}_1,\cdots ,{\overline{v}}_{\frac{n}{2}-1})$. 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_0,v_1,\cdots ,v_{\frac{n}{2}-1})$

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

$=(M({(\omega )}^{-1}),M({({\omega }^3)}^{-1}),\cdots ,M({({\omega }^{n-1})}^{-1}),M(\omega ),M({\omega }^3),\cdots ,M({\omega }^{n-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},{\omega }^{-1},{\omega }^{-3},\cdots ,{\omega }^{-(n-1)}\}=\{\omega ,{\omega }^3,\cdots ,{\omega }^{n-1},{\omega }^{2n-1},{\omega }^{2n-3},\cdots ,{\omega }^{n+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)$.