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

柯程松 等:一种基于 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