格是m维实空间Rm正规排列的点阵,从数学的角度看,格是Rm上的一个离散加法子群。格基约化的思想源于18世纪Lagrange、Gauss等人的二次型的约化理论和19世纪末Minkowski的数的几何的研究。自从著名的LLL算法在1982年被提出,到如今30年的时间里,格理论在数学、密码学、理论计算机等领域都得到了广泛的应用和发展。在数学和公钥密码分析方面,LLL算法及其他格基约化算法作为有效的工具得到了广泛的应用(文献对格基约化算法进行了很好的总结)。很多数学问题可以通过转化为格基约化算法可求解的问题而得到解决。比如,有理数域上单变元多项式的分解问题,变量个数固定的整数规划问题等。在公钥密码体制的安全性分析领域,格基约化算法作为有效的攻击工具成功评估了多个密码体制的安全性,包括背包型密码体制的破解,RSA公钥加密算法的弱密钥攻击,针对特殊形式的DSA和ECDSA的攻击等。此外,从理论计算机的角度看,格理论中的很多问题被证明是NP-困难的,密码学家可以设计出基于格理论中困难问题的密码体制,比如,基于uSVP (?)司题的Ajtai-Dwork公钥加密算法,基于SIS问题的数字签名算法以及基于LWE问题的公钥加密体制等。在量子计算机的模型下,Shor发现了求解因子分解和离散对数问题的多项式时间算法,目前,在量子计算机的模型下,还未找到求解NP-困难问题的有效算法。故而,基于格理论中困难问题的密码体制的分析与设计成为了备受关注的“后量子时代密码体制”的研究热点之一。本文针对格理论在公钥密码体制的安全性分析和计算代数方面的应用做了一些研究。主要工作包括给出了随机NTRU格中的最短向量长度的下界估计；对基于向量空间的一个同态加密体制进行了安全性分析,成功破解了设计者推荐的三组参数；对基于中国剩余定理的快速公钥加密算法,给出了一个启发式攻击。此外,利用格基约化算法,给出了判定有限域Fq上单变元稀疏多项式是否存在解的关于q的sub-linear的确定性算法。1、随机NTRU格的最短向量长度的下界估计给定一个n维格(?),如何寻找格(?)中的最短向量的问题是计算格理论中最重要的问题之一。关于最短向量长度的上界估计,可以由著名的Minkowski凸体定理得出,即,如果一个球的体积大于2ndet((?)),那么在这个球中必存在一个非零格点,从而,格中最短向量的长度小于(?)det(L)1/n。对于一个随机格,可以通过Gaussian Heuristic来“预测”这个格的最短向量的“平均”长度,即,给定一个行列式是det((?))的n维格(?),Gaussian Heuristic预测在Rn上的可测集(?)中,包含Vol(((?))/det((?))个格点,其中Vol((?))是可测集(?)的体积。取(?)为球心在原点的n维球,由Gaussian Heuristic可以得出,当Vol((?))≈det((?))时,可测集(?)中含有一个非零格向量。换句话说,最短向量的长度近似于体积是det((?))的球的半径,即(?)det((?))1/n。在本文的第一个工作中,利用Kolmogorov复杂度的理论,给出了估计一类随机整数格的最短向量长度的下界的一般方法。作为该方法的一个重要的应用,给出了随机NTRU格最短向量长度的下界估计。目前,NTRU公钥加密体制是IEEE P1363.1的标准之一。密码体制的加解密运算是在多项式环Z[X/(XN-1)上进行的。定义Sf和Sg分别为单变元多项式环Z[X]上的最高次数是N-1,系数很小的多项式的集合。设q是一个正整数,选取多项式f(x)∈Sf和g(x)∈Sg。设多项式h(x)=∑i=0N-1hixi满足h(x)f(x)=g(χ)(mod q,xN-1).定义循环矩阵：定义NTRU格：通过NTRU格中的短向量可以得到NTRU密码体制的等价密钥。因此,对于NTRU格的短向量的性质的研究对于评估NTRU密码体制的安全性有着重要的作用。如果多项式f(x)是集合Sf上随机选取的可逆元素,多项式g(x)随机选取自集合Sg,我们称NTRU格是(Sf,Sg)-随机的。值得注意的是,Gaussian Heuristic对于随机的NTRU格是不适用的。由Gaussian Heuristic可以得出,最短向量的长度约为Ω((?))。但是,由多项式f(x),g(x)的系数构成的向量长度为O((?))。由于多项式f和g的系数都很小,许多密码研究人员猜测向量T是NTRU格的最短向量,但是,至今没有给出严格的证明。在本文的第一个工作中,给出了估计一类随机整数格的最短向量长度下界的一般方法,作为该方法的一个重要应用,考虑了随机NTRU格的最短向量长度的下界估计,证明了NTRU格中最短向量的长度和私钥(f(x),g(x))的系数构成的向量的长度之间的比例至少是一个与维数无关的常数。2、对ISIT2008上的同态加密算法的安全性分析在1978年,Rives、Adleman和Dertouzos首次提出了同态加密的思想。此后,同态加密的思想得到了广泛的应用,比如,电子投票系统、私密信息检索协议等。同态加密算法可以描述为：给定两个消息m1,m2,满足这里⊕和⊕分别代表明文、密文空间的运算。通常,如果⊕代表明文空间中的模加运算,称这个体制为加同态的加密体制,如果⊕代表乘运算,则称为乘同态的加密体制。如果在同态加密协议中,只允许对密文进行有限步的操作,称为“受限制”同态加密体制,例如文献中提出的同态加密体制等。如果在同态加密协议中,允许对密文进行任意次的加法和乘法操作,则称为“完全’同态加密体制。最近,Gentry提出了基于理想格的“完全”同态加密体制,随后,基于其他数学困难问题的“完全”同态加密体制被提出,比如,基于近似最大公因子问题和基于环上的LWE问题的同态加密体制等。本文的第二个工作是对一个基于向量空间的“受限制”同态加密体制进行了等价密钥攻击。这个密码体制是由Aguilar Melchor, Castagnos和Gaborit[35]在ISIT2008上提出的(为方便描述,简称为MCG算法)。MCG算法的安全性依赖于计算背包向量问题的困难性。根据设计者推荐的参数设置,最好的恢复明文的方法是求解一个维数至少是600的短向量问题。通过对MCG同态加密体制的密钥生成算法的分析,首先,揭示了一个公钥和密钥生成过程中的一个临时私钥之间的隐藏线性关系；然后,由部分公钥构造一个维数远小于600的维数约减的格,通过求解这个新格的N个CVP实例,恢复出隐藏的噪声矩阵；最后,通过简单的数学操作,可以从这个噪声矩阵恢复出一系列的等价密钥。实验表明,我们的攻击对于所有的三组推荐参数都是实际有效的。3、基于中国剩余定理的快速公钥加密算法的安全性分析在1976年,密码学家Diffie和Hellman[44]首次提出了通过基于数学难题的单向陷门函数来构造公钥加密算法的思想。目前,应用最广泛的两大传统公钥算法包括基于整数分解问题的RSA公钥加密算法和基于有限域或者椭圆曲线上有理点群的离散对数问题的Elgamal公钥加密体制。由于这两大算法的加解密操作均需要进行运算量较大的模指数运算,不利于在一些资源受限的设备上应用。因此,设计安全性高、同时密钥生成、加解密速度快的公钥密码体制成为重要的研究方向。基于背包问题的密码算法是一种快速公钥加密体制,其加解密过程只需要模乘法和加法运算,不幸的是,从最初的Merkle-Hellman算法到后来的Chor-Rivest密码体制都被破解了。Wang等人设计了一个基于中国剩余定理的快速加密算法,在加解密过程中,只需要几个大整数的模乘法运算。相比于RSA、Elgamal算法,加解密速度要快很多。本文的第三个工作是对这个快速加密算法给出了一个启发式攻击,基本的思想是,通过构造格,把要恢复的明文转化成寻找格的短向量或者格中距离目标向量较近的格向量的问题。由于构造格的维数很低,调用格基约化算法即可恢复出明文。4、有限域上单变元稀疏多项式解的存在性判定本文的第四个工作考虑了格基约化理论在计算代数上的应用,主要研究了有限域上单变元稀疏多项式解的存在性判定问题。即给定有限域Fq,以及单变元t项多项式判定多项式f(x)在Fq是否存在解的问题。利用格基约化算法,给出了一个可以在4t+o(t)qt-2/t-1o(1)的时间内求解这个问题的确定性算法。当项数t固定时,这个算法是第一个关于q的sub-linear算法,同时也解决了Erich Kaltofen提出的在关于q的sub-linear时间内判定三项式在Fq上是否有根存在的公开问题。