格密碼技術(shù)分析綜述在信息技術(shù)飛速發(fā)展的同時(shí)也出現(xiàn)了越來(lái)越嚴(yán)重的安全問(wèn)題，各行各業(yè)的人們對(duì)于信息安全的理解越來(lái)越深刻，從最初的保密性到現(xiàn)在的完整性、認(rèn)證性、不可否認(rèn)性等要求越來(lái)越高。為了滿足人們對(duì)信息安全的要求，我們通常采用最關(guān)鍵、最核心的技術(shù)是加密技術(shù)。早期的密碼學(xué)安全性通?；谝恍?fù)雜的數(shù)學(xué)難題，例如，大整數(shù)分解問(wèn)題和離散對(duì)數(shù)問(wèn)題。隨著量子計(jì)算機(jī)的發(fā)展,傳統(tǒng)意義的密碼學(xué)協(xié)議安全性受到了極大的挑戰(zhàn)。在量子計(jì)算近似于無(wú)窮大的計(jì)算能力面前，當(dāng)前大部分的密碼協(xié)議框架與密碼學(xué)理論都顯得無(wú)能為力，如何匹配當(dāng)前人們對(duì)數(shù)據(jù)安全強(qiáng)烈的要求與當(dāng)前不完善的密碼學(xué)體系間的矛盾，成為當(dāng)前的迫切需求。Shor于1994年發(fā)表相關(guān)著作，描述了量子理論下的基于分解因子和離散對(duì)數(shù)的困難問(wèn)題的求解辦法。1996年Ajm提出了關(guān)于格上相關(guān)難題可以有效抵抗量子計(jì)算的攻擊,使得構(gòu)造格密碼方案成為可能，這個(gè)結(jié)論極大剌激了格密碼學(xué)的發(fā)展與創(chuàng)新，吸引了相關(guān)領(lǐng)域?qū)＜业淖⒁饬?，為格密碼理論的發(fā)展做出了巨大貢獻(xiàn)，并且為構(gòu)造新型的公鑰密碼體制提供了一條嶄新的思路。鑒于上述特性，近幾年基于格難題來(lái)分析與構(gòu)造新型公鑰密碼體制的研究已經(jīng)成為國(guó)際和國(guó)內(nèi)密碼學(xué)研究的一個(gè)熱點(diǎn)。量子計(jì)算機(jī)的未來(lái)發(fā)展可能會(huì)使大多數(shù)傳統(tǒng)的非對(duì)稱密碼原語(yǔ)變得不安全。幸運(yùn)的是，格密碼學(xué)仍然可以安全地抵御對(duì)手使用量子計(jì)算機(jī)的攻擊。它為后量子時(shí)代密碼學(xué)提供了最好的前景，因?yàn)樗哂谢谧顗那闆r困難的非常強(qiáng)的安全性證明，以及有效的實(shí)現(xiàn)?，F(xiàn)在我們按如下方式介紹格：定義1：格是m維空間Rm的n(m≥n)個(gè)線性無(wú)關(guān)組b1,b2,…,bn的整系數(shù)線性組合，即Λ={Σi=1定義2：對(duì)于矩陣A∈Zqn×mΛqΛqΛ定義3：對(duì)于任意參數(shù)δ>0，定義Rm上以r為中心的高斯函數(shù)為ρδ,r(χ)=exp(?π||χ?r||2/δ2) 我們定義格問(wèn)題上的困難假設(shè)如下：定義4：非齊次小整數(shù)解問(wèn)題（ISIS）：給定一個(gè)質(zhì)數(shù)q，一個(gè)矩陣A∈Zqn×m，一個(gè)向量y∈Zqn，一個(gè)正實(shí)數(shù)ζ，目標(biāo)是找一個(gè)非零整數(shù)向量 類似的，小整數(shù)解問(wèn)題（SIS）要求找到一個(gè)非零整數(shù)向量?∈Zm，使得A?=0modq且||?||≤ζ。對(duì)任意有界ζ=poly(n)和任意質(zhì)數(shù)q>ζ?ω(nlogn 陷門生成算法和原像采樣函數(shù)（PSF）介紹如下：引理1：存在一個(gè)概率多項(xiàng)式時(shí)間算法（PPT）TrapGen(q,n)輸出(A∈Zqn×m,TA∈Zm×m)，其中引理2：對(duì)任意質(zhì)數(shù)q，整數(shù)m≥2nlogq，PPT算法SamplePre(A,TA,y,δ)輸入一個(gè)矩陣A∈Zqn×m，一個(gè)短格基TA∈Zm×m，一個(gè)向量y∈ 現(xiàn)在我們介紹格委托技術(shù)NewBasisDel。我們首先描述Zqm×m上矩陣的分布Dm×m，定義為(引理3：PPT算法NewBasisDel(A,R,TA,σ)輸入一個(gè)秩n矩陣A∈Zqn×m，一個(gè)來(lái)自分布Dm×m可逆矩陣R，一個(gè)Λq⊥(A)上的短格基TA計(jì)算TB`={R輸入TB`和Λq⊥(B)上任意格基，輸出一個(gè)Λ執(zhí)行算法RandBasis(TB``,σ)輸出一個(gè)2.5平衡二叉樹平衡二叉樹(AVL樹)是一個(gè)具有以下性質(zhì)的二叉排序樹：(1)平衡二叉樹的左子樹和右子樹也是平衡二叉樹，且左子樹和右子樹深度的絕對(duì)值之差不超過(guò)1。(2)平衡因子(BalanceFactor,BF)的定義為二叉樹結(jié)點(diǎn)左子樹的高度減去右子樹的高度。對(duì)于一棵滿足平衡二叉樹性質(zhì)的二叉樹，BF只能取?1，0和1。平衡二叉樹的結(jié)點(diǎn)結(jié)構(gòu)定義如代碼清單2.1所示，每個(gè)平衡二叉樹的結(jié)點(diǎn)結(jié)構(gòu)包括一個(gè)數(shù)據(jù)域，平衡因子和左右指針域。圖2.5(1)顯示了兩棵平衡二叉樹，圖2.6(2)顯示了兩棵非平衡二叉樹，樹中結(jié)點(diǎn)的值為平衡因子。對(duì)于一棵滿足AVL樹性質(zhì)的二叉樹，BF只能取?1，0和1，否則，該樹為非平衡二叉樹。代碼清單2.1平衡二叉樹結(jié)點(diǎn)結(jié)構(gòu)定義typedefstructBiTNode{intdata;intb