论文研究-并行LLL算法研究综述.pdf

所需积分/C币:36 2019-09-13 08:14:00 811KB .PDF
13
收藏 收藏
举报

Lenstra-Lenstra-Lovasz(LLL)格基约化算法自1982年被提出以来,已被成功应用于计算机代数、编码理论、密码分析、算法数论、整数规划等众多领域。经过三十多年的发展,串行LLL算法的理论分析和实际效率都已得到显著改进,但仍不能满足密码分析等领域处理较大规模问题的需要。因此,并行LLL算法研究被寄予厚望。对并行LLL算法的研究现状进行了综述,总结了当前并行LLL算法设计与分析中存在的问题和难点,并对其未来发展趋势进行了展望。
382019,55(16) Computer Engineering and Applications计算机工程与应用 出格C的一组LL约化基,其中= naxlblb‖,即复杂法1,该算法的核心思想是对不满足定义1条件(2)的 度不超过On2+92=)。 那些相邻的向量尽可能并行地进行交换。具体来讲,这 尽管原始LLL算法已是多项式时间的算法,但其 策略分为两个阶段:在第一阶段中,当算法进入步骤3 运行效率并不理想。随后的改进大致可以分为两类 时,对所有奇数下标的基向量考祭定义1条件(2)是否 类以改进算法对n的依赖程度为目标主要采用的力)满足,若不满足,则同时交换;在第二阶段中,当接下来 式是用模算术替代原始算法中的有理算术,目前最好 次进入步骤3时,对所有的偶数下标基向量考察定 的结果归功 J Storjohann,该算法复杂度上界是义1条件(2)是否满足,若不满足,则同时交换。完整执 类以改进算法对的依赖程度为目标关键技术是将境下,(a1 o(n 2+)其中≤2.376是线性代数指数。另行以上两个阶毁次被称为次“awap”在申行环 ap'需要O(n2次算术操作。但是,因 误差可控的浮点算术引入算法中,目前最好的结果归功为基的正交化过程和规模约减这两个主要步骤都适合 并行,所以在有n2个处理器的网格上,一次“al-swap 于 Nov等该算法的复杂度上界是OX。可以在O次并行步骤(包括算术操作和通信开销)内 n+93+值得注意的是, Neumaier和Steh于2017年 提出了个新型的L算法,融入了求解SVP的BKZ的执行次数将由Om降低到On8)。但是,因为在采 ( Block Korkin- Zolotarev)算法思想,并结合模算术成功 地将复杂度上界降至Omn H前,这是理论上 用¨al-swap”策略后,算法中涉及的整数规模较难分析 所以在文献[37-38]中仅对并行LLL算法的复杂度进行 最好的结果。能否设计更快的ILL算法,进一步降低其 复杂度是一个公开问题 启发式的分析。 在实际应川中,有很多计算软件都实现了LLL算 该算法严格的复杂度分析是由 Heckler和 Thiele完 法,比如商用的 Maple、 Mathematica、 Magma,开源的 成的。同时,这篇文献还分析了基于“al-swap”策略 NTL.FLINTLO FPLLL、HPLL等。如前所述,目的其他并行LLL算法的复杂度。特别地,若采川有 前运行效率最高的是HPLL。针对LL算法,尽管有埋算术(精确算术),在nxn的网格上Roch和lrd的 的钦件包攴持多线程操作,但那是在同时计算不同格的 并行LLL算法的复杂度不超过On+2+)。从而, 1约化基意义下的并行计算都不涉及并行的算法。在n×xn的刚格上,基于“ all-swap”策略的并行IL算法 近年来,我国学者在格的理论利算法方面也取得了相对于定理1给出的串行.算法的复杂度达到了n2 不错的进展,包括王小云院士及其团队在格的转移定理的(最优)加速比。于是,“a-swap”策略成为现有并行 方面有深入研究,王源华等也研究过格中依次最短元 LL算法的基本策略。 关组与 Minkowski约化基之间的关系,温金明等改进 all-swap策略的变种如下: 了关于格的 Hermite常数的线性界四;在SVP的计算方 Wetzel给出了一个分块的“al-swap”策略,设计了 面,王小云院士团队等在筛法方面有贡献22,潘彦斌等个并行LL算法。在原始LLL算法中,可以看成局 研究了格困难问题间的规约;彭力强、毕经国等在部的块的规模是2(两个向量参与交换),在这个分块算 LLL的应用方面取得了突破。另外还有诸多关于格法中,将格的基分成了k个互不相交的块,每个块的规 算法在通信中的应用和优化3。 模是纟。当k=n时,就是串行的LLL算法。同时,实验 也指出,最佳的分块规模取决于并行系统的体系结构。 3并行LLL算法 在文献(43中,也提及了一种被称为“全序 all-swap 事实上,对于计算格中短向量这问题是否有快速的策略,即不对向量下标进行奇偶区分按照‖b‖2的排 的并行算法仍然是一个公开问题。其体的并行复杂性序结果,在同一阶段交换所有不满足定义1条件(2)的 分类以及NC规约的定义可以参考文献[35]。 von zur向量。这一策略在类似的求解整数关系问题的算法 Gathen证明了两个整数最大公因子的计算问题可以PSLQ中也被用到过,但这样的策略可能导致算法进 被N(规约到格的短向量计算问题。但计算两个整数入无限循环,借助文献[45中的修复技术,可以证明算 最大公因子这问题本身是否属于NC类也是·个公法的终止性 开问题 3.2基于近似算术的并行LLL算法 3 all-swap策略 基于有理算术的算法虽是精确的,但由于众所周知 在定理1中已经指出,申行的LLL算法所需的算法的中间过程膨胀,会大大降低相关算法的实用性。为了 操作次数不超过OnB),这可以粗略地解释为步骤3的追求效率的提高,通常会诉诸于近似算术的算法,包括 循环次数为OnB),而每次循环都需要On)次算术操基于定点数算术( Fixed-Point Arithmetic)和浮点数算术 作。1992年,Roch和ⅶ Tillard提出了首个并行ILL算( Floating-Point Arithmetic)的算法 刘洋,等:并行LLL算法研究综述 2019,55(16) 39 事实十,Joux给岀的并行LLL算法就是基丁定点4结束语 算术的。该算法实际上是将基于定点数算术的串行综上所述针对并行算法的研究尽管已有大量 ILL算法和 Roch-Villard的并行IL算法各自优势结论文发表,相关并行算法的理论分析和实际效率都有明 合起来而得到的。Joux对这个并行LLL算法也给出了显的改善,但是进一步改进的空间还很大:尤其是并行 个启发式的复杂度分析针对常用类型的格比如背)LL算法的复杂度分析尚未完成。止如Jd等听指 包格和多项式因式分解产生的格,在n2个处理器上的出的那样,有的学者在证明了所设计的LL算法在多项 复杂度不超过On2++),但这个结果建立在一个未式次算术操作内终止后便声称相应算法具有多项式的 被证明的猜想之上。 时间复杂度,但这是不科学的。因为其中涉及的浮点数 随后, Heckler和i将浮点算术应用于Roch-规模以及浮点运算的误差控制等因素都没有考虑。这 Villard并行LL算法,也提出了一个并行LL算法"。个点,从串行1I算法的发展历程可见一斑。 在n个处理器上,这个算法的并行算术操作次数不超 串行LLL算法自1982年被提出以来,效率也是在 过Om,但该法的复杂度分析难度颇人,尚未完引浮点算术后才得到显著提升。尽管基于浮点算 成。因此在随后的诸多并行I算法设计中,尽管都术的LL算法长期以来被广泛应用但是一直没有明 不约而同地采用了浮点算术,但都没有理论十的复杂度其正确性,也没有分析其复杂度。直到2005年, Nguen 分析。 和 Stehle给出了第一个严格证明的浮点LIL算法,随 后串行的基于浮点算术的严格的LLL算法被陆续提 表!并行LLL算法的复杂度 出3:,其复杂度也随之被改进。这些工作的关健在 算法 n×n的网格 于如何在LLL约化基意义下进行数值分析。这止是 基于有理算术21 OnB 基于浮点算术Omn“),启发式 并行LLL算法目前面临的最大难点。 由于并行计算打乱了原来串行DLL算法的算术操 3.3针对不同硬件平台的进一步改进 作执行秩序,导致原有的数值稳定性分析不能被移植到 对于LLL格约化算法在MIMO( Multiple- Input并行LL算法中,从而不能从理论上对算法进行前向误 Multiple-Output通信系统中的应用,有一些针对超大规差分析,也不能得到浮点数的误差控制条件,进而不能 模集成电路( Very Large Scale Integration Circuit,vLSl)保证浮点并行LLL算法的正确性和终止性。 平台而设计的LLL算法3在通信系统的应用中,所 鉴于此,在并行LLL算法的设计和分析方面,未来 处理的对象都是复数域¢上的格。对于这种情形,的研究可以从如下两方面入手:第一,设计攴持将目前 Alden等指岀对某些特殊情况,无法证明LLL算法的终串行浮点LLL算法数值分析移植过来的新型并行LLL 止性s。因此,人们通常只关心实际的运算效率,而不算法。第二,分析当前并行LL算法的数值稳定性,并 考虑算法的复杂度 进行误差控制,从理论上保证算法的正确性和终止性, 针对多线程的并行LLL算法, Backer和 Wetzel做了进而提出优化的改进方案 系列的工作。他们对可移植操作系统接口( Portable Operating SysteIn Interlace,POSX)到和多核系统3参势文献: 都分別给出了多线程的并行LLL算法。另外,Luo和1 van emde boas p another np- complete partition prob Qiao也釆用了延迟规模约减的技术设计了一个多线程 lem and the complexity of computing short vectors in 环境下的并行LLL算法 a lattice[R]. Mathenatics Deparlment, Universily of Amster- 近年来,针对GPU支持单指令多数据( Single Instruc dam,1981 lion Mulliple Data,SMD)的特点而设计的并行LL算2 Ajtai MThe shortest vector problem in L2 is NP- hard 法也陆续涌现。有的是针对LLL算法本身的改进,比如 for randomized reductions (extended abstract)[C]/ACM Jeremic和Qiao将 Jacobi条件引入格约化算法,并在 Symposium on Theory of Computing, 1998: 10-19 GPU上进行了实现;有的则是通过重新设计适合GPU【3 J Micciancio L, Regev C. Lattice-based cryptographylC'∥ 体系结构的数据结构,来优化并行LLL算法,达到加速 dings of Posl-Quanturn Cryptography. Berlin: Springer 2009:147-191 的目的mm。 [4] Hanrot G, Pujol X, Stehle D Algorithms for the shortest 然而,这些改进的加速效果并不明显。比如, Mariano and closest lattice vector problems[C]/Proceedings of 等的实验显示,在SIMD和GPU的帮助下,他们重新 Coding and Cryptology. Berlin: Springer, 2011: 159-190 设计的基于向量化数据结构的并行LL算法仅比NTL[5] Lenstra A K, Lenstra h w, Lovasz L Factoring polyno 中实现LLL计算程序提速35%。山此可见,在这方面的 nials with rational coefficients[J]. Mathematische Annalen 研究还有待进一步完善。 1982,261(4):515534 402019,55(16) Computer Engineering and Applications计算机工程与应用 16 van Hoeij M, Novocin A Gradual sub-lattice reduction 723-730 and a new complexity for factoring polynomials[J].Algo- [23]Wen J, Chany X wOn the Kz reduction[].IEEE Trans rithmica,2012,63(3):616-633 actions on Information Theory, 2019, 65(3):1921-1935 Graham NEffective LLL redue [24] Wang X, Liu M, Tian C, et al. Improv lattice decoding[C]//IEEE International Symposium on heuristic sieve algorithm for shortest vector problem[C]/ Information Theory, 2007: 196-200 ACM Asia Conference on Information, Computer and [8]Coppersmith D. Finding a small root of a univariate mod- Communications Security, 2011: 1-9 ular equation[C]International Conference on the Theory [25] Zhang F, Pan Y, Hu Gi.A three-level sieve algorithm for and Applications of Cryptographic Techniques. Heidelberg the shortest vector problem[C y/conference on Selected Springer, 1996: 155-165 O Areas in CrypTography. Heidelberg: Springer, 2013: 29-47 I Coppersmith, D Small solutions to polynomial equations,t261曹政,程庆丰.一种基于分块采样方法的格基约减算法 and low exponent RSa ulnerabilities[J]Journal of Cryp 码学报,2019,6(1):73-82 tolo,1997,10(4):233-260 [271 Zheng Z X, Wang X Y, Xu G w,et al. Orthogonalized [10 Kannan R, Lenstra A K, Lovasz L Polynomial factoriz lattice enumeration for solving SVPUJ Science China tion and nonrandomness of bits of algebraic and some In formalion Sciences, 2018 61: 032115 transcendental numbers[].Mathematics of Computation, [28] Pan Y, Zhang F Solving low-density multiple subset sum 1988,50(181):235-250 problems with SVP oracle[J] Journal of Systems Sci- [Il] Lenstra Jr H wInteger programming with a fixed num ence and Complexity, 2016, 29(1): 228-242 ber of variables[J].Mathematics of Operations Research,[29]彭力强,胡磊,黄章杰,等,模背包向量问题的实际复杂度 1983,8(4):538-548 与基于格密码体制的实际安全性门密码学报,2014,1 [12] Stehle D Lattice reduction algorithms[C]/International Sym (3):225-234 posium on Symbolic and Algebraic Computation. New [30] Bi J, Nguyen P Q Rounding and chaining LLL: finding York: ACM. 2017:11-12. laster small roots of univariate polynomial congruences[C!/ [13 Neumaier A, Stehle, D Faster LLL-type reduction of lattice International Conference on Practice and Theory of Pub bases[C]//International Symposium on Symbolic and lic Key Cryptography, 2014: 185-202. Algebraic Computation. New York: ACM, 2016: 373-380 [31] Bi J, Cheng Q, Maurice Rojas J Sublinear root detection [14] Villard G. HPLLL: software library for linear algebra and and new hardness results for sparse polynomials over Euclidean lattice problemsicp/ol]. 2019-03-19.HttP: ii finite fields[J]. SIAM Journal on Computing, 2016, 45(4) perso ens-lyon. fr/gilles. villard/hpllly 1433-1447 [15] Chen J Algorithms and experiments for computing inte- [321 Chen J W, StehleD, Villard G Computing an LLL-reduced er relations[C]/10th Conference on Computer Math basis of the orthogonal lattice C]/International Sympo matics, Wuhan. 2018 sium on Symbolic and Algebraic Computation. New York l16 Storjohann A Faster algorithms for integer lattice basis ACM,20l8:127-133 reduction[R]. Zurich: ETH, Department of Compuler Sci- [33] Zhang W, Qiao S, Wei Y HKZ and Minkowski reduc- ence. 1996 tion algorithms for lattice-reduction aided mimo detec [17 Novocin A, Stehle D, Villard G An LLL-reduction algorithm lion[J.IEEE Transactions on Signal Processing, 2012. 60 with quasi-linear time complexity: extended abstractlCii (11):5963-5976 ACM Symposium un Theory of Compuling, 2011: 403-412. [34] Zhang W, Qiao S, Wei YA diagonal lattice reduction [18 Shoup V. NTL a library for doing number theory[CP/Ol] algorithm for MIMO detection J. ILEL Signal Process [2019-03-20].https://shoup.net/nt ing Letters,2012,19(5):311-314 [191 Hart W, Johansson F, Pancratz SFLINT: fast library for [35] Cook S A. The classification of problems which have numbertheoryicp/ol]-[2019-03-20.http:/flintlib.org fast parallel algorithms[C]/Proceedings of Fundamentals 120 The FPLLL Development Team. FPLLL: a lattice reduc- of Computation Theory Berlin: Springer, 1983: 78-93 tionlibrary[cp/ol.]-[2019-03-20].https:/github.com/fplll/[36]vonZurGathenJ.Parallelalgorithmsforalgebraic fell problems[J].SIAM Journal on Computing, 1984. 13(4) [21 Wei W, Tian C, Wang X. New transference theorems on 802-824 lattices n-unique shortest vectors[J]. Discrete [37] Villard G Parallel lattice basis reduction[C]/International Mathematics,2014,315/316:144-155 ymposium on Symbolic lic and Algebraic Computation 「22]王源华,尚士魁,高峰,等格中依次最短无关组与 Minkowski York:ACM,1992:269-277 约化基等价的充分条件中国科学:数学,2010,40(8):[38] Rocha L. Villard G. Parallel gcd and lattice basis reduc 刘洋,等:并行LLL算法研究综述 2019,55(16)41 tion(C/2nd Joint International Conference on Vector complexity of LlL lattice reduction in MIMO wireless and Parallel processing. Berlin: Springer, 1992: 557-564 systems[c]2008 IEEE International Conference on Acous [39 Heckler C, Thiele L Complexity analysis of a parallel ics, Speech and Signal Processing, 2008: 268.5-2688 lattice basis reduction algorithm[]. SIAM Journal on [54] Backes W, Wetzel S. a parallel LLL using POSIX threads[RI Computing,1998,27(5):1295-1302 The Center for Discrete mathematics and Theorelical [40] Heckler C, Thiele LA parallel lattice basis/reduction Computer Science, 2008 for mesh-connected processor arrays and parallelcom-[55] Backes W, Wetzel S Parallel lattice basis reduction using plexily[c//Symposium on Parallel& Distributed Pro a multi-threaded Schnorr-Euchner LLL algorithm[C!/ cessing. Piscataway: IEEE, 1993: 400-407 European Conference on Parallel Processing. Berlin [41] Joux A. A fast parallel lattice reduction algorithm[C] Springer,2009:960-973 2nd Gauss Symposium, Munich, 1993: 1-15 56 Backes W, Wetzel S. Improving the parallel Schnorr- [42] Wetzel S An efficient parallel block -reduction algorithm[c Euchner LlL algorithm[C/2011 International Confer 3rd International Symposium on Algorithmic Number ence on Algorithms and Architectures for Parallel Pro Theory. Berlin: Springer, 1998: 323-337 cessing Berlin: Springer, 2011: 27-39 [43]-Bartkewitz T Improved lattice basis reduction algorithms 157 Backes W, Wetzel S Parallel lattice basis reduction-the and their efficient implementation on parallel systemS[D] road to many-core[C]/2011 IEEE International Confer- Bochum: Ruhr-University Bochum, 2009 ence on High Performance Computing and Co ommuni [44] Bailey D H, Broadhurst D J Parallel integer relation detec cations,20l1:417-424. tion: techniques and applications J]. Mathematics of Com [58 Luo Y, Qiao S.a parallel LLL algurithm[C]//4th Inter pulation,2000,70(236):1719-1736 national Conference on Computer Science and Soft- [45 Feng Y, Chen J, Wu W.Two variants of HJLS-PSLQ with ware Engineering. New York: ACM, 2011: 93-101 applications[ C] /International Workshop on Symbolic 59 Jeremic F. Qiao S.a parallel Jacobi-type lattice basis Numeric Computation. New York: ACM, 2014: 88-96 reduction algorithm [J]. International Journal of Numer 146 Schnorr C, Euchner M. Lattice basis reduction improved al Analysis and Modeling: Series B, 2014, 5(1/2): 1-12 practical algorithms and solving subset sum problems[J 160J Jozsa C M, Domene F, Pinero G, et aL. Efficient GPU Mathenatical Programming, 1994, 66(1): 181-199 [47 van Hoeij M, Novocin A Gradual sub-lattice reduction implementation of lattice-reduction-aided multiuser pre coding[c]/1oth International Symposium on Wireless and a new complexity for factoring polynomials J].algo Communication Systems. Piscataway: IEEE, 2013: 876-880 rithmica,2012,63(3):616-633 [48] Heckler C, Thiele L Parallel complexity of lattice basis [61 Jozsa C M, Domene F, Vidal A m,et al. High perfor- reduction and a floating-point parallel algorithm[ C]!Inter mance lattice reduction on heterogeneous computing plat nalional Conference on parallel Architectures and lan form[J]Journal of Supercomputing, 2014, 70(2): 772-785 guages Europe. Berlin: Springer, 1993: 744-747 [62 Mariano A, Correia F, Bischof CA vectorized, cache eff [49 Burg A, Seethaler D, Matz G vLSI implementation of cient LLL implementation[ C]/12th International Meeting a lattice- reduction algorithm for multi-antenna broad on High Performance Computing for Computational Sci cast precoding[C]/IEEE International Symposium on ence. Berlin: Springer, 2017: 162-173 Circuits and Systems, 2007: 673-676. [63 Schnorr C P.A more eflicient algorithm for latlice basis 50 Gestner B, Zhany W, Ma X, et al. VLSI implementation reduction[J] Journal of Algorithms, 1988, 9(1): 47-62 of a lattice reduction algorithm for low-complexity [64] Nguen P Q, Stehle DFloating-point LLL revisited[C equalization[cyi4th TEFF International Conference on Cir 24th Annual International Conference on the Theory cuits and Systems for Communications, 2008: 643-647 and Applications of Cryptographic Techniques. Berlin [51 Bruderer L, Studer C, Wenk M, et al. VLSI implementa- Springer,2005:215-233 tion of a low-complexity LLL lattice reduction algo [651 Morel I, StehleD, Villard G. H-LLL: using householder rithIn for Mimo detection C2010 IEEE International nside LlliC]/2009 InTernational Symposium on SyIn Symposium on Circuits and Systems, 2010: 3745-3748 bolic and Algebraic Computation. New York: ACM, 2009 [52 Ahmad U, Amin A, Li M, et al. Scalable block-based parallel lattice reduction algorithm for an SDR base- [66] Chang X W,Stehle D, villard G Perturbation analysis band processor[C]/2011 IEEE International Conference of the or factor r in the context of Lll lattice b on Communications. 2011: 1-5 reduction[J]. Mathematics of Computation, 2012, 81(279) 53 Alden J, Seethaler D, Matz G. Worst-and average-case 1487-1511

...展开详情
试读 6P 论文研究-并行LLL算法研究综述.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743737 欢迎大家使用并留下宝贵意见
2019-09-13
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
    最新推荐
    论文研究-并行LLL算法研究综述.pdf 36积分/C币 立即下载
    1/6
    论文研究-并行LLL算法研究综述.pdf第1页
    论文研究-并行LLL算法研究综述.pdf第2页

    试读结束, 可继续阅读

    36积分/C币 立即下载 >