格基规约理论及其在密码设计中的应用毕业论文

《格基规约理论及其在密码设计中的应用毕业论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西南交通大学研究生学位论文及其在密码设计中的应用年级二O0二级姓名余位驰中请学位级别博士专业通信与信息系统指导教师何大可教授二oo五年七月西南交通大学博士研究生学位论文第1页摘要格基规约是格理论研究的一个重要内容，也是密码设计和分析中的一个重要工具。在理论研究中，许多格上问题都可以通过格基规约来求解(或者近似求解)。在密码学应用中，对一些密码方案的分析最终都可以等价成一个格基规约问题。因此研究新型格基规约算法不仅具有理论价值，同时也具有重要的实用价值。把密码方案的安全基础建立在已知的数学难题上是

2、密码设计常用的一种方法。一个好的密码方案除了要求是安全的，还应该是高效的。格是一种典型的线性代数结构。并且格上一些问题的困难性已经得到证明。如果利用格上难题设计新型密码方案，那么不仅可以期望方案的安全性能够得到证明，而且还可以期望格的线性结构能够使方案具有较高的运算速度。因此，在格上构造密码方案得到国内外许多学者的关注。本文以现代通信国家重点实验室开放基金课题“NTRU公开密钥密码体制的研究”(No．51436010203QT2201)为基础，对格基规约理论和基于格上难题的新型密码方案进行了研究

3、。本文前半部分研究的重点在格基规约理论研究。在这部分内容中，本文设计一种新型的格基规约算法——，次格基规约算法。这个算法得到规约基的质量不仅好于标准ELL算法，而且这个算法具有计算花费时间和规约结果质量之间可以相互转化的特点：通过牺牲更多的运算时间来获得质量更优的规约基。标准LLL算法最多仅能够解决近似因子为口p。1J／2的近似最短向量问题(app-SVP)，而相同情况下，f次格基规约算法最多能够解决近似因子为口啦的近似最短向量问题。尽管最短向量问题是NP问题，但是这并不意味着任何一个格的最短向

4、量求解都是困难的。本文提出了最短向量已知格的概念，研究了判断一类格中最短向量的两个充分条件。讨论了如何利用这两个条件快速生成最短向量已知格。本文后半部分研究的重点在利用格上难题设计构造密码方案。在这部分内容中，首先分析了几个基于格上难题的公钥密码方案，针对这些方案都存在解密错误现象，介绍了完备公钥密码方案(PPKC)和非完备公钥密码方案(IPKC)的概念，分析了PPKC和IPKC在安全特性上的一些差异，提出了针对IPKC的解密错误探测攻击模型。依据现代通信国家重点实验室开放基金课题研究的成果，本

5、文针对NTRU解密错误现象设计了高效的纠错补偿算法。在最后部分，利用前人研究的结果构造了一种基于格上难题的具有碰撞免疫特性的Hash函数。本文的主要工作有如下几个方面：第1I页西南交通大学博士研究生学位论文1．对密码学涉及的格理论知识进行了总结。分析了格基规约问题的由来和目前格基规约算法研究的进展。首次提出，次格基规约的概念，并且设计了f次格基规约算法。通过大量数值实验比较了，次格基规约和标准LLL规约算法的性能。2．提出了最短向量已知格的概念。提出并且证明了判断一类格中最短向量的两个充分条件。

6、讨论了使用这两个充分条件来生成随机最短向量已知格的技术。3．分析了几个基于格上难题的新型公钥密码方案，讨论了它们各自的特点。介绍了完备公钥密码方案和非完备公钥密码方案的概念。比较了这两种方案对不同攻击方法抵抗能力上的差别。提出针对非完备公钥密码方案的解密错误探测攻击模型。4．深入研究了NTRU解密错误的机制，提出了保证NTRU无解密错误参数选择的理论界。针对NTRU解密错误现象设计了补偿算法，实现对NTRU解密错误的纠错。5．分析了LMAC设计中存在的一个问题。利用Goldreich压缩函数设计

7、了具有碰撞免疫特性的GHash函数。证明了GHash函数具有的一些安全特性，提出了安全GHash函数的两套基本参数集，讨论了GHash的几种应用。关键词：信息安全；公钥密码；格基规约；Hash函数西南交通大学博士研究生学位论文第1II页Abs仃actLatticereductioniSnotonlyallimportanttaskoflatticeresearchbutalSOapowerfultoolforcryptology．ManylatticeproblemsCanbesolvedbyl

8、atticereductiondirectly,andevensomeNP-hardlatticeproblemscallbeapproximatelysolvedbyreduction．Ontheotherhand，somecryptanalysisCanbereducedtolatticereductionproblems．Therefore，todesignnewlatticereductionalgorithmshasgreatvalueinlatticeresearchaswellas