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

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

次数 d=d(λ)为 2 的幂,模数 q=q(λ)≥2,通常为素数.与前面记号相同,定义多项式环 R=][x]/f(x),R q =] q [x]/f(x).令
χ=χ(λ)是 R q 上的一个分布.令 k 为模的维数,本文取 k=2 为例,MLWE n,q,χ,k 问题即区分以下两个分布:
b ⎞
⎛ a ⎡ a 12 ⎤⎡ ⎤
• 第 1 个分布: ⎜ 11 ⎥⎢ ⎥ ⎟ , 1 ⎟ ⎢ ⎜ .其中,均匀独立随机选取多项式 a jr ←R q (下标 1≤j≤k,1≤r≤k),b j ←R q
⎣ ⎝ a 21 a 22⎦⎣ ⎦ ⎠ b 2
(1≤j≤k).
⎛ a ⎡ a 12 ⎤⎡ ⎤ a ⎡ a 12 ⎤ ⎡ ⎤ ⎡ ⎤
e ⎞
b
s
1
,
• 第 2 个分布: ⎜ 11 ⎥⎢ ⎥ = ⎢ 11 ⎥ ⎢ ⎥ ⎢ ⎥ ⎟ ⋅ 1 + 1 ⎟ ⎢ ⎜ ,简记为(A,b=A⋅s+e).其中,均匀独立随机选取多
b
⎣ ⎝ a 21 a 22⎦⎣ ⎦ ⎣ a 21 a 22⎦ ⎣ ⎦ ⎣ ⎦ ⎠ s 2 e 2
2
项式 a jr ←R q (下标 1≤j≤k,1≤r≤k),s j ←R q (1≤j≤k),e j ←χ(1≤j≤k).注意:此处的向量 s 为加密算法中
的私钥,(A,b)是对应的公钥.
3 基于 MLWE 的同态内积方案
本节将给出本文的同态内积方案.核心问题有两个:一是如何通过密文乘法计算得到内积;二是密文乘法计
[3]
算后,对应的密钥需要做相应变化.所以,本文参考据 BGV 方案 的思路定义了类似于张量积的密文空间运算
⊗(详见定义 1).由于 BGV 方案基于 RLWE 问题构造,而本文方案基于 MLWE 问题构造,本文的密文空间计算更
为复杂,也会引入更大的解密噪声,所以本文参考 BGV 方案的思想对误差的积累与控制进行了分析,从而保证
了本文方案的正确性.并给出了两种优化的加密参数,在两种加密参数下能够高效分别计算两种不同大小的整
数向量同态内积.最后证明了本文方案是 IND-CPA 安全的.

3.1 同态内积方案
本节给出了本文的同态内积方案,总共分为 5 块——密钥生成:keygen(parameters);加密:Enc(pk,m);解密:
Dec(sk,c);同态内积计算:Evalutate(c 1 ,c 2 );同态运算后解密:AfterDec(c 1 ⊗c 2 ,sk).
首先给出方案中将出现的符号的定义,以帮助读者阅读,见表 1.

Table 1 Definitions of the notations in the scheme
表 1 方案记号的定义
符号 意义
λ
λ 安全参数,方案可抗 2 次攻击
k k=k(λ)=2,由安全参数λ决定的模的次数
n R q 上多项式的次数
dp
q q>2 的素数,决定有限域大小
η 噪声分布的参数
dp 明文压缩参数,决定明文的大小
dt 公钥压缩参数
du 密文压缩参数
dv 密文压缩参数
1. keygen(parameters)
1) 设安全参数为λ,根据 MLWE n,q,χ,k 中的安全性规约,输入加密参数 n=n(λ)=256;k=k(λ)=2;模数 q=q(λ);环
n
R q =] q [x]/x +1;噪声分布β η ,其中,η=5;公钥压缩参数 dt;
2) 均匀随机取样 A ← R q kk× ;
k
3) 均匀取样私钥与噪声 (, ) ←se β × η k β ;
η
4) t:=COmpress q (As+e,dt);
5) 输出公钥 pk:=(t,A),私钥 sk:=s.
2. Enc(pk,m)
dp
n
1) 输入公钥 pk:=(t,A)、明文 m∈{0,…,2 −1} 、公钥压缩参数 dt、密文压缩参数 du 和 dv、加密参数 dp.
其中,明文 m 是将 n 格规定范围的整数作为系数的多项式;