一种高效的同态加密方案及其应用-解读 - PamShao

阅读paper"一种高效的同态加密方案及其应用"的笔记。

基础#

生成可逆矩阵对的算法#

• 输入：矩阵维数
• 输出：一对互逆矩阵(I1,I2)

算法的目的是构造一对互逆矩阵, 同时由于每一步中的置换参数都是随机生成的, 所以可使矩阵的
元素不具备任何特征, 可以通过改变随机变换的次数来调整效率和随机性.

密钥交换技术#

来源于BGV方案，作用是将一组密文 - 私钥转换到一组新的密文 -私钥, 同时保证解密正确性.

• 输入：密钥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困难问题上