阅读paper"一种高效的同态加密方案及其应用"的笔记。
算法的目的是构造一对互逆矩阵, 同时由于每一步中的置换参数都是随机生成的, 所以可使矩阵的
元素不具备任何特征, 可以通过改变随机变换的次数来调整效率和随机性.
来源于BGV方案，作用是将一组密文 - 私钥转换到一组新的密文 -私钥, 同时保证解密正确性.
假设原始的密钥和密文为(S)和(c)，则经过密钥交换后输出满足：新密钥和新密文为(S')和(c'=Mc+e approx Mc)，其中(e)很小可以忽略，可以看出密钥交换产生的新密文，噪音增加了一点。
其中(I)是(m*m)的单位矩阵。
其中，矩阵(wI)视为明文向量对应的私钥进行了一次密钥转换, 得到公、私钥，所以，假设(wI)对应的明文为(c)，(S')对应的明文为(c'=Mc)，则：
(w)是什么？也是参数？
加密过程中除计算新密文外, 还引入了一个噪声向量, 从而使得加密结果形式上满足 LWE 问题.
其中(left lceil aright rfloor_q)表示对向量或矩阵(a)中各元素在模(q)的域中取最近整数.（四舍五入）。
为保证解密的正确性, 需要对算法中的各参数做出限制. 下面分析解密过程:
要保证解密正确性需要限制(|Se/w|< 1/2) , 其中符号(|a|)表示向量或矩阵(a)的元素的最大绝对值. 将该限制条件进一步加强, 然后展开得到:
所以噪声(e)的上限：
在该限制条件下, 可以保证解密正确. 在实际应用中, 噪声往往会随着同态计算的进行而不断增大, 而
当噪声足够大时, 就会造成解密失败. 所以在实际应用中, 可以噪音上限的公式中, 得到一个密文可
以进行的同态计算深度(L), 然后再应用中加以限制, 以此来保证同态计算的结果可以顺利解密.（Leveled-FHE）。
1、用同一公钥(M)加密两个等长的明文向量(x_1,x_2)有:
2、将上面两式相加有:
只需给噪声向量 (e_1, e_2)合适的限制条件即可得到:
只要满足：(|S(e_1+e_2)|<1/2)，就可以解密正确。
线性变换：给定整数(x)，输出(Gx)，其中(G)是一个矩阵/向量/整数等，那么如何设计：(Dec(Gc)=Gx)
1、根据解密结构(x=left lceil Sc/wright rfloor_q)可得:(Gx=Gleft lceil Sc/wright rfloor_q=left lceil GSc/wright rfloor_q=Dec(GS,c))，即密文(c)可以看作是明文(Gx)在公钥(GS)下加密的。
2、然后利用密钥交换技术，将(GS)作为输出，得到新密钥(S')，及(M'=Trans(GS))，此时(S')对应的新密文为(c'=M'c+e')，根据密钥交换的性质有：
3、用新密钥(S')对新密文解密：
可以看出上面的噪音不仅有第一次加密时引入的噪声(e), 还有密钥转换过程中引入的新噪声(e')以及因进行线性变换而引入的噪声(|GSe+S'e'|). 将上面解密过程展开有:
所以解密正确的条件是：
随着计算深度的增加噪声的大小也快速增大, 直至无法正确解密.
总结一下流程：
现在给出一个密文(c)，想计算其线性变换(Gc)，然后解密后相当于对应的明文(x)做线性变换(Gx)：
1、将密文(c)，对应的私钥(S)，变为(GS)，作为密钥交换的输入
2、密钥交换输出新私钥(S')，得到新密文(c')
3、用新私钥(S')解密新密文(c')得到明文(Gx)
什么是加权内积？
两向量内积:(<X,Y>=x_1y_1+x_2y_2+...+x_ny_n)
两向量加权内积：(<X,Y,H>=x_1y_1h_1+x_2y_2h_2+...+x_ny_nh_n)，其中(H)是权值向量
关于加权内积没看太懂。
回想方案的公私钥{(M,S)}
密钥安全就是不能根据公钥(M)推测出私钥(S)或者在一定程度上模拟出解密过程，即不能仅从公钥和密文就可以解出明文！
观察公钥(M=P_mM_t)，是否能从(M)中推断出(P_m)或者(M_t)?
因为(P_m)是一个随机可逆矩阵，想直接构造出(P_m)是困难的。可行的办法就是(P_m^{-1}M=M_t)，即需要知道(P_s)，可以尝试随机取(P_s)，但矩阵规模很大时，很难选取，所以选择合适的矩阵规模，是影响方案安全性的重要参数。
模拟方案是否满足IND-CPA（不可区分的选择明文攻击）：
若攻击者能以概率为(Pr=1/2+varepsilon)获胜，则攻击者同样也可以以相同的概率求出(x)：
已知$ c_i,M_i,c_i=M_ix+e_i,0 leq i<n$
该问题明显就是LWE问题了，LWE问题被Regev证明是困难的，所以该方案的安全性规约到LWE困难问题上
