早在1994年,Shor[1]就提出了分解大整数和求解离散对数问题的多项式时间量子算法。近年来,随着量子计算的高速发展,传统公钥密码学面临着严峻挑战,因此研究抗量子攻击的密码体制被提升到一个前所未有的高度。其中,格密码体制是近十多年来逐步建立并向实用化密码体制发展的新型密码体制,是未来抗量子计算攻击公钥密码体制核心研究领域。格是n维实空间中一类具有周期结构离散点的集合。具体地,格是Rn中n个线性无关的向量b1,…,b所有整系数线性组合构成的集合,其中b1,…,bn称为格的一组基。它是数的几何中一个经典研究对象,来源于17世纪对球堆积问题的研究。现在,在密码分析和密码体制设计方面,格理论都有很重要的应用。方面,解决格中困难问题的有效算法转变为公钥密码分析的重要工具,利用格基约化等工具已成功分析多个经典公钥密码体制,例如小加解密指数的RSA体制[2,3],背包密码体制[4-6],NTRU[7]等。另一方面,Ajtai[8]在1996年开创性的给出了格困难问题的worst-case至(?)average-case的归约,即证明了一类随机格的短向量问题(SIS)的困难性至少等价于最坏情况下格中计算问题的困难性,这使得基于格的陷门单向函数的设计成为可能,开启了基于格的密码学大门。目前,格密码体制的安全性大多基于格中计算问题的困难性。因此,对格中困难问题的研究是基于格的密码学的核心研究内容。格理论中最重要的计算困难问题有最短向量问题(SVPγ)、最近向量问题(CVPγ)以及最短线性无关向量问题(SIVPγ),其中γ≥1表示近似因子。1.格上的高斯测度不等式及主对偶格的反转定理作为用分析方法研究几何问题的重要工具,高斯测度在格问题的研究中发挥了重要作用。对任意的实数s＞0,定义以c∈Rn为中心,s为伸缩因子的高斯密度函数为Vx∈Rn,ρs,c(x)=e-π‖x-c‖2/s2给定格L∈Rn,其上的离散高斯测度定义为(?)x∈L,DL,s,c(x)=ρs,c(x)/,ρs,c(L)其中ρs,c(L)=∑v∈Lρs,c(v)。当s=1或c=0时,通常略去下标。Banaszczyk[9]首次研究了格上离散高斯测度的基本性质,通过矩估计、导数计算等复杂的推导,给出了的两个重要的测度不等式,即证明了对任意的n维格L,向量u∈Rn及实数c＞(?),有其中表示l2范数n维闭单位球。Banaszczyk利用这两个测度不等式,改进了之前的主对偶格的反转定理,在相差一个常数因子情况下获得了最优的上界,即对任意的n维格L及其对偶格L*,λ1(L,Bn(2))λn(L*,Bn(2))≤n,其中,对任意的关于原点中心对称的凸体U及1≤i≤n,λi(L, U):=inf {r>0:dim(span(L n rU))≥i}为格L在凸体U诱导的度量下的第i个逐次最小值。基于相同的测度不等式,通过对格结构更加细致的分析,Cai[13]又推广了Banaszczyk的结果,即证明了存在绝对常数C＞0,使得对任意的n维格L及1≤i≤n,有λi(L,Bn(2))vn-i+1(L*,Bn(2))≤Cn,其中,对任意的关于原点中心对称的凸体U,v1(L,U)定义为使得rU中包含i个可扩充为格L的一组基的线性无关向量的最小正实数r。2000年,Klein[10]首次利用整数上的离散高斯测度给出了一个求解目标向量距格很近时的最近向量问题的多项式时间算法,但文中并没有给出s较小时依离散高斯分布采样整数的具体算法。随后,Gentry等[12]给出了一个s较大时整数格上的离散高斯测度不等式,并由此说明拒绝采样算法可在多项式时间内依离散高斯分布返回一个整数,且进一步证明了Klein算法在伸缩因子s较大时可以依离散高斯分布输出一个格点。此外,格上的离散高斯测度在计算复杂性理论与格密码体制的安全性证明中也有重要应用。文献[11,12]将这一强有力的工具用于格困难问题的归约,用之设计了一种有效的随机采样格点的方法,改进了Ajtai的worst-case至(?)average-case的归约因子,得到了目前最好的结果。基于格上的离散高斯测度不等式,Aharonov与Regev[14]定义了一个能很好地区分目标向量与格距离大小的函数,由此证明了间隔因子为(?)的最近向量问题(GapCVP(?)n)不可能是NP-hard的。Regev[15]则利用这两个测度不等式设计了一个安全性基于计算最难格的唯一最短向量问题(uSVP)的格公钥密码体制。因此,格上高斯测度不等式的研究具有重要意义,任何本质的改进都将影响已有的格困难问题的分析结果与格密码体制的安全性。本文第三章首先分析了整数上离散高斯测度,给出了一个与光滑参数无关的测度不等式,进而说明拒绝采样算法同样适用于伸缩因子相对较小时的离散高斯分布,完善了Klein算法的理论分析；其次用一个简洁、易懂的证明改进了Banaszczyk[9]给出的一般格上的测度不等式,即证明了对任意的n维格L,向量u∈Rn及实数c＞(?),有其中(?)。进一步,利用Banaszczyk[16]给出的一般lp范数下格上高斯测度不等式把Cai[13]的反转定理推广到lp范数,获得了比简单利用常规范数不等式推广更紧的上界,深化了主对偶格的结构关系。即证明了对任意的n维格L,1≤p,q<∞,i=1,2,…,n,存在正常数C1,C2,C3使得如下结论成立,特别地,当1/p+1/q=1时,其中Bn(p)与Bn(∞)分别表示lp与l∞范数下的n维闭单位球。2.格上的离散拉普拉斯测度及其在CVPP问题中应用格上离散高斯测度的引入为格结构、格中困难问题以及基于格的密码体制的研究提供了强有力的工具。是否存在其他测度工具能在格问题的研究中找到应用呢?基于以上想法,第四章推广了高斯测度,定义了格上的拉普拉斯测度,并将其应用于格困难问题的研究。对任意的向量c,x∈Rn及实数s>0,定义以向量c为中心,以s为伸缩因子的拉普拉斯密度函数,记为其中‖·‖1表示l1范数度量。便于书写,对任意的可数集A,对任意的格L,定义格上的离散拉普拉斯分布EL,s,c为在编码或基于格的密码系统中,译码或解密过程中通常对应着求解最近向量问题。此时,格L一般是公开的,因此允许接收者或攻击者对格进行任意形式的预处理,且编码理论中的度量一般为l1范数度量,因此考虑l1范数度量下带预处理的最近向量问题具有重要的实际意义。在本文第四章中,我们研究了格上离散拉普拉斯测度的基本性质,得到了两个有用的格上拉普拉斯测度不等式,并将其应用于带预处理的最近向量问题研究,得到了一个求解l1范数下间隔因子为O(n/log n)的GapCVPP问题的多项式时间算法,改进了简单利用范数不等式推广Aharonov与Regev的工作[14]所得到的结果,部分解决了Peikert[17]在计算复杂性会议CCC2007上提出的一个公开问题。同时格上离散拉普拉斯测度的引入为格上其他困难问题的研究提供了潜在新工具。3.格中困难问题的有效归约格的最短向量问题(SVPy)与最近向量问题(CVPγ)是格理论中研究的最为广泛的两个问题,而Ajtai[8]与Regev[18]的工作表明所有基于随机格的短向量问题(SIS)与LWE问题设计的格密码体制的安全性都依赖于最短线性无关向量问题(SIVPy)的困难性。因此一个自然的问题就是比较SIVPy与SVPγ、CV凡的难易程度。为了研究SIVPγ问题的困难性,Blomer与Seifert[19]首次给出了精确CVP问题到精确SIVP司题的确定多项式归约,但不保持格的秩。Miccinacio[20]结合主对偶格反转定理改进了上述结果,得到一个保持格的秩的确定多项式时间归约。通过对格结构的细致刻画,文献[20]还给出了一个从SIVPγ至(?)CVPγ的保持秩与逼近因子的多项式时间归约,这说明精确CVP问题与精确SIVP问题是等价的。对逼近因子较大时,SIVPγ与SVPγ、CVPγ之间的关系目前还知之甚少。对此,Miccinacio[20]在离散算法国际会议SODA2008上提出了以下两个公开问题。公开问题1：最短向量问题(SVPγ)与最短线性无关向量问题(SIVPγ)之间是否存在保持格的秩与逼近因子的确定多项式时间归约?这两个问题是等价的,不可比较的,还是一个严格难于另一个?公开问题2：是否存在最近向量问题(CVPγ)到最短线性无关向量问题(SIVPγ)的保持格的秩与逼近因子的确定多项式时间归约?本文第五章对Miccinacio提出的这两个问题进行了重要探索。研究了最短向量问题与最短线性无关向量问题之间的关系,给出了SIVPγ(?)n至(?)SVPγ的一个保持格的秩的确定多项式时间归约,使最短线性无关向量问题归约因子由目前的γ2(?)降为γ(?)；其次,研究了某些较弱条件或特殊情况下最近向量问题与最短线性无关向量问题的关系,当目标向量距格距离较大时,在SIVPγ谕示下,利用Babai的最近平面算法可求解这一特殊的最近向量问题,其中近似因子2γ(?)n,并且对随机选取的目标向量,该算法是以不小于1/2的概率会得到正确解。特别地,当谕示问题的逼近因子γ∈(1,2)时,我们得到了更好的结果。当目标向量距格的距离较近时,我们详细清晰地阐述了Klein算法的去随机化算法,并从理论上严格分析了其时间复杂度,由此给出了BDDc/vn(?)(?)SIVPγ(?)(?)一个确定多项式时间归约,这里c为任一给定的常数。