阅读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/)，则：
/(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困难问题上
