基础 生成可逆矩阵对的算法阅读paper"一种高效的同态加密方案及其应用"的笔记。
- 输入：矩阵维数
- 输出：一对互逆矩阵(\(I_1,I_2\))
算法的目的是构造一对互逆矩阵, 同时由于每一步中的置换参数都是随机生成的, 所以可使矩阵的
元素不具备任何特征, 可以通过改变随机变换的次数来调整效率和随机性.
来源于BGV方案，作用是将一组密文 - 私钥转换到一组新的密文 -私钥, 同时保证解密正确性.
- 输入：密钥\(S\)
- 输出：新密钥\(S'\)和矩阵\(M\)
假设原始的密钥和密文为\(S\)和\(c\)，则经过密钥交换后输出满足：新密钥和新密文为\(S'\)和\(c'=Mc+e \approx Mc\)，其中\(e\)很小可以忽略，可以看出密钥交换产生的新密文，噪音增加了一点。
正确性
其中\(I\)是\(m*m\)的单位矩阵。
同态方案 密钥生成- 输入：参数m
- 输出：私钥\(S\)和公钥\(M\)
其中，矩阵\(wI\)视为明文向量对应的私钥进行了一次密钥转换, 得到公、私钥，所以，假设\(wI\)对应的明文为\(c\)，\(S'\)对应的明文为\(c'=Mc\)，则：
\[Sc'=SMc=wIc \to SM/w=I \]加密\(w\)是什么？也是参数？
- 输入：公钥\(M\)，明文\(x\)
- 输出：密文\(c\)
加密过程中除计算新密文外, 还引入了一个噪声向量, 从而使得加密结果形式上满足 LWE 问题.
- 输入：私钥\(S\)，密文\(c\)
- 输出：明文\(c\)
其中\(\left \lceil a\right \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/w\right \rfloor_q\)可得:\(Gx=G\left \lceil Sc/w\right \rfloor_q=\left \lceil GSc/w\right \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困难问题上