格密码技术分析综述
在信息技术飞速发展的同时也出现了越来越严重的安全问题，各行各业的人们对于信息安全的理解越来越深刻，从最初的保密性到现在的完整性、认证性、不可否认性等要求越来越高。为了满足人们对信息安全的要求，我们通常采用最关键、最核心的技术是加密技术。早期的密码学安全性通常基于一些复杂的数学难题，例如，大整数分解问题和离散对数问题。随着量子计算机的发展,传统意义的密码学协议安全性受到了极大的挑战。在量子计算近似于无穷大的计算能力面前，当前大部分的密码协议框架与密码学理论都显得无能为力，如何匹配当前人们对数据安全强烈的要求与当前不完善的密码学体系间的矛盾，成为当前的迫切需求。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;
intbf;//平衡因子
BiTNode*lchild,*rchild;
}BiTNode,*BiTree;
图2.6平衡二叉树与非平衡二叉树