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⟩},\cdots 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\right)+A_{⟨i,2⟩}\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left({\displaystyle \frac{q}{{\beta }^2}}{S}_i\right)+\cdots +A_{⟨i,l⟩}\cdot {\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left({\displaystyle \frac{q}{{\beta }^l}}{S}_i\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\right)$

$={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }\left(\left(A_i\right)\cdot S_i\right)={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(A_i{S}_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))$

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

$$

4.

$B$ is equivalent to a trivial GLWE encryption with $S^{\prime }$, where its every $A_1,A_2,\cdots$ is 0. That is, ${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(B)=(\stackrel{k}{\overbrace{0,0,\cdots }},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)\right)={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(B-\underset{i=0}{\overset{k-1}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}(A_i{S}_i))={\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(\mathrm{\Delta }M+E)$

$$

6.

To 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)\right)$

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

$(\stackrel{k}{\overbrace{-A_0^{\prime },-A_1^{\prime },\cdots ,-A_k^{\prime }}},B-B^{\prime })$

$$

The decryption of the above ciphertext gives us:

${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }^{-1}((\stackrel{k}{\overbrace{-A_0^{\prime },-A_1^{\prime },\cdots ,-A_k^{\prime }}},B-B^{\prime }))$

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

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

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

$=\mathrm{\Delta }M+E-E^{\prime }\approx \mathrm{\Delta }M+E$

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

${\mathsf{\text{𝖦𝖫𝖶𝖤}}}_{S^{\prime },\sigma }(\mathrm{\Delta }M)$ is an encryption of plaintext $\mathrm{\Delta }M$ with the plaintext scaling factor 1. However, we can theoretically see this 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.

□