## 3 Building Block
### Optimizing the Key Switching
The matrix \(\mathbf{W_{s_{1}\to s_{2}}}\) with \((n_{2}+1)\) columns consists of the matrix \(-\mathbf{A_{s_{1}\to s_{2}}}\) with \(n_{2}\) columns and \(\mathbf{b_{s_{1}\to s_{2}}}\): \[\mathbf{W_{s_{1}\to s_{2}}}=\left[\mathbf{b_{s_{1}\to s_{2}}}\parallel-\mathbf{A_{s_{1} \to s_{2}}}\right]\in R_{Q}^{n_{1}\times(n_{2}+1)}\]
* SwitchKey\((\mathbf{W_{s_{1}\to s_{2}}},\mathbf{c_{s_{1}}})\) : To switch a ciphertext under a secret key \(\mathbf{s_{1}}\) to \((1,\mathbf{s_{2}})\), output: \[\mathbf{c_{s_{2}}}:=\left[\left\lfloor\frac{\mathbf{W_{s_{1}\to s_{2}}}^{\mathbf{\mathsf{ T}}}\cdot\mathbf{c_{s_{1}}}}{p}\right\rceil\right]_{q}.\]  
To ensure the security, the variance of \(\chi^{n_{1}}\) cannot be simply taken as the variance of \(\chi\), otherwise it will lead to great security losses. In Section 5, we prove that if for some real number \(k>0\), written as \(p\cdot q=q^{k}\), and suppose \(\left\lVert\chi\right\rVert<B\), we need \(\left\lVert\chi^{n_{1}}\right\rVert=B_{k}>\alpha^{1-\sqrt{k}}\cdot q^{k-\sqrt{ k}}\cdot B^{\sqrt{k}}\), where \(\alpha\) is a constant, e.g., \(\alpha\simeq 3.758\). The correctness and security are as shown below. **Lemma 6** (Correctness). : _Set \(\mathbf{s_{1}}\in R_{q}^{n_{1}}\), \(\mathbf{s_{2}}\in R_{q}^{n_{2}}\), \(\mathbf{c_{s_{1}}}\in R_{q}^{n_{1}}\) as arbitrary vectors of polynomials. Let \(\mathbf{W_{s_{1}\to s_{2}}}\leftarrow\mathrm{SwitchKeyGen}(\mathbf{s_{1}},\mathbf{s_{2}},p)\). Let \(\mathbf{c_{s_{2}}}\leftarrow\mathrm{SwitchKey}(\mathbf{W_{s_{1}\to s_{2}}},\mathbf{c_{s_{1}}})\). Then:_  
\[\left\langle\mathbf{c_{s_{2}}},(1,\mathbf{s_{2}})\right\rangle=\left\langle\mathbf{c_{s_{1}} },\mathbf{s_{1}}\right\rangle+r\;(\text{mod }q).\]  
_where \(\left\lVert r\right\rVert<\frac{q\cdot B_{k}\cdot\delta_{k}}{p}+\left(\delta_{ k}\cdot\left\lVert\mathbf{s_{2}}\right\rVert+1\right)/2\)._  
Proof. : Let \(\mathbf{e}:=\left(\frac{\mathbf{W_{s_{1}\to s_{2}  
Lemma 6 is proven. According to Lemma 6, we can choose \(p\) to minimize the error so that it is less than the error of the multiplication. Then, we must choose \(p\geq q^{3}\) when \(B\) is small and does not depend on \(q\). \(\square\)  
**Lemma 7** (Security): _Let \(\mathbf{s_{1}}\in R_{q}^{n_{1}}\) be the arbitrary vectors of polynomials. If \(\mathbf{s_{2}}\leftarrow\)_ RE.SecretKey \(\mathrm{Gen}\big{(}1^{\lambda}\big{)}\)_and_\(\mathbf{W}\leftarrow\mathrm{SwitchKeyGen}(\mathbf{s_{1}},\mathbf{s_{2}},p)\)_, then \(\mathbf{W}\) is computationally indistinguishable on \(R_{Q}^{n_{1}\times(n_{2}+1)}\), assuming that \(\mathrm{DRLWE}_{d,q,\chi}\) holds._  
According to the key switching process, \(\mathrm{SwitchKeyGen}(\mathbf{s_{1}},\mathbf{s_{2}},p)\), \(\mathbf{W}=[\mathbf{b}\parallel-\mathbf{A}]\in R_{Q}^{n_{1}\times(n_{2}+1)}\), where \(A\) is a uniform matrix, \(\mathbf{b}=[\mathbf{A}\cdot\mathbf{s_{2}}+\mathbf{e}+p\cdot\mathbf{s_{1}}]_{Q}\). Since each element of \(\mathbf{b}\) is the ciphertext of the RE encryption scheme, \(\mathbf{b}\) is indistinguishable from the uniform distribution \(U\big{(}R_{Q}^{n_{1}}\big{)}\). Therefore, \(\mathbf{W}\) is computationally indistinguishable from the uniform distribution on \(R_{Q}^{n_{1}\times(n_{2}+1)}\) and Lemma 7 is proven. \(\square\)