本文選題：格基規(guī)約　切入點：LLL規(guī)約　出處：《深圳大學》2017年碩士論文

【摘要】：隨著信息時代的快速發(fā)展,信息安全問題與我們密切相關(guān),因而密碼學逐漸成為人們?nèi)找骊P(guān)注的焦點。數(shù)據(jù)的安全性與保密性是密碼技術(shù)的核心要素,而格基規(guī)約算法是密碼學中核心要素的重要體現(xiàn),它是一種典型的密碼學分析技術(shù)。當前,LLL(Lenstra,Lenstra,Lovasz)是最經(jīng)典的格基規(guī)約算法。而以LLL算法為基礎(chǔ)的變體數(shù)不勝數(shù),其目的都是為了優(yōu)化。格基規(guī)約算法具有廣泛的應用,例如:數(shù)論,整數(shù)規(guī)劃,丟番圖逼近以及密碼學等方面。而本文主要從優(yōu)化格基規(guī)約算法、用規(guī)約思想來初始化參數(shù)去解決球譯碼算法、格理論在0-1整數(shù)背包中的應用以及背包算法的并行化方面來闡述,具體內(nèi)容如下:(一)格基規(guī)約是求解格中非零近似最短向量的問題,著名的LLL算法可在多項式時間內(nèi)求解出可證明的約減基。l次規(guī)約是LLL算法的變體,有著更高質(zhì)量的約減基,但是運行時間大幅度增加。而分塊LLL規(guī)約則是約減基略差但運行時間減少明顯的算法。因此,本文提出在分塊LLL規(guī)約中加入l次規(guī)約的思想。有效汲取二者的優(yōu)勢,生成分塊l次規(guī)約算法,其在時間-質(zhì)量方面可達到相對權(quán)衡。(二)球譯碼算法是解決整數(shù)最小二乘問題的有效方法,而球譯碼算法的關(guān)鍵問題是搜索空間中初始化半徑的選擇。論文首先提出利用阿達瑪比率選取一組高質(zhì)量的基;其次提出用QR(orthogonal matrix,upper triangular matrix)分解,LLL優(yōu)化規(guī)約以及帶預測技術(shù)的寬度優(yōu)先搜索算法K-Best(BFS+PEDS)疊加的方式來約減所選取的一組基;最后再利用球譯碼算法來求解,其過程等價于在格中求解最近向量問題。(三)背包問題是一個NPC(non-deterministic polynomial complete)問題,同時也是經(jīng)典的組合優(yōu)化問題。利用(一)中優(yōu)化規(guī)約算法來提高密碼分析的效率,縮短密碼分析的時間。規(guī)約算法同樣可應用在基于格的背包密碼系統(tǒng)的分析上。為了深入了解背包原理,研究其常規(guī)算法的思想。因此,針對0-1整數(shù)背包,提出新生成算法的并行化來加速解決背包問題。
[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

【參考文獻】

相關(guān)期刊論文 前2條

1 王小云;劉明潔;;格密碼學研究[J];密碼學報;2014年01期

2 余位馳;何大可;;一種新型l次格基規(guī)約算法[J];鐵道學報;2007年01期

，

本文編號：1725721