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

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

2 预备知识

本节将给出本文算法中会出现的符号以及一些相关概念.该部分内容会用到文献[12,14]中的相关技术,为
了保证读者阅读的方便,在本文中采用的记号与文献[12]一致.

2.1 基础符号
令 R=][x]/f(x)为整系数多项式环 Z[x]模 f(x)的商环,R q =] q [x]/f(x)表示 R 的系数再模 q.其中,如果未作特殊说
n
明,f(x)=x +1,n 为 f 的次数.
+
当 q 为大于 2 的素数,令 mod q 表示模 q 的取值范围是[−(q−1)/2,(q−1)/2],用 mod q 表示模 q 的取值范围是
−
[0,q−1],类似地,mod q 的范围是[−(q−1),0].
对 x∈\,round(x)表示通常的四舍五入,⎡x⎤为向上取整,⎣x⎦为向下取整.
对于 R q 上的多项式 u(x)=u 0 +u 1 x+…+u n−1 x n−1 ,简单记为 u,u 的无穷范数为||u|| ∞ =max{|u j |}.对于 k 个多项式
k
)
(,pp 2 ,..., p ∈ R 组成的向量 p 的无穷范数定义为所有分量无穷范数中最大的一个,即为||p|| ∞ =max||p i || ∞ .如未作
n
1
q
特殊说明,通常使用||⋅||简略表示无穷范数.
如果 A 为集合,令 a←A 表示从集合 A 均匀选取元素 a;如果 A 为分布,则表示依分布 A 选取元素 a.
本文的 log 均表示以 2 为底的对数.
令 Pr[⋅]表示概率,negl 表示概率可忽略不计.
n
令{a,b} 表示一个 n 维整数向量,其中,向量元素大于等于 a 且小于等于 b.
n− 1
令两个 n 维整数向量分别为 a=(a 0 ,…,a n−1 )和 b=(b 0 ,…,b n−1 ),令 ⋅= ∑ ab ,也就是向量 a 与 b 的内积.
ab
ii
i= 0
2.2 同态内积
本节将给出同态内积的详细概念.同态内积指的是在加密的状态下计算两个整数向量的内积,即令两个 n
维整数向量 a=(a 0 ,…,a n−1 )和 b=(b 0 ,…,b n−1 ),将两个整数向量分别作为环 R q 上多项式的系数得到明文 m 1 =(a 0 +
a 1 x+…+a n−1 x n−1 )∈R q 和 m 2 =(b 0 +b 1 x+…+b n−1 x n−1 )∈R q .设加密操作为 Enc(⋅),解密操作为 Dec(⋅),加密 m 1 与 m 2 分别
得到密文 c 1 =Enc(m 1 )与 c 2 =Enc(m 2 ).令 c 3 =c 1 ⊗c 2 ,其中,⊗是密文空间上的某种运算.如果能够通过 c 3 与私钥 sk 解
密得到 a⋅b,则我们将具有这种性质的加密方案称作同态内积方案.本文主要的贡献即基于文献[12]实现了一种
高效的同态内积方案.
2.3 中心二项分布
本文采用与文献[12]中同样的中心二项分布β η 作为加密方案中的噪声分布,定义如下:
η
2η
均匀随机选取(a 1 ,…,a η ,b 1 ,…,b η )←{0,1} ,计算并输出 ∑ (a − b j ) .
j
j= 1
我们用 u←β η 表示各系数依中心二项分布β η 独立选取,得到 R q 中的一个多项式 u.
k
从β η 取样 k 个独立并满足β η 分布的多项式构成向量 v,则记作 ←v β .
η
2.4 压缩技术(compress)与解压缩技术(decompress)
为了减小公钥与密文的大小,本文和文献[12]一样采用了文献[14]中的压缩技术(compress)与解压缩技术
(decompress).相应地,这会在密文中引入误差.为了保证解密的正确性,将在后面章节分析如何选择合适的参数.
+
d
d
定义函数 Compress q (x,d):输入 x∈Z q ,d<⎡logq⎤,输出 y=round((2 /q)⋅x) mod 2 .
d
定义函数 Decompress q (y,d):输入 y=Compress q (x,d),输出 x′=round((q/2 )⋅y).
不难得到:对于整数 x∈Z q ,先压缩再解压后产生的误差满足:|x−x′|≤round(q/2 d+1 ).
2.5 MLWE问题
d
和文献[12]一样,本文加密方案的安全性同样基于模容错学习问题 MLWE [15] .设安全参数为λ,f(x)=x +1,其