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