格基规约是格理论研究的一个重要内容,也是密码设计和分析中的一个重要工具。在理论研究中,许多格上问题都可以通过格基规约来求解（或者近似求解）。在密码学应用中,对一些密码方案的分析最终都可以等价成一个格基规约问题。因此研究新型格基规约算法不仅具有理论价值,同时也具有重要的实用价值。 把密码方案的安全基础建立在已知的数学难题上是密码设计常用的一种方法。一个好的密码方案除了要求是安全的,还应该是高效的。格是一种典型的线性代数结构,并且格上一些问题的困难性已经得到证明。如果利用格上难题设计新型密码方案,那么不仅可以期望方案的安全性能够得到证明,而且还可以期望格的线性结构能够使方案具有较高的运算速度。因此,在格上构造密码方案得到国内外许多学者的关注。 本文以现代通信国家重点实验室开放基金课题“NTRU公开密钥密码体制的研究”（No.51436010203QT2201）为基础,对格基规约理论和基于格上难题的新型密码方案进行了研究。本文前半部分研究的重点在格基规约理论研究。在这部分内容中,本文设计一种新型的格基规约算法——l次格基规约算法。这个算法得到规约基的质量不仅好于标准LLL算法,而且这个算法具有计算花费时间和规约结果质量之间可以相互转化的特点:通过牺牲更多的运算时间来获得质量更优的规约基。标准LLL算法最多仅能够解决近似因子为α^（n-1）/2的近似最短向量问题（app-SVP）,而相同情况下,l次格基规约算法最多能够解决近似因子为α^1/2的近似最短向量问题。尽管最短向量问题是NP问题,但是这并不意味着任何一个格的最短向量求解都是困难的。本文提出了最短向量已知格的概念,研究了判断一类格中最短向量的两个充分条件。讨论了如何利用这两个条件快速生成最短向量已知格。本文后半部分研究的重点在利用格上难题设计构造密码方案。在这部分内容中,首先分析了几个基于格上难题的公钥密码方案,针对这些方案都存在解密错误现象,介绍了完备公钥密码方案（PPKC）和非完备公钥密码方案（IPKC）的概念,分析了PPKC和IPKC在安全特性上的一些差异,提出了针对IPKC的解密错误探测攻击模型。依据现代通信国家重点实验室开放基金课题研究的成果,本文针对NTRU解密错误现象设计了高效的纠错补偿算法。在最后部分,利用前人研究的结果构造了一种基于格上难题的具有碰撞免疫特性的Hash函数。 本文的主要工作有如下几个方面: