[区块链] 同态加密中的一些技术概念

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 区块链 -> 同态加密中的一些技术概念 -> 正文阅读

[区块链]同态加密中的一些技术概念

再线性化

用于解决密文乘法导致密文长度增长的问题。

在LWE同态方案中，LWE加密算法具有天然的加法同态，为了使得其再满足乘法同态，将密文乘法定义为密文的张积，用对应的密钥的张积进行解密，将会使得结果满足乘法同态性。但这样的结果是每次乘法将会导致密文长度增加，如果LWE密文长度为 $n$ ，那么每次乘法后密文都会增长 $n^2/2$ ，因此需要解决密文长度增加的问题。

方案大致是，将解密函数表示为一个关于密文 $c$ 的一个多变元多项式 $f_{sk}(c)$ ，其中 $c$ 的各项是该多项式的变元，密钥 $s k$ 的各项是多项式的系数。密文乘法之后，密钥中的各项次数会从1次变为2次，如 $s=(s_1,s_2)$ ，同态乘法后将变为 $s\otimes s = (s_1s_1,s_1s_2,s_2s_1,s_2s_2)$ ，此时用一个长度与 $s$ 长度相同的新密钥 $t$ 对 $\otimes s$ 中的各项加密，就可以将“2次”密钥转化为“1次”密钥，从而得到一个新的密文，长度与原密文相同，且使用 $t$ 对新密文解密和使用 $\otimes s$ 对密文 $c_1 \otimes c_2$ 解密结果一样。

维数-模约减

用于压缩解密电路的深度，得解密电路深度大于有限次同态加密的电路深度。

我们知道，同态加密方案中，要使用同态解密达到控制噪声的话，解密电路的深度需要小于同态加密的电路深度（噪声上限所允许的电路深度），就是要达到同态解密之后还能再进行同态运算，这样就可以一次同态运算接着一次同态解密运算来达到“全同态”。
若将在再线性化中，将新密钥 $t$ 的长度取为比正常密文长度小，就能获得更小长度的密文，同时如果再进一步将新密钥的模取为比正常密文的模更小，就可以实现降低解密电路深度。

密钥交换

是再线性化技术的优化版本，该技术用于控制密文维数的增长，实际上是一个高维向量与高维矩阵的乘积。
给出维数是 $n_1$ 的密文 $c_1$ 和密钥 $s_1$ ，以及其目标密钥 $1,s_2)$ （维数是 $n_2+1$ ），输出结果是密文 $c_2$ ，对应密钥是 $1,s_2)$ ，两个密文对应的明文是一样的，如果让 $1,s_2$ 的维数小于 $s_1$ 的，那么就能在密文乘积后约减密文的维数，转换为正常的密文维数。

模交换（Modulus Switching）

该技术用于约减密文里的噪声，管理噪声的增长。
假定密文初始噪声为 $B$ ，去模 $\approx B^k$ （也就是噪音上限）。经过一次乘法电路后噪声增加为 $B^2$ ，通过 $\log k$ 层乘法后，噪声达到上限。如果采用模交换技术，每次乘法之后对密文除以 $B$ ，对 $B^2$ 来说相当于把它约减回 $B$ ，同时将密文长度缩小为原来的 $1/ B$ ，则新密文的模变为 $q / B$ 。依次下去，每次噪声都被“拉回”原来的大小 $B$ ，而模依次递减形成一个由高到低的阶梯型， $q/B^2,q/B^3,\cdots,q/B^{k-1}$ ，这样可以执行的乘法深度就近似为 $k ? 1$ ，对比 $\log k$ ，能够实现的深度呈指数级提高。

Bootstrapping

该技术主要是用来刷新密文噪声。
把一个满噪音的FHE的密文加密进另一个FHE密文中，并且同态计算FHE的解密算法，把里层的密文解密还原为原文，就能获得一个全新的低噪音FHE密文。

一次bootstrapping的过程

首先生成多组密钥（以两组为例） $pk_1,sk_1),(pk_2.sk_2)$
假定明文为 $m$ ，首先用第一组密钥进行加密得到 $Enc_{pk_1}(m)$ ，初始得到的噪声很低，随着不断的同态计算将得到一个达到噪声临界值的密文 $C_{f(m)} = Enc_{pk_1}(f(m))$ ，也就是说如果再进行一次同态计算就将导致解密失败。
接着，将这个密文用 $pk_2$ 进行加密得到 $Enc_{pk_2}(C_{f(m)})$ 。
然后使用一个加密后的密钥 $Enc_{pk_2}(sk_1)$ ，使用 $Enc_{pk_2}(C_{f(m)})$ 和 $Enc_{pk_2}(sk_1)$ 进行同态运算 $Dec_{sk_1}(C_{f(m)})$ 。这样一来可以得到 $Enc_{pk_2}(Dec_{sk_1}(C_{f(m)})) = Enc_{pk_2}(C_{f(m)})$ ，这样一来，当前的噪声已经不是达到限度的那个噪声了，而是一次同态运算后产生的新的噪声，也就变相的削弱了噪声。

同理，可以继续嵌套这个过程，等到每一波同态计算噪音极限后，再次Bootstrapping来计算更复杂的函数。
当然，这里存在一个小缺点，那就是在生成参数的时候需要事先准备好Bootstrapping的链条，即生成公钥私钥对 ${pk_i,sk_i\}$ ，并且公开对应的私钥 $sk_i$ 加密在下的密文 $pk_{i+1}$ 。所以作为第三方，我们仍然不能计算任意深度的电路，因为计算的深度在进行公共参数生成的阶段已经被决定好了。
解决方案可以使用循环密钥，以双密钥的系统来说 $pk_1,sk_1),(pk_2.sk_2)$ ，同时公开在 $pk_2$ 加密下的 $sk_1$ 和 $pk_1$ 加密下的 $sk_2$ ，然后无限循环即可。