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

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

2) 对公钥进行解压缩操作 t′:=Decompress q (t,dt);
3) 均匀随机取样随机向量及噪声 (, , )e ←re 1 2 β × η k β η k β × η ;
k
T
4) 加密得到密文: : Compress= u q (A r + e 1 ,du ∈ ) R ;
q
⎛ ⎛ q ⎞ ⎞
T
5) 加密得到密文: : v = Compress q ⎜ tr + e + 2 round ⎜ dp ⎟ ⋅ , m dv ∈ ⎟ R ;
q
⎝ ⎝ 2 ⎠ ⎠
6) 输出密文 :( , )c = v ∈ u R × q k R .
q
3. Dec(sk,c)
1) 输入私钥 sk:=s、密文 c:=(u,v)、密文解压缩参数 du 和 dv、加密参数 dp;
2) 解压缩得到 u′=Decompress q (u,du);
3) 解压缩得到 v′=Decompress q (v,dv).
输出明文:
T
m′:=Compress q (v′−s u′,dp) (1)
4. Evalutate(c 1 ,c 2 )
为了说明方案的同态内积计算 Evalutate(c 1 ,c 2 ),首先给出两种密文空间上的张量积运算的定义(具体分析
见第 3.3 节).
定义 1. 分别定义两种密文空间上的张量积运算:
a) 对于密文 c = (, )v ∈ u R × k R 与 c = (, )v ∈u R × k R ,其中,本文取 k=2,定义密文张量积为
1 1 1 q q 2 2 2 q 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 ).
b) 对于密钥 ∈s β ,定义密钥张量积 s⊗s=(1,−s 0 ,−s 0 ,−s 1 ,−s 1 ,s 0 s 1 ,s 0 s 1 ,s 0 s 0 ,s 1 s 1 ).定义 s⊗s 为计算密钥.
k
η
Evalutate(c 1 ,c 2 ):
1) 输入密文 c 1 ,c 2 ,其中,
¾ c = 1 Enc ( pk m = , 1 ) ( , )v ∈ 1 1 R × u q k R 是加密明文 m 1 得到的密文;
q
¾ c = 2 Enc (pk m = , 2 ) ( , )v ∈ 2 2 R × u q k R 是加密明文 m 2 得到的密文;
q
2) 求密文张量积 c 1 ⊗c 2 ,其中,⊗见定义 1 中的种类 a),该运算对应明文的向量内积(将在第 3.3 节给出详细
分析).
5. AfterDec(c 1 ⊗c 2 ,sk)
1) 输入私钥 sk:=s 并根据定义 1 中的种类 b)计算密文内积 s⊗s.
2
dp
2) 解密内积:m 3 =round(c 1 ⊗c 2 ⋅s⊗s⋅2 2⋅dp /q ) mod 2 ,多项式 m 3 的常数项即多项式 m 1 与 m 2 的系数组成的
两个 n 维向量的内积(其中,m 2 的系数要以特殊的方式排列,将在下一节详细分析).
3) 存在计算的目标整数向量大于 n 维的情况,通过以下方案计算.
假设要计算两个 n+1 维的向量内积,则将向量分为两块加密:
¾ 第 1 块加密前 n 维向量得到密文 c 1 =(u 1 ,v 1 )与 c 2 =(u 2 ,v 2 ).
¾ 第 2 块加密剩下的 1 维向量(用 0 填充明文多项式剩下的位置),得到密文 c 3 =(u 3 ,v 3 )与 c 4 =(u 4 ,v 4 ).
此时,计算同态内积即分别先计算 c 1 ⊗c 2 与 c 3 ⊗c 4 ,然后进行密文相加(将向量 c 1 ⊗c 2 与 c 3 ⊗c 4 对应
位置分别相加).解密即计算:
2
m 3 =round((c 1 ⊗c 2 +c 3 ⊗c 4 )⋅s⊗s⋅2 2⋅dp /q ) mod 2 dp (2)
其他维数的情况以此类推.
3.2 通过多项式乘法计算向量内积
由于明文 m 1 与 m 2 是 R q 上的多项式,可以通过如下多项式乘法运算来求得整数向量的内积:
若多项式 m 1 =w 0 +w 1 x+…+w n−1 x n−1 ∈R q ,m 2 =u 0 +u 1 x+…+u n−1 x n−1 ∈R q ,令多项式 m 3 =y 0 +y 1 x+…+y n−1 x n−1 =m 1 ⋅m 2 ,