同态加密原理解析

1.数学介绍

同态加密方案基于一个难以计算的问题Ring Learning with Errorsred。这些方案中的数据在加密和未加密时都用多项式表示。

这里举一个简单的多项式：$$4x^2+2x+1$$ 注意，其中的系数都是整数并且每个系数都会 $modt$。 假设 $t=24$ ,如下图所示 $21+6=3mod24$。

或者我们可以将范围变为$[-11,12]$，这样方便我们取负数。

我们定义了一个特殊的多项式，称为多项式模数，并且只考虑多项式在被这个多项式模数除后的余数。在FV方案中，这个多项式模数的具体形式是$x^d+1$，其中 $d=2^n$，$n$为某个整数。这里我们举例说明取 $n=4$，因此这个多项式是$x^{16}+1$

因为我们只考虑关于$x^{16}+1$后的余数，所以余数的中的多项式取值范围便为$[x^0，x^{15}]$，下面便是我们需要考虑的余数：$$a_{15}{x}^{15}+a_{14}{x}^{14}+a_{13}{x}^{13}+a_{12}{x}^{12}+a_{11}{x}^{11}+a_{10}{x}^{10}+a_9{x}^9+a_8{x}^8+a_7{x}^7+a_6{x}^6+a_5{x}^5+a_4{x}^4+a_3{x}^3+a_2{x}^2+a_1{x}^1+a_0$$
其中系数$a_i$的取值范围为 { 0 , t − 1 } \{0,t-1\} {0,t−1}，也就是说这里面的每个系数都会被 $modt$，我们可以用系数环面来说明，如下所示:
在该图中每个环代表一个$x^i$可以拥有24种系数的中一个。绿点代表系数为0。

假设当我们让 $2x^{14}and{x}^4$ 相乘,同时 $mod{x}^{16}+1$，将这个项（如下图中的红点所示）向前绕着环体旋转4个幂次，然后将值反射到0点的另一侧，变成了$22x^2$。这个只是为了直观展示，方便后面的讲解，当然你也可以使用多项式除法进行计算，结果相同。

2.使用多项式环进行加密

2.1 私钥和公钥的产生

我们首先定义$d=16,t=7,q=874$,那么多项式的模便为$x^{16}+1$

对于密钥或者私钥$s$，我们产生一个系数为 { − 1 , 0 , 1 } \{-1,0,1\} {−1,0,1}中的一个的随机多项式：$$s=x^{15}-x^{13}-x^{12}-x^{11}-x^9+x^8+x^6-x^4+x^2+x-1$$

接下来我们产生一个公钥，使用密文空间中的随机多项式，其中系数 $modq$ $$a=42x^{15}-256x^{14}-393x^{13}-229x^{12}+447x^{11}-369x^{10}-212x^9+107x^8+52x^7+70x^6-138x^5+322x^4+186x^3-282x^2-60x+84$$

我们还定义了一个误差多项式，从离散高斯分布中提取出的“小”系数。这个多项式在这里只使用一次，然后被丢弃。$$e=-3x^{15}+x^{14}+x^{13}+7x^{12}-6x^{11}-6x^{10}+x^9+4x^8-x^6+3x^5-4x^4+4x^3+4x+1$$

公钥是由一对多项式组成 $pk=([-as+e{]}_q,a)$,多项式算术取多项式的模，系数算术取$q$的模。

下面举一个例子，公钥的第一个多项式将这样构建

$$p{k}_0=-285x^{15}-431x^{14}-32x^{13}+86x^{12}-83x^{11}-142^{10}-41x^9+430x^8+26x^7-158x^6-281x^5+377x^4+110x^3-234x^2-113x+252$$

系数取值范围为 { 0 , q − 1 } \{0,q-1\} {0,q−1}的多项式 $a$ ,与系数取值范围为 { − 1 , 0 , 1 } \{-1,0,1\} {−1,0,1}的多项式$s$ 相乘，由于多项式乘法相对于多项式模数的“旋转和反射”特性，这有效地混合和打乱了 $a$ 的所有系数，并且还进一步添加了小误差项 $e$ 。多项式 $a$ 有效地掩盖了公钥中的私钥 $s$ 。

2.2 加密

加密便是将一个多项式且其系数 $modt$ 的明文，将它转化为一对系数 $modq$ 的多项式。这里我们举一个例子：$m=3+4x^8=3-3x^{8}mod7$。

加密需要三个小多项式。两个误差多项式取自与公钥误差多项式相同的离散高斯分布，另一个多项式我们称之为 $u$ ,它的系数为 { − 1 , 0 , 1 } \{-1,0,1\} {−1,0,1}，就像私钥一样。

密文由两个经计算后的多项式表示：

$$ct=([p{k}_{0}u+e_1+qm/t{]}_q,[p{l}_{1}u+e_2{]}_q)$$
消息 $m$ 是在模 $t$ 的范围，给它乘上 $\frac{q}{t}$ 将它的范围缩放到模 $q$ 上，再加上噪声与掩码。

$c{t}_0$,$c{t}_1$的计算结果如下，大家没事可以动手算一下。

总之一个密文可以由公钥，私钥，掩码，噪声，消息表示为：

2.3 解密

我们首先通过计算$[c{t}_0+c{t}_{1}s{]}_q$从消息中完全删除掩码。将计算结果扩展得$[qm/t+e_1+eu+e_{2}s{]}_q$，可以看到其中包含缩放后的消息和一些噪声，只要噪声不太大我们便可以通过舍入恢复消息。

具体来说

我们将该多项式重新缩放到模 $t$ 上，也就是乘上 $\frac{t}{q}$ ：

四舍五入这些系数便可以恢复我们的消息:$$m=3-3x^8$$

我们用下图 来进行说明：在缩放到最接近的整数后，我们将近似系数四舍五入，从而得到我们的信息:总之，我们通过下式来计算解密结果：$$m^{{}^{\prime }}=[\lfloor \frac{t}{q}[c{t}_0+c{t}_{1}s{]}_q\rceil {]}_t$$其中$\lfloor \rceil$表示取整最接近的整数。

3.同态计算

3.1 同态加法

假设我们有两个多项式 $m_{1}and{m}_2$，它们使用相同的公钥加密：$$a=([p{k}_0{u}_1+e_1+q{m}_1/t{]}_q,[p{k}_1{u}_1+e_2{]}_q)$$ $$b=([p{k}_0{u}_2+e_3+q{m}_2/t{]}_q,[p{k}_1{u}_2+e_4{]}_q)$$我们将a,b相加得到c：$$c=([p{k}_0{u}_3+e_5+q(m_1+m_2)/t{]}_q,[p{k}_1{u}_3+e_6{]}_q)$$缩放之前的解密：$$[q(m_1+m_2)/t+e_5+e{u}_3+e_{6}s{]}_q$$只要最后的噪声不太大，在缩放后被舍入掉，便可以得到正确的解密结果。

3.2 同态乘法

首先我们根据同态的解密公式得：$$[c{t}_0+c{t}_1{s}^1{]}_q$$注意：这个方程是一个多项式$(c{t}_0)$乘以1($s^0$)加上一个多项式$(c{t}_1)$乘以另一个多项式$(s^1)$，然后对 $x^d+1$ 取模，对 $q$ 取模。

现在，我们在上面看到解密产生了一个独立于掩码项 $au$ 的量 $noise$ $$[c{t}_0+c{t}_1{s}^1{]}_q\to \frac{t}{q}m+noise$$
我们现在考虑两个多项式 $m_{1}and{m}_2$ 使用相同的公钥加密：$$[a_0+a_1{s}^1{]}_q\to \frac{t}{q}{m}_1+n_1$$$$[b_0{+}_1{s}^1{]}_q\to \frac{t}{q}{m}_2+n_2$$
如果我们取它们的乘积，我们有:$$[a_0+a_1{s}^1{]}_q[b_0{+}_1{s}^1{]}_q\to (\frac{t}{q}{m}_1+n_1)(\frac{t}{q}{m}_2+n_2)$$
我们将左边展开:$$mult(a,b)=c_0+c_{1}s+c_2{s}^2$$其中$$c_0=[\frac{t}{q}{a}_0{b}_0{]}_q$$$$c_1=[\frac{t}{q}(a_1{b}_0+a_0{b}_1){]}_q$$$$c_2=[\frac{t}{q}{a}_1{b}_1{]}_q$$
最后的公式应该为：$$mult(a,b)=[\lfloor \frac{t}{q}[c_0+c_{1}s+c_2{s}^2]\rceil {]}_t$$

英文链接