Page 275 - 《软件学报》2021年第11期
P. 275

柯程松  等:一种基于 MLWE 的同态内积方案                                                        3601


                 该乘法是 R q 上的乘法,所以满足以下关系:
                                                          ⎡  u 0  u 1  u 2  ... u n− 1 ⎤
                                                          ⎢ −                    ⎥
                                                          ⎢  u n−  1  u 0  u 1  ... u n−  2 ⎥
                                       ( ,...,y 0  y n−  1 ) =  (w 0 ,...,w n−  1 ) ⎢ ⋅  −  u n−  2  −  u n−  1  u 0  ... u n−  3  ⎥ ,
                                                          ⎢                      ⎥
                                                          ⎢  #    #    #   ...  #  ⎥
                                                          ⎢                      ⎥
                                                          ⎣  −  u 1  −  u 2  −  u 3  ...  u 0 ⎦
                    即可得到 y 0 =(w 0 ,w 1 ,w 2 ,…,w n−1 )⋅(u 0 ,−u n−1 ,−u n−2 ,…,−u 1 ).所以在求两个即令两个 n 维整数向量 a=(a 0 ,…,a n−1 )
                 和 b=(b 1 ,…,b n−1 )的同态内积时,需要按照以下排列将整数向量 b 作为多项式 m 2 的系数:
                                                            2
                                              m 2 =b 0 −b n−1 x−b n−2 x −…−b 1 x n−1 ∈R q             (3)
                 3.3   通过密文空间张量运算计算同态内积
                          [3]
                    与 BGV 方案类似,可以采用密文作张量积的方式进行同态乘法运算.但是由于本文方案是基于 MLWE 问
                 题构造的,与 BGV 方案的密文空间运算以及进行噪声的膨胀方式均不同.本节将具体分析第 3.1 节定义 1 中的
                 密文空间运算⊗.
                                                                               dp
                                                                       dp
                                                                   T
                    根据公式(1),通过解密算法得到两个明文 m 1 =round((v 1 −s u 1 )⋅2 ) mod  2 =(a 0 +a 1 x+…+a n−1 x n−1 )∈R q ,m 2 =
                              dp
                                      dp
                         T
                                                    2
                 round((v 2 −s u 2 )⋅2 /q) mod 2 =(b 0 −b n−1 x−b n−2 x −…−b 1 x n−1 )∈R q ,根据第 3.2 节的分析,密文空间的运算只要对应明
                 文做 R q 上的多项式乘法即可,所以等式两边同时做乘法:
                                m =  3  m m⋅  1  2
                                     =  round ((v −  T  ) (v⋅  − su  s u  ) 2 ⋅  2 dp⋅  / q 2 )mod2 dp
                                                      T
                                          1    1  2    2                                              (4)
                                  =  round (c ⊗  c ⋅  (1, s−  , s−  , s−  , s s s s s s s s s−  ,  ,  ,  ,  ) 2 ⋅  2 dp⋅  / q 2 )mod2 dp
                                         1   2    0  0  1  1  01  01  0 0  1 1
                                     =  (z +  z x +  ... z+  x n− 1 )∈  R
                                     0  1      n− 1    q
                 其中,c 1 ⊗c 2 =(v 1 v 2 ,v 2 u 10 ,v 1 u 20 ,v 2 u 11 ,v 1 u 21 ,u 10 u 21 ,u 11 u 20 ,u 10 u 20 ,u 11 u 21 )即密文空间运算.那么进行同态运算之后,需要
                 通过计算密钥 s⊗s 来解密.具体来讲就是第三方或者云服务器进行密文空间运算 c 1 ⊗c 2 后得到向量(v 1 v 2 ,v 2 u 10 ,
                 v 1 u 20 ,v 2 u 11 ,v 1 u 21 ,u 10 u 21 ,u 11 u 20 ,u 10 u 20 ,u 11 u 21 ),将该向量传给用户,用户持有计算密钥,用户通过计算 m 3 =round(c 1 ⊗c 2 ⋅
                         2
                                dp
                 s⊗s⋅2 2⋅dp /q ) mod  2 进行同态运算后的解密操作,其中,m 3 =(z 0 +z 1 x+…+z n−1 x n−1 )∈R q ,z 0 =a⋅b 即目标整数向量的内
                 积.但公式(4)成立,要保证将噪声控制在一定范围内.在第 3.4 节中具体分析.
                 3.4   方案正确性与优化参数
                    本节将分析本文同态内积方案的正确性,并针对不同的应用场景给出两种推荐的加密参数:在第 1 种参数
                                    n
                                                                                     n
                 下,能够计算两个{0,128} 整数向量的同态内积;在第 2 种参数下,能够计算两个{0,1024} 整数向量的内积.其中,
                 向量的维数 n 根据第 3.1 节中加密算法的安全性取 256.在实际应用场景下(如逻辑回归分类、密文检索),需要
                 计算的目标向量均是浮点数.应用本文的同态内积方案时,需要先将浮点数乘以 10 的幂次变为整数,一般情况
                 下,两位有效数字就够用了(即使用本文推荐的第 1 种加密参数);如果需要更高的精度,那么推荐使用本文第 2
                 种加密参数,能够同态计算 3 位有效数字的向量内积,但使用第 2 种推荐参数时方案的效率会降低.
                    由于进行了同态运算,解密时的噪声必然会增大,所以必须调整加密参数才能保证方案的正确性.
                                                                                              dp
                                                                                    dp
                    根据文献[12],运行第 3.1 节中加解密算法解密后得到明文 m′=round(m+ε⋅2 /q) mod  2 ,其中,噪声
                 || || || (ε =  T  − er  T  ) (+ s e  t T  + cr  T  u ) e+ s c  2  +  c v  || ,且
                                         ⎛         2 512 η ⋅ ⋅  ⎛  q  ⎞  2  q  ⎞
                                        Pr || || 12ε  ⎜  ⋅  ⋅  ⎜  +  η >  ⎟  +  ⎟  =  negl            (5)
                                         ⎜           6    ⎝  2 du+  1  ⎠  2 dv+  1  ⎟
                                         ⎝                               ⎠
                    接下来分析同态内积之后解密得到正确结果的条件.
                                                                 dp
                                      dp
                    设 m′  1  round (m +  1  ε  2 /) mod  2 , q  dp  m′ =  2  =  round (m +  2  ε ⋅  ⋅  2 /) mod 2q  dp  ,则
                                                                           dp
                                                          dp
                                                                dp
                           m′  3  m m′ ⋅  1 ′ =  2  =  (m m + ⋅  2  2 2 dp⋅  / q εε ⋅ 2  ⋅  1  2  +  2 / q +  2 / q ε ⋅  2  ⋅  m +  1  2 / q ε ⋅  1  ⋅  m 2 )  mod  2 dp  (6)
                                       1
   270   271   272   273   274   275   276   277   278   279   280