Proof. $$

1.

Given the principle of polynomial decomposition (§A-6.2) and the polynomial $A_i\in {\mathbb{Z}}_q[x]∕(x^n+1)$, its decomposition is as follows:

$$

${\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(A_i)=(A_{i,1},A_{i,2},\dots ,A_{i,l})$, where

$$

$A_i=A_{i,1}{\displaystyle \frac{q}{{\beta }^1}}+A_{i,2}{\displaystyle \frac{q}{{\beta }^2}}+\cdots +A_{i,l}{\displaystyle \frac{q}{{\beta }^l}}$

$$

2.

$⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(A_i),{\mathrm{𝐾𝑆𝐾}}_i⟩$
$=A_{i,1}\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left({\displaystyle \frac{q}{{\beta }^1}}{S}_i+E_{i,1}\right)+A_{i,2}\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left({\displaystyle \frac{q}{{\beta }^2}}{S}_i+E_{i,2}\right)+\cdots +A_{i,l}\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left({\displaystyle \frac{q}{{\beta }^l}}{S}_i+E_{i,l}\right)$

$▹$ where each GLWE ciphertext is an encryption of $S_i{\displaystyle \frac{q}{\beta }},S_i{\displaystyle \frac{q}{{\beta }^2}},\cdots ,S_i{\displaystyle \frac{q}{{\beta }^l}}$ as plaintext with the plaintext scaling factor 1

$$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(\left(A_{i,1}{\displaystyle \frac{q}{{\beta }^1}}+A_{i,2}{\displaystyle \frac{q}{{\beta }^2}}+\cdots +A_{i,l}{\displaystyle \frac{q}{{\beta }^l}}\right)\cdot S_i+E_i\right)$ $▹$ where $E_i=\underset{j=1}{\overset{l}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{A}_{i,1}{E}_{i,j}$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(\left(A_i\right)\cdot S_i+E_i\right)={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(A_i{S}_i+E_i)$

$$

3.

$\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(A_i),{\mathrm{𝐾𝑆𝐾}}_i⟩=\sum _{i=0}^{k-1}({\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(A_i{S}_i+E_i))$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{A}_i{S}_i+E_i\right)$

$$

4.

$B$ is equivalent to a trivial GLWE encryption with $S^{\prime }$, where its every $A_0,A_1,\dots ,A_{k^{\prime }-1}$ is 0. That is, ${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(B)=(\stackrel{k^{\prime }}{\overbrace{0,0,\dots <!--\; FUNCTION\; APPLICATION\; -->}},B)$. Note that ${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(B)$ can be created without the knowledge of $S^{\prime }$, because its all $A_i{S}_i$ terms are 0.

$$

5.

${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(B)-{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(A_i{S}_i+E_i)\right)$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(B-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(A_i{S}_i+E_i))$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(\mathrm{\Delta }M+E^{\prime })$ $▹$ where $E^{\prime }=E-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{E}_i$

$$

6.

If we explicitly expand the above relation,

${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(B)-{\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(A_i{S}_i+E_i)\right)$

$=(\stackrel{k^{\prime }}{\overbrace{0,0,\dots <!--\; FUNCTION\; APPLICATION\; -->}},B)-(\stackrel{k^{\prime }}{\overbrace{A_0^{\prime },A_1^{\prime },\dots <!--\; FUNCTION\; APPLICATION\; -->,A_{k^{\prime }-1}^{\prime }}},B^{\prime })$ $▹$ where $B^{\prime }=\underset{i=0}{\overset{k^{\prime }-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{A}_i^{\prime }{S}_i^{\prime }+\sum _{i=0}^{k-1}{A}_i{S}_i+\sum _{i=0}^{k-1}{E}_i$

$(\stackrel{k^{\prime }}{\overbrace{-A_0^{\prime },-A_1^{\prime },\dots <!--\; FUNCTION\; APPLICATION\; -->,-A_{k^{\prime }-1}^{\prime }}},B-B^{\prime })$

$$

The decryption of the above ciphertext gives us:

${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }^{-1}((\stackrel{k^{\prime }}{\overbrace{-A_0^{\prime },-A_1^{\prime },\dots <!--\; FUNCTION\; APPLICATION\; -->,-A_{k^{\prime }-1}^{\prime }}},B-B^{\prime }))$

$=B-B^{\prime }-\underset{i=0}{\overset{k^{\prime }-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}-A_i^{\prime }{S}_i^{\prime }$

$=B-\underset{i=0}{\overset{k^{\prime }-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{A}_i^{\prime }{S}_i^{\prime }-\sum _{i=0}^{k-1}{A}_i{S}_i-\sum _{i=0}^{k-1}{E}_i+\sum _{i=0}^{k^{\prime }-1}{A}_i^{\prime }{S}_i^{\prime }$

$=B-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{A}_i{S}_i-\sum _{i=0}^{k-1}{E}_i$

$=\mathrm{\Delta }M+E-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{E}_i$

$=\mathrm{\Delta }M+E^{\prime }\approx \mathrm{\Delta }M+E$ $▹$ where $E^{\prime }=E-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{E}_i$

Strictly speaking, $B-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{A}_i{S}_i=\mathrm{\Delta }M+E+\mathit{𝐾𝑞}$ where $K$ is a polynomial representing the wrap-around coefficient values as multiples of $q$. However, since all the above computations are done in modulo $q$, the $\mathit{𝐾𝑞}$ term gets eliminated.

$$

7.

Thus, $(0,0,\dots ,B)-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}⟨{\mathsf{\text{𝖣𝖾𝖼𝗈𝗆𝗉}}}^{\beta ,l}(A_i),{\mathrm{𝐾𝑆𝐾}}_i⟩={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(\mathrm{\Delta }M+E^{\prime })\approx {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(\mathrm{\Delta }M+E)$

${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(\mathrm{\Delta }M+E^{\prime })$ is an encryption of plaintext $\mathrm{\Delta }M$ with the plaintext scaling factor 1. However, we can re-interpret this ciphertext as an encryption of plaintext $M$ with the plaintext scaling factor $\mathrm{\Delta }$. This way, we can recover the ciphertext’s original scaling factor $\mathrm{\Delta }$ without any additional computation.

□