第一作者:王柯翔(1992—),男,广西桂林人,硕士.研究方向为密码学及其应用.email:14120358@bjtu.edu.cn
基于带错误学习问题(Learning With Errors,LWE)构造的密码体制能够抵御量子攻击,它的应用效率与LWE问题的采样过程密切相关.而在LWE问题采样中,对其中的错误因子(Error Factor)采样占采样过程绝大部分时间,本文对LWE问题中的错误因子的采样算法进行研究,将在高斯分布上效率较高的金字塔(Ziggurat)采样算法,应用到了一种高效的LWE问题采样算法中.基于在连续域上的采样比离散域上采样效率高的思路,对LWE问题采样算法在离散域上采样的过程进行了优化,提出了一种将连续域上的采样结果进行取整的方法,.对优化前后的两种LWE问题的采样算法进行了对比实验,结果表明:改进后的算法在不占用大量内存并且保证安全性的情况下,将采样速度提高了38%~200%.
The crypto system constructed with Learning With Errors (LWE) can resist quantum attacks, and its application efficiency is closely related to the sampling process of LWE problem. In the LWE problem sampling, the error factor sampling which accounted for most of the sampling process. This paper studies the sampling algorithm of the error factor in the LWE problem, and applies the Gaussian distribution (Ziggurat) sampling algorithm to an effective sampling algorithm of the LWE problem. Based on the idea of high sampling efficiency on the sampling domain in the continuous domain, this paper deals with the LWE problem sampling algorithm on the discrete domain. The sampling process is optimized, and a method of rounding the sampling results in the continuous domain is proposed and applied to the LWE problem sampling algorithm. We have compared the two LWE sampling algorithms before and after optimization. The experimental results show that the improved algorithm increases the sampling speed by 38% ~ 200% in the condition of not using a lot of memory and ensuring the safety of sampling.
在量子计算不断发展与突破的情形下, 传统的密码学将面临巨大的挑战.目前研究人员已提出针对大整数因子分解和计算离散对数的量子算法, 这将使得未来的量子计算机可攻击现有的基于数论问题的公钥密码算法, 如RSA(Rivest-Shamir-Adleman)提出的加密算法, DSA(Digital Signature Algorithm, 数字签名算法), ECDSA(Elliptic Curve Discrete Signature Algorithm, 椭圆曲线数字签名算法)等, 而量子计算机的出现只是时间问题, 因此设计新型、高效和能抵抗量子攻击的密码算法已经成为了如今密码学发展的趋势[1].
在抵抗量子计算机攻击的密码体制研究中格理论中的困难问题被应用在很多密码体制设计中[2].目前应用在密码体制里主要有小整数解(Small Integer Solution, SIS)问题[3]和学习错误(LWE)问题[4], SIS被视为LWE问题的对偶问题. 2005年, 文献[4]提出的LWE问题因为已经被证明为NP完全问题, 从而在NP不等于P的假设下, 基于LWE问题的公钥密码方案可以抵御量子计算机的攻击, 并且有可证明安全的特性, 被应用在很多的公钥密码体制中.而很多在格上的基于LWE问题的密码体制, 通常需要从某种分布上采样获得错误因子, 一般是在格上的离散高斯分布上采样[5].因而研究出有效的格上的离散高斯分布的采样算法对LWE问题的应用有着重要的意义.
基于高斯随机数的生成器[6], 目前在离散高斯分布上的采样算法主要有:文献[7]的离散Ziggurat采样算法较优.文献[8]的Kunth-Yao算法是基于一种完美的随机比特产生器和随机比特模型来进行采样, DDG-tree的概念在其中起着关键作用, Kunth-Yao算法的采样速度较快, 但是需要占用较大内存, 综合占用内存和运行速度离散Ziggurat算法性能较优.文献[9, 10]的拒绝采样算法(rejection sampling)和取反算法[11, 12](inversion method)是采样的两种最基本的算法.文献[13, 14]的二分法算法是将这两种算法相结合.
在文献[5]中提出了一种对错误因子采样的算法, 本文作者将在连续域上与离散域上的Ziggurat采样算法分别应用在了文献[5]提出的算法中, 通过对连续域上的Ziggurat算法进行改进, 在对比实验下发现本文在连续域上高斯分布的Ziggurat改进算法相比较于离散Ziggurat采样算法, 可以使得LWE问题的采样算法的采样速度提高38%~200%.
本文中, Z表示整数域, Zq表示模
定义1 LWE问题. LWE存在两个方面的问题: 1)判断问题.是对于当给定相互独立的采样
定义2 格. 格是Rn的一个子群, 对于n个线性无关的向量组成的基
有满秩矩阵A∈
其中.对于向量
Ziggurat采样算法是文献[10]提出的拒绝采样算法的一种改进, 将高斯概率密度分布函数中
图1中, 每次分好块后将每个矩形的右下角的点
离散Ziggurat采样算法[7]在Ziggurat算法的基础上进行了改进, 在算法思路上与连续域Ziggurat算法相同, 主要是将高斯分布上的坐标值和矩形的面积进行了变换.做出了如下改进:
1) 把每一块矩形的面积规定为对应的
2) 矩形的各点的计算方法不一样.
对于
式中,
3)在
在文献[5]中提出了一种从初始矩阵G上对LWE问题中错误因子的采样算法, 为了方便在之后做比较, 将该算法描述为算法1, 其内容如下:
算法1:
输入:G, v
输出:t=(t0, ..., tk-1)Τ
对于
式中: G满足Gnk=In$\otimes$gT, 其中In表示单位向量, gT=
算法1的优点在于将较为复杂的格上的高斯分布采样转化为整数域上以
算法1通过将格上的离散高斯分布采样转化到整数域上的离散高斯分布采样的方法使采样效率得到提升, 而考虑到对于一种分布的采样, 连续分布上的采样效率要比离散分布上采样效率高, 基于这一思路, 将连续高斯分布的采样通过取整的处理方式转化为离散高斯分布的采样, 形成了算法2, 其内容如下:
算法2:
输入:
输出:
对于
如果式(12)不满足, 则返回再执行式(11).
为了验证算法2的正确性, 对该算法进行了证明:
1)由式(14)可知
2)若向量
3)将
式中,
通过上述证明可知算法2在采样结果上是正确的, 采样得到的向量
实验是在Intel(R)Core(TM)i3-4170 3.70 GHz的处理器, 8 GB内存, 操作系统为ubuntu 14.04的计算机上实现的.对于算法中的中心和方差等参数, 选择依照了文献[1]中提出的参数:
通过验证得到向量
图2(a)中显示了算法1中使用离散Ziggurat采样算法在分块数为20和100时与算法2采样所需时间的对比, 从图2中可以看出, 在采样次数到达
从算法采样速度快慢来看, 尽管将连续高斯分布采样结果直接取整的方法, 不能够准确转化成为对应整数域上的离散高斯采样结果, 但是通过实验结果表明, 将此方法应用在本文提到的LWE问题的采样算法中是可行的.应用到本文提到的LWE问题的采样算法中, 在采样次数相同且数量较大的情况下, 将连续高斯分布采样结果取整的算法应用在LWE问题的采样中比使用离散Ziggurat采样算法在分块数不是特别高的情况下所需的采样时间少, 使得算法的采样速度提升了38%~200%左右, 而在使用分块数很大的离散Ziggurat采样算法时, 与连续高斯分布采样结果取整的方法的采样速度十分接近.
从算法采样占用内存情况来看, 实验结果表明了在分块数为正常数值20和100的情况下, 使用将连续高斯分布取整的方法比使用离散Ziggurat采样算法在LWE问题采样中占用CPU的时间短, 只有到分块到500和1 000这样非常大的数值的时候, 两种算法的占用CPU的时间才较为接近, 而此时离散Ziggurat采样算法在预计算上花费的时间很长, 会很大的影响LWE问题采样算法的整体效率, 因此在离散Ziggurat选择分块数为500和1 000时, 算法2的采样效率仍然高于算法1.
本文在高斯分布上采样效率较高的Ziggurat采样算法基础上, 分析了一种将LWE问题采样从格上离散高斯分布转化到整数域上的离散高斯分布上采样的算法, 并将离散Ziggurat采样算法应用其中.本文作者提出了一种新的改进算法, 使用将连续高斯分布的采样结果取整的采样方法替代了离散高斯分布采样, 为了验证改进的采样算法的采样效率, 对两种采样算法进行了实验, 实验记录的采样所需时间显示, 在产生采样数量大于等于
The authors have declared that no competing interests exist.