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

3602 Journal of Software 软件学报 Vol.32, No.11, November 2021

n
dp
由公式(6)可以推出 m 1 ⋅m 2 ⋅n<2 /2.根据应用场景的需要,当计算两个{0,128} 整数向量的同态内积时,
10
n
8
0≤m 1 ,m 2 ≤2 ;当计算两个{0,1024} 整数向量的同态内积时,0≤m 1 ,m 2 ≤2 .所以在第 1 种推荐参数下 dp=23,第
2 种推荐参数下 dp=29.
由公式(6)推出同态内积操作后解密正确的条件如下式:
dp
dp
dp
2
Pr(||2 2⋅dp /q ⋅ε 1 ⋅ε 2 +2 /q+2 /q⋅ε 2 ⋅m 1 +2 /q⋅ε 1 ⋅m 2 ||>1/2)=negl (7)
2
dp
dp
dp
其中,令α 1 =2 2⋅dp /q ⋅ε 1 ⋅ε 2 ,α 2 =2 /q,α 3 =2 /q⋅ε 2 ⋅m 1 +2 /q⋅ε 1 ⋅m 2 .所以,同态内积运算后解密正确的条件为
Pr(||α 1 +α 2 +α 3 ||>1/2)=negl.
将公式(5)带入公式(7),分别得到:
η q 2 η 2 q
64(2 ) 2 6 + + η 3
dp
dp
6144(2 ) η dp 2 24576(2 ) η dp 2 2 24576(2 ) η dp 2 3 4(2 ) 2 2 du (2 ) 2
du
⋅
α 2 2 dp / q ε = 2 ⋅ ⋅ ε = + + + + (8)
1 1 2 du 2 du 2 dv dv 2
(2 ) q 2 ⋅ q q 2 ⋅ 4(2 )
dp
α 2 =2 /q (9)
⎛ ⎛ q ⎞ 2 q ⎞
264 6 η ⎜ ⎜ + η ⎟ + ⎟ (2 2 dp⋅ )
⎜ ⎝ 2 du+ 1 ⎠ 2 dv+ 1 ⎟
α 3 2/ q ε = dp ⋅ 2 m + 1 2/ q ε ⋅ dp ⋅ 1 ⋅ m = 2 ⎝ ⎠ (10)
q
保证||α 1 +α 2 +α 3 ||>1/2 的概率可以忽略不计,本文方案能够解密正确.根据第 3.1 节加密参数η=5,给出本文的
第 1 种推荐参数(计算两位有效数字的整数向量内积),此时 dp=23,当模数 q=73786976294838206633、压缩参数
du=dt=dv=60 时,同态内积操作后能够正确解密;本文的第 2 种推荐参数(计算 3 位有效数字的整数向量内积),
此时 dp=29,当模数 q=4835703278458516698824713、压缩参数 du=dt=dv=79 时,同态内积操作后能够正确解密.
这两种加密参数均能够保证目标向量维数超过 n 维时,通过公式(2)多次进行密文加法时噪声保证能够正确解
密的范围内.
3.5 方案安全性
定理 1. 在 MLWE n,q,χ,k 问题假设的前提下,本文的同态内积方案是 IND-CPA 安全的.
证明:使用基于游戏的证明思路,用 Adv Game1 [A]表示敌手 A 在下列游戏中的优势.由于前面部分与文献[12]
中定理 3 的证明类似,该处不再赘述.
Game 0: Game 0 为标准的 IND-CPA 游戏,按照前面给出的方案来生成公钥 pk:=(t,A),私钥 sk:=s.
k
Game 1: Game 1 改变 Game 0 中公钥 t:=As+e 的生成过程,采用均匀随机选取 ′ ←t R .我们有:
q
Adv Game1 [A]−Adv CPA [A]≤Adv MLWE [A].
Game 2: Game 2 改变 Game 1 中挑战密文的生成方式,不使用公钥加密得到挑战密文,而是均匀随机选取
(, )v ←u ′′ R × q k R .我们有:
q
Adv Game2 [A]−Adv Game1 [A]≤Adv MLWE [A].
Game 3: Game 3 使用 Game 2 中挑战密文的生成方式,均匀选取两段随机密文 (, )uv ← ′′ R × k R 与
1 1 q q
⎛ T ⎛ 1 ⎞ u ′ ⎞ A ⎛ ′ 2 ⎞u ⎞⎛
′′
(, )uv ← R × k R .由于方案支持同态内积,必须还要考察密文的张量形式,敌手 A 区分 ⎜ , ⎟ ⎜ ⎟ ⊗ ⎜ ⎟ ⎟⎜ 和
2 2 q q ⎜ T v′ ⎟
⎝ ⎝ ⎠ ⎝ v′ t 1 ⎠ ⎝ 2 ⎠ ⎠
⎛ T ⎞ A ⎛ 1 ⎞ u ⎛ 2 ⎞u ⎞⎛
⎜ ⎜ , ⎟ ⎜ ⎟ ⊗ ⎜ ⎟ ⎟⎜ ⎟ 的分布与 MLWE n,q,χ,k 问题一样难,其中,(u 1 ,v 1 )和(u 2 ,v 2 )分别为 m 1 和 m 2 的密文,所以,Game 3
⎝ t T ⎝ ⎠ ⎝ v 1 ⎠ ⎝ v 2 ⎠ ⎠
与 Game2 中敌手 A 的优势差为
Adv Game3 [A]−Adv Game2 [A]≤Adv MLWE [A].
所以,总的来说,
Adv CPA [A]≤3⋅Adv MLWE [A].