阅读paper"一种高效的同态加密方案及其应用"的笔记。
基础#
生成可逆矩阵对的算法#
- 输入：矩阵维数
- 输出：一对互逆矩阵(I1,I2
I1,I2 )
算法的目的是构造一对互逆矩阵, 同时由于每一步中的置换参数都是随机生成的, 所以可使矩阵的
元素不具备任何特征, 可以通过改变随机变换的次数来调整效率和随机性.
密钥交换技术#
来源于BGV方案，作用是将一组密文 - 私钥转换到一组新的密文 -私钥, 同时保证解密正确性.
- 输入：密钥S
S - 输出：新密钥S′和矩阵M
假设原始的密钥和密文为S和c，则经过密钥交换后输出满足：新密钥和新密文为S′和c′=Mc+e≈Mc，其中e很小可以忽略，可以看出密钥交换产生的新密文，噪音增加了一点。
正确性#
其中I是m∗m的单位矩阵。
同态方案#
密钥生成#
- 输入：参数m
- 输出：私钥S和公钥M
其中，矩阵wI视为明文向量对应的私钥进行了一次密钥转换, 得到公、私钥，所以，假设wI对应的明文为c，S′对应的明文为c′=Mc，则：
w是什么？也是参数？
加密#
- 输入：公钥M，明文x
- 输出：密文c
加密过程中除计算新密文外, 还引入了一个噪声向量, 从而使得加密结果形式上满足 LWE 问题.
解密#
- 输入：私钥S，密文c
- 输出：明文c
其中⌈a⌋q表示对向量或矩阵a中各元素在模q的域中取最近整数.（四舍五入）。
解密正确性的参数要求#
为保证解密的正确性, 需要对算法中的各参数做出限制. 下面分析解密过程:
要保证解密正确性需要限制|Se/w|<1/2 , 其中符号|a|表示向量或矩阵a的元素的最大绝对值. 将该限制条件进一步加强, 然后展开得到:
所以噪声e的上限：
在该限制条件下, 可以保证解密正确. 在实际应用中, 噪声往往会随着同态计算的进行而不断增大, 而
当噪声足够大时, 就会造成解密失败. 所以在实际应用中, 可以噪音上限的公式中, 得到一个密文可
以进行的同态计算深度L, 然后再应用中加以限制, 以此来保证同态计算的结果可以顺利解密.（Leveled-FHE）。
同态计算#
加法#
1、用同一公钥M加密两个等长的明文向量x1,x2有:
2、将上面两式相加有:
只需给噪声向量 e1,e2合适的限制条件即可得到:
只要满足：|S(e1+e2)|<1/2，就可以解密正确。
线性变换#
线性变换：给定整数x，输出Gx，其中G是一个矩阵/向量/整数等，那么如何设计：Dec(Gc)=Gx
1、根据解密结构x=⌈Sc/w⌋q可得:Gx=G⌈Sc/w⌋q=⌈GSc/w⌋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>=x1y1+x2y2+...+xnyn
两向量加权内积：<X,Y,H>=x1y1h1+x2y2h2+...+xnynhn，其中H是权值向量
关于加权内积没看太懂。
安全性分析#
密钥安全#
回想方案的公私钥{M,S}
密钥安全就是不能根据公钥M推测出私钥S或者在一定程度上模拟出解密过程，即不能仅从公钥和密文就可以解出明文！
分析#
观察公钥M=PmMt，是否能从M中推断出Pm或者Mt?
因为Pm是一个随机可逆矩阵，想直接构造出Pm是困难的。可行的办法就是P−1mM=Mt，即需要知道Ps，可以尝试随机取Ps，但矩阵规模很大时，很难选取，所以选择合适的矩阵规模，是影响方案安全性的重要参数。
语义安全#
模拟方案是否满足IND-CPA（不可区分的选择明文攻击）：
若攻击者能以概率为Pr=1/2+ε获胜，则攻击者同样也可以以相同的概率求出x：
已知ci,Mi,ci=Mix+ei,0≤i<n
该问题明显就是LWE问题了，LWE问题被Regev证明是困难的，所以该方案的安全性规约到LWE困难问题上