本质
BGV方案里面的key-swith的本质是在已有$s_A, s_B, (c_0^A,c_1^A)$并且$s_A,s_B$保密的基础上，构造出$(c_0^B,c_1^B)$，使其满足：
$$ \left[\left[c_0^A+s_A\cdot c_1^A\right]_Q\right]_P=\left[\left[c_0^B+s_B\cdot c_1^B\right]_Q\right]_P $$充分条件是：
（1）$c_0^B+s_B\cdot c_1^B\equiv c_0^A+s_A\cdot c_1^A+Pv(\text{mod}\;Q)$
（2）$\left|v\right|\leq \frac{Q-P}{2P}-\left|e_A\right|$
key-switch的几种构造方式本质都是在不断缩小$\left|v\right|$的上界，
high level
用$s_B$加密$s_A$即$ks_{A\rightarrow B}=(\left[s_A+a\cdot s_B+Pe_{ks}\right]_Q,-a)\in \mathcal{R}_Q^2$，称$ks_{A\rightarrow B}$是从$s_A$到$s_B$的切换密钥（公钥）。
令$c^B=(\left[ c_0^A+c_1^A\cdot ks^{A\rightarrow B}_0\right]_Q,\left[c_1^A\cdot ks^{A\rightarrow B}_1\right]_Q)$，则
$$ \begin{aligned} c_0^B+c_1^B\cdot s_B& = c_0^A+c_1^A\cdot ks^{A\rightarrow B}_0+c_1^A\cdot ks^{A\rightarrow B}_1\cdot s_B\\ &=c_0^A+c_1^A\cdot s_A+Pc_1^A\cdot e_{ks}\\ &\equiv m+P(e_A+c_1^A\cdot e_{ks})(\text{mod}\;Q) \end{aligned} $$只要保证$\Vert e_A+c_1^A\cdot e_{ks} \Vert_{\infty}\leq\Vert e_A\Vert_{\infty}+\Vert c_1^A\cdot e_{ks} \Vert_{\infty} \leq \frac{Q-P}{2P}$，则密钥切换成功。
但是$\Vert c_1^A\cdot e_{ks}\Vert_{\infty}\leq N \Vert c_1^A\Vert_{\infty}\Vert e_{ks}\Vert_{\infty}\leq \frac{NQB_{ks}}{2}$，因此有很大概率超出界，所以我们需要想办法降低$\Vert c_1^A\cdot e_{ks}\Vert_{\infty}$。
下面介绍几种key-switch的具体构造方式，均参考自1。
BV11
GHS
HYBRID
重线性化
重线性化技术是在处理密文乘法时提到的，对于密文乘法我们有
$$ c^1\cdot c^2=(c_0^1+s\cdot c_1^1)\cdot(c_0^2+s\cdot c_1^2)=c_0^1\cdot c_0^2+(c_0^1\cdot c_1^2+c_1^1\cdot c_0^2)\cdot s+(c_1^1\cdot c_1^2)\cdot s^2\\ \left[c^1\cdot c^2\right]_Q=\left[(m_1+Pe_1)(m_2+Pe_2)\right]_Q=\left[m_1m_2+P(m_1e_2+m_2e_1+Pe_1e_2)\right]_Q $$令$d_0=c_0^1\cdot c_0^2,d_1=c_0^1\cdot c_1^2+c_1^1\cdot c_0^2,d_2=c_1^1\cdot c_1^2$，则
$$ \left[d_0+d_1\cdot s+d_2\cdot s^2\right]_Q=\left[m_1m_2+P(m_1e_2+m_2e_1+Pe_1e_2)\right]_Q $$如果$\left|m_1e_2+m_2e_1+Pe_1e_2\right|\leq \frac{Q-P}{2P}$，则
$$ \left[\left[d_0+d_1\cdot s+d_2\cdot s^2\right]_Q\right]_P=\left[m_1m_2\right]_P $$这样就可以把$(d_0,d_1,d_2)$看做是$\left[m_1m_2\right]_P$的密文。
噪声上界估计：
$$ \Vert m_1e_2+m_2e_1+Pe_1e_2\Vert_{\infty}\leq \frac{P}{2}(e^1_b+e^2_b)+ne^1_be^2_b $$重线性化的本质是在已有$s_B,(d_0^A,d_1^A,d_2^A)$并且$s_B$保密的基础上，构造出$(c_0^B,c_1^B)$，使其满足：
$$ c_0^B+s_B\cdot c_1^B \equiv d_0^A+s_B\cdot d_1^A+s_B^2\cdot d_2^A+Pv(\text{mod}\;Q)\\ \left|v\right|\leq \frac{Q-P}{2P}-\left|e_A\right| $$令$c_1^B=c_1^{B'}+d_1^A,s_A=s_B^2$，则只需要构造出$(c_0^B,c_1^{B'})$，使其满足：
$$ c_0^B+s_B\cdot c_1^{B'} \equiv d_0^A+s_A\cdot d_2^A+Pv(\text{mod}\;Q)\\ \left|v\right|\leq \frac{Q-P}{2P}-\left|e_A\right| $$此时就可以看做正常的key-switch操作了，唯一的区别在于噪声上界由上面的三者确定而不是下面的两者确定，这是因为上面的三者有确定的明文形式，而下面的两者没有实际明文对应。
噪声上界估计：
$$ \Vert e_B\Vert_{\infty}=\Vert v+e_A\Vert_{\infty}\leq \Vert v\Vert_{\infty}+\frac{P}{2}(e^1_b+e^2_b)+ne^1_be^2_b $$因此密钥切换后的噪声会有所增加，且增加项为$\left|v\right|$。
进行乘法的两个密文的噪声上界分别为$e_b^1,e_b^2$，但是重线性化的乘积密文噪声上界增大到$\Vert v\Vert_{\infty}+\frac{P}{2}(e^1_b+e^2_b)+ne^1_be^2_b$。
显然，这个噪声上界有很大的概率接近解密上界即$\frac{Q-P}{2P}$，因此需要降噪，这里BGV使用了Mod Switch的方法来进行处理，可以参考上一篇博客内容。
此时有两种思路，（1）先分别进行Mod Switch，再进行重线性化；（2）先进行重线性化再进行Mod Switch。
如果是把模qR的密文通过Mod Switch变成模q的密文，那么噪声上界将从$e_b$变为$\frac{e_b}{R}+\frac{\sqrt{Nw(s)}}{2}$，其中$w(s)$是私钥的非零元素个数。
单纯从噪声角度看，（1）的噪声近似为$\frac{Ne^1_be^2_b}{R^2}+\frac{N^2w(s)}{4}$，（2）的噪声近似为$\frac{Ne^1_be^2_b}{R}$。这里不确定$N,R,e$三者取值，不好比较。
从计算角度看，（1）似乎比（2）增加了一个Mod Switch操作，前者的重线性化操作处理的模数要比后者低，并且重线性化的时间要显著高于Mod Switch操作，因此（1）的计算性能不会显著低于（2）。
因为，没有具体数值，所以目前无法得到哪种方法更好。但是看到很多开源库里面似乎都使用了第二种方法。
此外，重线性化技术本身可以看做key-switch的一个推广特例。
未来计划
- 结合安全性、噪声和性能分析参数设计方法
- 分析simd下的旋转操作如何加速
- 分析自举操作