灵山建设局网站,网站做专题页面,index放WordPress哪个目录,vs2010做网站时间控件学习资源#xff1a; 全同态加密I#xff1a;理论与基础#xff08;上海交通大学 郁昱老师#xff09; 全同态加密II#xff1a;全同态加密的理论与构造#xff08;Xiang Xie老师#xff09; 现在第二代#xff08;如BGV和BFV#xff09;和第三代全同态加密方案都是基…学习资源 全同态加密I理论与基础上海交通大学 郁昱老师 全同态加密II全同态加密的理论与构造Xiang Xie老师 现在第二代如BGV和BFV和第三代全同态加密方案都是基于LWE构造的现在先进的全同态方案也都是基于LWE的所以本文总结一下LWE的基础知识。 首先考虑我们希望加密一个数 s s s 现在用一系列的 a i a_i ai对 s s s进行加密得到 a i s a_is ais实际上通过求解最大公约数GCD就能求解出 s s s。但是如果加上一个随机噪声 e i e_i ei得到 a i s e i a_ise_i aisei那么将难以求解出 s s s的值。这个过程就是我对LWE的简单理解所谓error就是一个noise。 全同态加密的计算过程分为三步密钥生成KeyGen、加密Enc、同态计算Eval、解密Dec。、
KeyGen 首先构造出如上的等式 s ⋅ A e s A e s\cdot A e sAe s⋅AesAe然后得到公钥pk − A -A −A和 s A e sAe sAe的拼接以及私钥sk s s s和1的拼接。于是得到pk和sk满足相乘后的结果是随机噪声e接近0。
Enc
加密用的公钥pkr是一个只包含0或1的随机向量m是待加密的信息放在向量的最低位上。
Dec
解密用的私钥sk和ct计算完内积后求mod 2得到解密结果。 正确性证明 sk和pk相乘得到2eKeyGen时满足的条件然后和r做内积得到一个很小的偶数噪声最终的结果就是m很小的偶数噪声于是通过mod 2就能将噪声消除得到解密结果m。这也就是为什么构造的噪声是2e而不是e我的理解就是希望通过构造偶数的随机噪声从而在解密时方便用mod 2的方式消除掉噪声。
安全性证明 当pk是伪随机的r具有足够高的熵也就是随机性很强时pk和pk乘r都是伪随机的。自然和带m的向量相加后加密结果也是伪随机的。 下面是Xiang Xie老师的公式化描述 加密公式密文c 公钥pk ✖️ 随机r 明文m 解密公式明文m 密文sk, 私钥sk mod q mod 2 在这个基础上再mod 2就能解密出明文m的值。只要噪声够小就能保证正确性。 这里有个需要区分的事情以上 P K ( A , b A s ′ 2 e ) PK(A, bAs2e) PK(A,bAs′2e)是BGV方案BFV则是 P K ( A , b A s ′ e ) PK(A, bAse) PK(A,bAs′e)区别是BGV将信息编码在低位而BFV将消息编码在高位学习BFV的时候会说明。
Eval加法同态和乘法同态 注意到同态加法或乘法都会带来显著的噪声累积并且乘法是呈平方增长趋势。 然后说说如何解密同态乘的结果下面的式子可以看到两个密文做乘法等价于密文和私钥分别先做tensor product然后再做内积。因此显然密文和私钥的大小都翻了一倍。Example是一个等价性的证明。 那么问题来了如何将同态乘之后的密文大小和私钥大小都恢复回去呢这就是Key Switching解决的问题。
下面是Xiang Xie老师的描述 Key Switching
目标是将密文和私钥的大小恢复到线性大小。 现在求密文c1和c2的乘法 以上过程基于比特分解这个概念 下面是Xiang Xie老师的描述
Key Switching的目标将私钥 s ~ \tilde s s~下的 c ~ \tilde c c~ 转换为 私钥 s s s下的 c c c并且 c ~ \tilde c c~和 c c c都是加密的同一个明文。 这里有一个核心概念是Key Switching Key (KSK)也就是用私钥 s s s来加密 s ~ \tilde s s~。 通过Key Switching过程可以推导出私钥从 s ⊗ s s\otimes s s⊗s变成了线性的 s s s同时密文从 c ~ \tilde c c~变成了线性的 c c c。并且通过最后一行式子可以看出Key Switching后的 ⟨ c , s ⟩ \langle c, s\rangle ⟨c,s⟩和原来的 ⟨ c ~ , s ⊗ s ⟩ \langle \tilde c, s\otimes s\rangle ⟨c~,s⊗s⟩之间相差了一个噪声 2 c ~ T e ~ 2\tilde c^T\tilde e 2c~Te~这部分是可以非常大的所以到这里仍然没办法实现Key Switching。
这里引入了一个Gadget矩阵G 于是Key Switching的过程变成了下面这样 此时增加的误差就非常小了。 总结一下就是通过Key Switching原来私钥 s ~ s ⊗ s \tilde ss \otimes s s~s⊗s下的 c ~ c ⊗ c \tilde cc\otimes c c~c⊗c被转换成了私钥 s s s下的 c c c注意Key Switching后的 s , c s, c s,c都不是原来的值了double check。 对于BGV加法的噪声线性增长乘法的噪声平方增长Key Switching虽然可以支持乘法了限制sk变得特别大但是实际上噪声是在原本乘法噪声基础上加了一个很小的噪声总体也非常大。因此需要进一步降低这个噪声。
Modulus Reduction 到这里通过LWE实现了很小深度的同态乘法和加法计算key switching则是对每层用新的密钥但是随着计算深度加深噪声的扩大是爆炸性的因此还不是一个levelled FHE能计算指定深度的FHE。 现在我们希望不借助bootstrapping实现一个能计算一定深度的FHE需要用到模数变换。 暂时没太看懂中间的流程简而言之就是将密文c从模q的域变换到模p的域上pq于是噪声等比例缩小也就是大约缩小到原来的p/q倍。 下面是一个具体的例子 如果不做Modulus Reduction随着深度加深噪声呈双指数趋势增长level 3之后就会带来解密错误。 如果每个level上做Modulus Reduction那么噪声也会被维持在一个绝对值范围内代价就是模数会不断减小。 所以要想实现一个levelled FHE可以设置一个模数 B d B^d Bd然后就可以计算一个深度为 d d d的电路了其中 B B B是刷新后密文的噪声上界。计算完 d d d的深度后模数应该是降低到 B B B要保证此时解密不出错。BGV就是一种levelled FHE。
