1、解密电路的深度

上面有一个人说对了一半，其实我们可以把解密电路用AND电路和XOR电路表出，计算一下电路的深度（电路的深度代表着运算的次数），然后再和permitted functions中功能电路所允许的最大深度做个比较，就知道解密电路是否属于permitted functions集合了。

首先来分析permitted functions集合所允许的电路深度。由于permitted functions集合里的任一功能函数f 都可以用AND电路和XOR电路表出，而AND电路和XOR电路可以看做对输入的二进制位做乘法和加法，所以f电路的深度可以用输入位的对称多项式来衡量（用多项式衡量是因为多项式里恰好是变元的乘法和加法），又由于乘法是噪音的主要来源，所以可以用多项式中乘法次数来做电路深度的主要衡量指标。有：

c* = f ( c1, c2, …，cn ) = f ( m1+2r1+pq, m2+2r2+pq, …，mn+2rn+pq )

  = f ( m1+2r1, m2+2r2, …，mn+2rn ) +p(……)

密文c*的噪音为：c* mod p = f ( m1+2r1, m2+2r2, …，mn+2rn ), 要想c*解密正确必须有：f ( m1+2r1, m2+2r2, …，mn+2rn )< p/2, 其中mi+2ri 是密文ci的噪音。不妨令mi+2ri = xi, 且xi < B, B是密文ci噪音的上界，则有：

f ( x1, x2, …，xn ) < p/2。

我们的目标是衡量f 的运算次数d，所以可以用初等对称多项式来表达f ，有：

f ( x1, x2, …，xn ) = x1x2…xd + x1x3…xd + ……；其中d<=n

f ( x1, x2, …，xn )的每一项就是从n个变元( x1, x2, …，xn )里选取d个变元，因此有C（n, d）个项（C表示组合运算），由C（n, d）< n^d 得：

f ( x1, x2, …，xn ) < B^d n^d < p/2  => d < log p / log Bn , 也就是说f 最多运算次数为 log p / log Bn 。

下面再看看解密电路的运算次数：

Dec(c):   (c mod p) mod 2=（c – p*「c/p」）mod 2 = Lsb(c) XOR Lsb(「c/p」)

仔细端详解密电路的公式，发觉其复杂性主要来源是c/p，所以我们主要看c/p所需的运算次数。c/p=c* p^-1 , p^-1是小数，为了保证c* p^-1取整之后的的精确度，p^-1要取log c 位的。例如 12345678 * 0.111111 和 12345678 * 0.11111111的结果取整后是不一样的。那么两个数相乘的次数如何衡量呢？有如下结论:

 乘两个t位数相当于加t个数: 输出位是关于输入位的一个2次多项式

a3   a2    a1

b3   b2    b1

a3b1  a2b1  a1b1

a3b2  a2b2  a1b2

a3b3 a2b3   a1b3

 

加t个数可以应用“3-for-2 trick” :3个数相加得到两个数相加，输出位是关于输入位的一个次数最多为2次的多项式

a3               a2         a1

b3               b2         b1

                c3               c2         c1

             a3+b3+c3         a2+b2+c2    a1+b1+c1

a3b3+a3c3+b3c3   a2b2+a2c2+b2c2   a1b1+a1c1+b1c1      一次

                               二次

那么t个数应用这个技巧经过log_3/2 t 次相加后得到两个数，输出位的次数为2^{log3/2 t} = t^{log3/2 2}= t^1.71。

再看两个t位数相加：

进位：a2b2+a2a1b1+b2a1b1      a1b1

a3               a2         a1

b3               b2         b1

  a3+b3+a2b2+a2a1b1+b2a1b1   a2+b2+a1b1    a1+b1

三次

输出位的次数最多为t次，因为上面3位数相加次数最多为3次。

 

结合起来有：乘两个t位数的次数最多为2t^1.71t=2t^2.71，而c* p^-1里c的位数为log c，p^-1要取log c 位的，又因为log c > log p (因为 p<c)，所以c* p^-1的次数至少是2(log p)^2.71 , 而前面说过f最多运算次数为 log p / log Bn，所以解密电路的深度要大于Evaluate所允许运行功能电路的深度，因此如果Evaluate运行解密电路的话，将会产生不正确的结果，我们就说Evaluate无法运行解密电路，换句话说解密电路不在permitted functions 集合里。

结论应该知道了吧，是一个坏消息。解密电路不在permitted functions 集合里，其后果就是：无法对密文进行任意功能的运算！与全同态失之交臂。

怎么办呢？古人云：兵来将挡，水来土掩。解密电路深了，把它变浅不就完了。说容易做起来有点难。我觉得有技巧的地方就在于压缩解密电路。

 

2、  压缩解密电路

如何把电路变浅呢？一个直观的方法就是替别人承担一些工作，这样原来的任务量就变小了。

还是先来仔细打量一下问题出在的地方：

c* p^-1

这是一个乘积，要想把它变成一个较浅的运算电路，应该如何做呢？最直观的方法就是：把乘积变成和，也就是说把c* p^-1 —》∑zi。c*是密文，我们不可能拿它开刀，唯一可以做处理的地方就是p^-1，也就是说应该把p^-1 转换成一个和的形式即： p^-1 —》∑yi，要知道p是私钥是不能公开的，所以可以把p隐藏在∑yi中，同时这种隐藏要不会泄露p才可行，所以要有一个陷门才可以，这个陷门就是Sparse Subset Sum Prob (SSSP)，就是给一串整数x1,x2,……，xn，存在一个{1,……，n}的子集S，使得∑si * xi=0 (其中i∈S)，让你求这个S是不可行的。这个问题据说是困难的，好像没有被well studied。有了这个陷门就可以构造出：

取y1,y2,…,yn ∈[0, 2)，存在一个稀疏子集S，使得∑si * yi ≈ 1/p mod 2 (i∈S) (因为是实数所以用近似等于1/p表示，是存在一个误差的，这个误差不影响取整后的结果) 。令 zi<—c*yi  mod 2，zi保留一定的精确度，从而有：∑si * zi ≈ c/p  mod 2。所以解密电路中的「c/p」可以替换成「∑si * zi 」。解密电路变成：

    Lsb(c) XOR Lsb(「∑si * zi 」)。

这个变换后的方案，公钥除了原来的公钥pk之外还多加了一个向量{yi}。密文除了原来的c之外多出了一个向量{zi}。这个多出来的zi可以看做是提前拿出来计算以减轻解密电路负担的，这个方法叫预处理（post-process）。私钥由原来的sk变成了{si}。可以看到公钥变大，密文也变大，这个代价就是为了换得更浅的电路。那么电路变浅了吗？下面来分析一下：

主要分析一下∑si * zi的多项式次数，然后和我们前面分析的f所能执行的最大次数比较就OK。

假设zi的精确度为n位（我们考虑的都是二进制表示），整数位只考虑最低位，因为Lsb(「∑si * zi 」)是对和先取整再取最低有效位。如下所示：

  a1,0 ·  a1,-1 …… a1,-(n-1)  a1,-n    ---------- s1*z1

  a2,0 ·  a2,-1 …… a2,-(n-1)  a2,-n    -----------s2*z2

  a3,0 ·  a3,-1 …… a3,-(n-1)  a3,-n

……        …………

  at,0  · at,-1 ……  at,-(n-1)  at,-n     -----------sn*zn

 

如果上述t个数应用“3-for-2 trick”相加，电路深度也不会满足要求。所以得另寻它法。

有个概念说一下：HammingWeight，海明重量通俗的说就是向量中“1”的个数，由于我们是二进制相加，所以上面每一列相加的结果可以看成是该列的海明重量。那么海明重量怎么求呢？有一个定理非常有用，就是：

对于任意一个二进制向量<a1,a2,……，at>，其海明重量为W，并且其二进制表示为;wn,……w1w0的话，则wi可以表示为关于变元a1,a2,……，at的一个次数是2ⁱ多项式。这个多项式很好求，就是对称多项式e₂ⁱ （a1,a2,……，at），有现成的算法。

好了我们可以对上面的那些列运用此定理。对最低列求海明重量，则海明重量的最低位是e₂⁰ （a1,-n, a2,-n ……，at,-n）mod 2，它就是该列的和，这个海明重量的倒数第二位是e₂¹ （a1,-n, a2,-n ……，at,-n）mod 2，就进位到倒数第二列记为Cn,-(n-1)，如此下去;

 

 

 Cn,0    Cn,-1       Cn,-(n-1)            -------- 进位

a1,0 · a1,-1 ……  a1,-(n-1)  a1,-n

  a2,0 ·  a2,-1 …… a2,-(n-1)  a2,-n

  a3,0 ·  a3,-1 …… a3,-(n-1)  a3,-n

……

  at,0  ·  at,-1 …… at,-(n-1)  at,-n

                                   b-n

 

最后得到：

  

  C-1,0

 …………

 Cn-1,0   Cn-1,-1……     

 Cn,0     Cn,-1      Cn,-(n-1)

a1,0 ·  a1,-1 …… a1,-(n-1)  a1,-n

  a2,0 ·  a2,-1 …… a2,-(n-1)  a2,-n

  a3,0 ·  a3,-1 …… a3,-(n-1)  a3,-n

……

  at,0  ·  at,-1 …… at,-(n-1)  at,-n

   b0      b-1 ……  b-(n-1)   b-n     

 

 

则有：

b=「∑si * zi 」= (b0 + b-1 ) mod 2  (因为是取整，所以只关心第0列，取整是要取最近的整数，所以和b-1有关，如果b-1是1则要进上去)

别忘了我们现在的任务是要计算「∑si * zi 」的电路关于ai,j的多项式次数。开始时可以看成都是一次的： 

a1,0 ·  a1,-1 …… a1,-(n-1)  a1,-n   deg=1 · deg=1…… deg=1 deg=1

a2,0 ·  a2,-1 …… a2,-(n-1)  a2,-n   deg=1 · deg=1…… deg=1 deg=1                                  

a3,0 ·  a3,-1 …… a3,-(n-1)  a3,-n   deg=1 · deg=1…… deg=1 deg=1

……        …………

at,0  · at,-1 ……  at,-(n-1)  at,-n    deg=1 · deg=1…… deg=1 deg=1

 

然后计算完最后一列，有了向前面各列的进位后,如下：

 

e₂ⁿ( )     e₂^n-1( )     e₂²( )         

deg=1 · deg=1…… deg=1 deg=1

deg=1 · deg=1…… deg=1 deg=1

deg=1 · deg=1…… deg=1 deg=1

……         ………………

deg=1 · deg=1…… deg=1 deg=1

 

每一列关于ai,j的次数都变了，例如倒数第二列次数为4了，依次下去：

 

e₂¹( )

……        ……

e₂^n-1( )  e₂^n-2( )……

e₂ⁿ( )    e₂^n-1( )  e₂¹( )         

deg=1 · deg=1…… deg=1 deg=1

deg=1 · deg=1…… deg=1 deg=1

deg=1 · deg=1…… deg=1 deg=1

……         ………………

deg=1 · deg=1…… deg=1 deg=1

 

 

 

因为最后的结果是(b0 + b-1 ) mod 2，所以我们只关心前面两列的次数（即第0列和第一列），显然最高次数为2ⁿ ，所以计算「∑si * zi 」的电路关于ai,j的多项式次数为2ⁿ（别忘了n是zi的精确度）。回忆一下我们原来说的f所能计算的最高多项式次数为：log p / log Bn （2ⁿ中的n和此式的n不是一个n）。如何比较呢，得把参数确定一下，按照DGHV方案中的参数，λ为安全参数，取||p|| ～λ², ||r||～λ，所以p～2^λ2，B～2^λ，则log p / log Bn～λ。要想让Evaluate能够运行「∑si * zi 」电路，zi的精确度要取logλ才可以。现在你知道DGHV论文中zi精确度为什么要取那个数了吧。

到此为止我们知道了解密电路经过压缩，可以被Evaluate正确运算了，从而解密电路堂而皇之的进入permitted functions集合里了，所以该方案可以对密文做任意功能的运算了，知道这意味着什么吧，全同态实现了。七拐八歪的才修成正果，确实不容易。

接下来我们总结一下实现步骤，其实上面已经有了。

 

3、  实现步骤

功能函数f里其实有两样基本东西就够了：AND增强型电路，XOR增强型电路，经过集成电路化后如下现状：

 任意功能函数例如f1，都可以应用如上两个增强电路组合来表示，例如：

所以每次计算的基本步骤如下：

1)   对输入的明文m进行加密Enc(m),得到密文（c,z）,c是密文，z是向量<z1,z2,……>也称为扩展密文。

2)   对输入的密文进行重加密。输入的密文为（c,z）。在对密文运算之前每次都要对其重加密。因为明文空间是{0,1}，所以加密一定是对密文按位来加密。重加密的过程就是解密的过程，但是对象是对加密的密文以及加密的私钥进行。所以有：c’=Enc(Lsb(c))，得到的c’是一个整数。原本对z的每一位也要进行加密的，但是有一个方法可以提高效率，就是对z不加密，认为z的每一位自己就是自己的加密。另外私钥是s=<s1,s2,……>是0和1的向量，对私钥的每一位的加密记为sk’=<Enc(s1),Enc(s2),……>=<s1’，s2’,……>，得到的si’也是整数。然后运行∑si * zi，运行它的算法如前面所说，把每一个zi的二进制表示写成矩阵的一行，这样就得到一个矩阵：

              a1,0 ·  a1,-1 …… a1,-(n-1)  a1,-n  

  a2,0 ·  a2,-1 …… a2,-(n-1)  a2,-n   

  a3,0 ·  a3,-1 …… a3,-(n-1)  a3,-n

……        …………

              at,0  · at,-1 ……  at,-(n-1)  at,-n    

  

然后用si’乘以上面矩阵第i行的每一位，得到一个整数矩阵(矩阵中每一个元素都是整数)：

 

 

          ……     ……    e₂¹ (b1,-(n-1),

  b2,-(n-1)…，

bt,-(n-1)）

b1,0 ·  b1,-1 …… b1,-(n-1)    b1,-n  

  b2,0 ·  b2,-1 …… b2,-(n-1)    b2,-n   

  b3,0 ·  b3,-1 …… b3,-(n-1)    b3,-n

……        …………

          bt,0  ·  bt,-1 …… bt,-(n-1)   bt,-n

 

                                           e₂⁰ (b1,-n,b2,-n …，bt,-n）

 

 

 

然后对最后一列（最低位）求海明码，根据前面所述定理，海明码的最低位是e₂⁰ （b1,-n, b2,-n ……，bt,-n），其余各位e₂¹ （b1,-(n-1), b2,-(n-1) ……，bt,-(n-1)），……，都作为进位进到前面相应的位。依次计算下去，第1列的结果是b-1 = e₂⁰ （b1,-1, b2,-1 ……，bt,-1，……），第0列的结果是b0 = e₂⁰ （b1,0, b2,0 ……，bt,0，……）

 

b1,0 ·  b1,-1 …… b1,-(n-1)    b1,-n  

  b2,0 ·  b2,-1 …… b2,-(n-1)    b2,-n   

  b3,0 ·  b3,-1 …… b3,-(n-1)    b3,-n

……        …………

          bt,0  ·  bt,-1 …… bt,-(n-1)     bt,-n

           b0       b-1

3)   计算b= (b0 + b-1 ) ，b就是对应的Lsb(「∑si* zi 」)密文运算的结果。

4)   根据上面已经得到的c’=Enc(Lsb(c))，最终对密文c的重加密结果为：

c* = c’+ b

       知道此c*和c有什么关系么？c*是c的“重生”，噪音比原来降低了。

5)   然后将c*输入门电路。门电路一般都是二元的，需要两个输入，另外一个输入也用同样的方法计算得到

6)   进行门电路运算，例如加或乘，输出得到的结果。接下来有两种情况：第一种：此结果为最终结果，那么再进行重加密一次后，将密文返还给用户，用户解密后得到正确的运算结果。第二种：此结果不是最终结果，那么继续输入到下一级电路，依然是要先进行重加密。

     

4、  后记

历时一周的时间写了这个总结，就想用通俗的话语呈现整数上全同态方案的过程。整数全同态方案中另外就是有关参数的设置，噪音大小的分析等内容了，这个可以通过看DGHV方案来消化理解。

全部文章到此结束。此时此刻我觉得脑海里一篇空虚，很累很累，就好像春蚕将丝吐尽后的感觉。我知道，我需要看新的文章，以使我重生。

有个全同态加密群：187291158 。可以互相交流。

转载本文请联系原作者获取授权，同时请注明本文来自陈智罡科学网博客。
链接地址：https://blog.sciencenet.cn/blog-411071-617188.html

上一篇：整数上全同态加密方案分析（1）--献给全同态加密的初学者
下一篇：全同态加密研究资源汇总 (不断更新中！)