格基规约相关算法的研究

发布时间：2018-04-09 08:51

本文选题：格基规约　切入点：LLL规约　出处：《深圳大学》2017年硕士论文

【摘要】：随着信息时代的快速发展,信息安全问题与我们密切相关,因而密码学逐渐成为人们日益关注的焦点。数据的安全性与保密性是密码技术的核心要素,而格基规约算法是密码学中核心要素的重要体现,它是一种典型的密码学分析技术。当前,LLL(Lenstra,Lenstra,Lovasz)是最经典的格基规约算法。而以LLL算法为基础的变体数不胜数,其目的都是为了优化。格基规约算法具有广泛的应用,例如:数论,整数规划,丢番图逼近以及密码学等方面。而本文主要从优化格基规约算法、用规约思想来初始化参数去解决球译码算法、格理论在0-1整数背包中的应用以及背包算法的并行化方面来阐述,具体内容如下:(一)格基规约是求解格中非零近似最短向量的问题,著名的LLL算法可在多项式时间内求解出可证明的约减基。l次规约是LLL算法的变体,有着更高质量的约减基,但是运行时间大幅度增加。而分块LLL规约则是约减基略差但运行时间减少明显的算法。因此,本文提出在分块LLL规约中加入l次规约的思想。有效汲取二者的优势,生成分块l次规约算法,其在时间-质量方面可达到相对权衡。(二)球译码算法是解决整数最小二乘问题的有效方法,而球译码算法的关键问题是搜索空间中初始化半径的选择。论文首先提出利用阿达玛比率选取一组高质量的基;其次提出用QR(orthogonal matrix,upper triangular matrix)分解,LLL优化规约以及带预测技术的宽度优先搜索算法K-Best(BFS+PEDS)叠加的方式来约减所选取的一组基;最后再利用球译码算法来求解,其过程等价于在格中求解最近向量问题。(三)背包问题是一个NPC(non-deterministic polynomial complete)问题,同时也是经典的组合优化问题。利用(一)中优化规约算法来提高密码分析的效率,缩短密码分析的时间。规约算法同样可应用在基于格的背包密码系统的分析上。为了深入了解背包原理,研究其常规算法的思想。因此,针对0-1整数背包,提出新生成算法的并行化来加速解决背包问题。
[Abstract]:With the rapid development of the information age, the problem of information security is closely related to us, so cryptography has gradually become the focus of attention.The security and confidentiality of data are the core elements of cryptography, and the lattice specification algorithm is an important embodiment of the core elements in cryptography. It is a typical cryptographic analysis technology.Currently, LLL Len strake Lenstraan Lovasz) is the most classical lattice-based protocol algorithm.There are numerous variants based on LLL algorithm, whose purpose is to optimize.Lattice base reduction algorithm has been widely used in many fields, such as number theory, integer programming, Diophantine approximation and cryptography.This paper mainly discusses the optimization of lattice base specification algorithm, initializing parameters to solve the ball decoding algorithm, the application of lattice theory in 0-1 integer knapsack and the parallelization of knapsack algorithm.The specific contents are as follows: (1) the lattice base reduction is a problem of solving the non-zero approximate shortest vector of lattice. The famous LLL algorithm can solve the provable reductive basis. L order reduction in polynomial time is a variant of LLL algorithm, and it has a higher quality reduction base.But the running time increases greatly.The partitioned LLL protocol is an algorithm with a slight decrease in the base and a significant decrease in the running time.Therefore, this paper puts forward the idea of adding l times protocol to block LLL protocol.Based on the advantages of the two algorithms, the block l times reduction algorithm is generated, which can achieve a relative trade-off in terms of time and quality.(2) the sphere decoding algorithm is an effective method to solve the integer least square problem, and the key problem of the ball decoding algorithm is the choice of initialization radius in the search space.In this paper, we first propose to select a group of high-quality bases by using Adama ratio, and then we propose to reduce the selected bases by using QR(orthogonal matrix upper triangular matrix decomposition and the superposition of K-Best(BFS PEDSs, a width-first search algorithm with prediction technology.Finally, the spherical decoding algorithm is used to solve the problem, which is equivalent to solving the nearest vector problem in the lattice.(3) knapsack problem is a NPC(non-deterministic polynomial complete. it is also a classical combinatorial optimization problem.In order to improve the efficiency of cryptographic analysis and shorten the time of cryptographic analysis, the optimization protocol algorithm in (1) is used to improve the efficiency of cryptographic analysis.The protocol algorithm can also be applied to the analysis of lattice-based knapsack cryptosystem.In order to understand the principle of knapsack, the idea of conventional algorithm is studied.Therefore, for 0-1 integer knapsack, a parallel algorithm is proposed to solve the knapsack problem.
【学位授予单位】：深圳大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN918.1

【参考文献】