一种基于LWE采样算法的实现与优化
王柯翔, 黎琳, 彭双和
北京交通大学 计算机与信息技术学院,北京 100044
通信作者:黎琳(1978—),女,山东济南人,讲师,博士. email: lilin@bjtu.edu.cn

第一作者:王柯翔(1992—),男,广西桂林人,硕士.研究方向为密码学及其应用.email:14120358@bjtu.edu.cn

摘要

基于带错误学习问题(Learning With Errors,LWE)构造的密码体制能够抵御量子攻击,它的应用效率与LWE问题的采样过程密切相关.而在LWE问题采样中,对其中的错误因子(Error Factor)采样占采样过程绝大部分时间,本文对LWE问题中的错误因子的采样算法进行研究,将在高斯分布上效率较高的金字塔(Ziggurat)采样算法,应用到了一种高效的LWE问题采样算法中.基于在连续域上的采样比离散域上采样效率高的思路,对LWE问题采样算法在离散域上采样的过程进行了优化,提出了一种将连续域上的采样结果进行取整的方法,.对优化前后的两种LWE问题的采样算法进行了对比实验,结果表明:改进后的算法在不占用大量内存并且保证安全性的情况下,将采样速度提高了38%~200%.

关键词: ; 带错误学习问题; 高斯分布; 错误因子; 采样
中图分类号:TP309
Realization and optimization of a LWE sampling algorithm
WANG Kexiang, LI Lin, PENG Shuanghe
School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044,China
Abstract

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.

Keyword: lattice; learning with errors; Gaussian distribution; error factor; 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%.

1 预备知识
1.1 符号说明

本文中, Z表示整数域, Zq表示模 q的整数域; R表示实数域; 如果 X是一个集合, 用 xRX表示从 X上均匀采样获得的向量x, 如果 X是一个分布, xRX表示从 X上采样获得满足 X分布的 x.

1.2 基本概念

定义1 LWE问题. LWE存在两个方面的问题: 1)判断问题.是对于当给定相互独立的采样 Ai, bTiZqn×m×Zqm, 其中 Ai表示 i维矩阵, bTi表示 i维向量, nm均为正整数, q为素数.对于 AiRZqn×m, eiRχ, 有 bTi=sTAi+eTimodq, sZqn, 其中 ei为错误因子, sT为秘密因子.在 Zqm上的某一分布 χ, χ一般为离散高斯分布, 很难判断出采样 Ai, bTi是从 Zqn×m×Zqm中均匀随机采样获得的.2)搜索问题.则是很难从采样 Ai, bTi中找出 sT.

定义2 格. 格是Rn的一个子群, 对于n个线性无关的向量组成的基 Β=b1, .., bnRn.定义由基Β 构成的n维格为

Λ=LΒ=B×c=i=0nbi·ci:cZn(1)

有满秩矩阵AZqn×m, 其中n∈ Z, 则定义所有向量正交的奇偶校验矩阵A组成的m维格为

ΛA=eZm|Ae=0modq(2)

其中.对于向量 vZqn, 任意 xZmΛvA表示 ΛAx+ΛA的转换, 满足 Ax=vmodq, 定义为

ΛvA=eZm|Ae=vmodq(3)

2 Ziggurat采样算法
2.1 连续域上的Ziggurat采样算法

Ziggurat采样算法是文献[10]提出的拒绝采样算法的一种改进, 将高斯概率密度分布函数中 x0部分划分为 m个矩形, 为了保证选取到每一个矩形的概率相同, 将所有矩形面积设为相同.对于任一矩形 Ri都与分布曲线相交分为两部分, 其中一部分为完全在高斯分布以内, 另一部分则在分布以外, 如图1所示.

图1 划分块数m=8时的Ziggurat采样方法Fig.1 Ziggurat sampling method when divided blocks m=8

图1中, 每次分好块后将每个矩形的右下角的点 xi, yi记下后, 开始采样:1)随机产生一个整数 i, 1< i< m-1, 来选中第 i个矩形.2)在 0, xi上随机产生一个 x', 如果 x'xi+1, 说明 x'必在分布以内; 否则 xi< x'xi+1, 需要采用拒绝采样. 3)随机产生一个 y'yi-1, yi, 如果 y'+yi-1f(x')( f(x')为连续高斯分布概率密度函数), 则表示选中了在分布以内的值, 就选中 x', 否则拒绝这个 x', 返回到第1)步产生 i值.

2.2 离散域上的Ziggurat采样算法

离散Ziggurat采样算法[7]在Ziggurat算法的基础上进行了改进, 在算法思路上与连续域Ziggurat算法相同, 主要是将高斯分布上的坐标值和矩形的面积进行了变换.做出了如下改进:

1) 把每一块矩形的面积规定为对应的 x轴坐标 xi值向上取整乘以矩形的高度, 1+xi×yi-yi-1.

2) 矩形的各点的计算方法不一样. m个矩形块有相同的面积 S, 规定: ym:=0, x0:=0, xm:=, 其中, t表示高斯分布的边界, σ表示高斯分布的方差.通过迭代运算可以得到

ym-1=S/(1+xm)(4)xm-1=ρσ-1ym-1(5)

对于 i=m-2, ..., 1.

yi=S/(1+xi+1)+yi+1(6)xi=ρσ-1yi(7)y0=S/(1+x1)+y1(8)

式中, ρσ-1y表示离散高斯分布概率密度函数.

3)在 y̅i, y̅i-1中获取随机数 y̅, 为此定义 h̅i:=y̅i-1-y̅i为第 i个矩形的高, 在 {0, 1, ..., 2ω-1}中均匀采样获得 y', 将 y̅的值定义为 y̅=h̅iy'[0, 2ωh̅i], 其中 ω为正整数.通过上述变换使得均匀采样得到的值更为准确.

3 LWE采样算法的改进
3.1 一种LWE采样算法的实现

在文献[5]中提出了一种从初始矩阵G上对LWE问题中错误因子的采样算法, 为了方便在之后做比较, 将该算法描述为算法1, 其内容如下:

算法1:

输入:G, v

输出:t=(t0, ..., tk-1)Τ

对于 i=0, ..., k-1, 循环计算

tiD2Z+ai, r(9)ai+1=ai-ti/2(10)

式中: G满足Gnk=In$\otimes$gT, 其中In表示单位向量, gT= 1, 2, ..., 2k-1; D2Z+ai, r为整数域上的离散高斯分布.该算法初始化一整数 a0v中任意元素 vi满足 viZq, 输出的 t满足格上分布 tΛvigT, 向量 t即为采样结果.

算法1的优点在于将较为复杂的格上的高斯分布采样转化为整数域上以 2Z+a0为中心, r为方差的离散高斯分布的采样, 使得采样效率能较大提高.因而决定该算法采样效率好坏的关键是在整数域上的离散高斯分布采样的过程, 在前文中提到了离散Ziggurat采样算法是目前综合性能较优的算法, 因而将该算法应用到了对算法1的实现, 与之后提出的算法进行比对.

3.2 整数域上采样过程的改进

算法1通过将格上的离散高斯分布采样转化到整数域上的离散高斯分布采样的方法使采样效率得到提升, 而考虑到对于一种分布的采样, 连续分布上的采样效率要比离散分布上采样效率高, 基于这一思路, 将连续高斯分布的采样通过取整的处理方式转化为离散高斯分布的采样, 形成了算法2, 其内容如下:

算法2:

输入: G, v

输出: t=t0, ..., tk-1Τ

对于 i=0, ..., k-1, 循环计算

ti'Zigguratai, r(11)Ifti'mod2=aimod2(12)ti=ti'(13)ai+1=ai-ti/2(14)

如果式(12)不满足, 则返回再执行式(11).

为了验证算法2的正确性, 对该算法进行了证明:

1)由式(14)可知 ti=ai-2ai+1;

2)若向量 t满足 tΛvigT, 则满足 gTt=vimodq, 由 gT=1, 2, ..., 2k-1可得

gTt=t0+2t1+22t2+...+2k-1tk-1(15)

3)将 ti=ai-2ai+1代入式(15), 可得

gTt=a0-2a1+2a1-2a2+22a2-2a3+...+2k-1ak-1-2ak(16)gTt=a0-2kak=vi-2kak(17)

式中, 2kakk=lnq, 则 2kmodq=0, 从而 gTt=vimodq成立.

通过上述证明可知算法2在采样结果上是正确的, 采样得到的向量 t均能满足 tΛvigT, 所以采样结果均满足在格上的分布, 因而算法2的采样结果既具有正确性, 也具有安全性.

4 实验结果及分析

实验是在Intel(R)Core(TM)i3-4170 3.70 GHz的处理器, 8 GB内存, 操作系统为ubuntu 14.04的计算机上实现的.对于算法中的中心和方差等参数, 选择依照了文献[1]中提出的参数: n256; q为2的次方, 且 q219; r2×ln2n1+1ε/π.两种算法都调用了基于linux的时间函数clock_gettime的计数器CLOCK_PROCESS_CPUTIME_ID来计算运行效率.

通过验证得到向量 t是否满足 gTt=vimodq来验证实验结果是否正确.得到的采样都满足上述条件.算法1中使用的离散Ziggurat采样算法, 在进行采样算法前需要预先计算将高斯分布划分矩形的块数, 实验使用了文献[5]中对数据精度和方差等参数的选取方法; 同时由于Ziggurat采样算法本身具有划分矩形的块数越多, 采样速度越快且占用内存也越高的特性, 从而将算法1中离散Ziggurat采样算法在不同划分块数下与算法2进行了效率比对结果如图2所示.

图2 算法1和算法2实验结果对比Fig.2 Experimemal results comparisons contrast between algorithm 1 and algorithm 2

图2(a)中显示了算法1中使用离散Ziggurat采样算法在分块数为20和100时与算法2采样所需时间的对比, 从图2中可以看出, 在采样次数到达 107次时, 算法2采样所需的时间分别是算法1采样所需时间的33%和72%.从图2(b)可以看到, 此时算法1中使用离散Ziggurat采样算法在分块数为20和100时比算法2中占用CPU的时间更长, 约是算法2占用时间的514%和190%.图2(c)显示了算法1中使用离散Ziggurat采样算法在分块数达到500和1 000时与算法2的采样所需时间对比, 可以看到此时算法1与算法2采样所需时间接近.从图4(d)中可以看到, 此时算法2比算法1中使用离散Ziggurat采样算法分块数为500和1 000时所占用CPU的时间更短.

从算法采样速度快慢来看, 尽管将连续高斯分布采样结果直接取整的方法, 不能够准确转化成为对应整数域上的离散高斯采样结果, 但是通过实验结果表明, 将此方法应用在本文提到的LWE问题的采样算法中是可行的.应用到本文提到的LWE问题的采样算法中, 在采样次数相同且数量较大的情况下, 将连续高斯分布采样结果取整的算法应用在LWE问题的采样中比使用离散Ziggurat采样算法在分块数不是特别高的情况下所需的采样时间少, 使得算法的采样速度提升了38%~200%左右, 而在使用分块数很大的离散Ziggurat采样算法时, 与连续高斯分布采样结果取整的方法的采样速度十分接近.

从算法采样占用内存情况来看, 实验结果表明了在分块数为正常数值20和100的情况下, 使用将连续高斯分布取整的方法比使用离散Ziggurat采样算法在LWE问题采样中占用CPU的时间短, 只有到分块到500和1 000这样非常大的数值的时候, 两种算法的占用CPU的时间才较为接近, 而此时离散Ziggurat采样算法在预计算上花费的时间很长, 会很大的影响LWE问题采样算法的整体效率, 因此在离散Ziggurat选择分块数为500和1 000时, 算法2的采样效率仍然高于算法1.

5 结论

本文在高斯分布上采样效率较高的Ziggurat采样算法基础上, 分析了一种将LWE问题采样从格上离散高斯分布转化到整数域上的离散高斯分布上采样的算法, 并将离散Ziggurat采样算法应用其中.本文作者提出了一种新的改进算法, 使用将连续高斯分布的采样结果取整的采样方法替代了离散高斯分布采样, 为了验证改进的采样算法的采样效率, 对两种采样算法进行了实验, 实验记录的采样所需时间显示, 在产生采样数量大于等于 107且占用内存不大的情况下, 改进的LWE问题的采样算法所需时间是原有的采样算法的33%~72%, 即采样速度上提升了38%~200%左右, 实现了对原有算法的优化.

The authors have declared that no competing interests exist.

参考文献
[1] FOLLÁTH J. Gaussian sampling in lattice based cryptography[J]. Tatra Mountains Mathematical Publicati-ons. 2015, 60(1): 1-23. [本文引用:2]
[2] CHARLES F, KARNEY F. Sampling exactly from the normal distribution[J]. ACM Transactions on Mathematical Software, 2013, 42(3): 1-10. [本文引用:1]
[3] WANG S B, ZHU Y, DI M A, et al. Lattice-based rey exchange on small integer solation problem[J]. Science China Information Sciences, 2014, 57(11): 1-12. [本文引用:1]
[4] REGEV O. On lattices, learning with errors, rand om linear codes and cryptography[C]// 37th Annual ACM Symposium on Theory of Computing, 2005: 84-93. [本文引用:2]
[5] BANSARKHANI R E, DAGDELEN Ö, BUCHMANN J. Augmented learning with errors: the untapped potential of the error term[J]. Financial Cryptography and Data, 2015: 333-352. [本文引用:5]
[6] THOMAS D, LUK W, LEONG P H W, et al. Gaussian rand om number generators[J]. ACM Computing Surveys, 2007, 39(4): 415-416. [本文引用:1]
[7] BUCHMANN J, CABARCAS D, GÖPFERT F, et al. Discrete ziggurat: a time-memory trade-off for sampling from a Gaussian distribution over the integers[C]//Selected Areas in Cryptography, 2014: 402-417. [本文引用:2]
[8] ROY S S, VERCAUTEREN F, VERBAUWHEDE I. High precision discrete Gaussian sampling on FPGAs[C]//Selected Areas in Cryptography , 2014: 383-401. [本文引用:1]
[9] GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions[C]//Proceedings of the Annual ACM Symposium on Theory of Computing, 2008, 14: 197-206. [本文引用:1]
[10] DWARAKANATH N C, GALBRAITH S D. Sampling from discrete Gaussians for lattice-based cryptography on a constrained device[J]. Applicable Algebra in Engineering Communication&Computing, 2014, 25(3): 159-180. [本文引用:2]
[11] PEIKERT C. An efficient and parallel Gaussian sampler for lattices[C]//Advances in Cryptology-Crypto, 2010: 145-166. [本文引用:1]
[12] MICCIANCIO D, PEIKERT C. Trapdoors for lattices: simpler, tighter, faster, smaller[C]//International Conference on the Theory & Applications of Cryptographic Techniques, 2012, 7237: 700-718. [本文引用:1]
[13] DUCAS L, DURMUS A, LEPOINT T, et al. Lattice signatures and bimodal Gaussians[C]// Advances in Cryptology-Cpypto 2013, 2013, 8042: 40-56. [本文引用:1]
[14] MARSAGLIA G, TSANG W W. The ziggurat method for generating rand om variables[J]. Journal of Statistical Software, 2000, 5(8): 1-7. [本文引用:1]
[15] DUCAS L, NGUYEN P Q. Faster Gaussian lattice sampling using lazy floating-point arithmetic[C]// International Conference on the Theory & Application of Cryptology & Information Security, 2012, 7658: 415-432. [本文引用:1]