论文题目: 格基规约理论及其在密码设计中的应用
论文类型: 博士论文
论文专业: 通信与信息系统
作者: 余位驰
导师: 何大可
关键词: 信息安全,公钥密码,格基规约,函数
文献来源: 西南交通大学
发表年度: 2005
论文摘要: 格基规约是格理论研究的一个重要内容,也是密码设计和分析中的一个重要工具。在理论研究中,许多格上问题都可以通过格基规约来求解（或者近似求解）。在密码学应用中,对一些密码方案的分析最终都可以等价成一个格基规约问题。因此研究新型格基规约算法不仅具有理论价值,同时也具有重要的实用价值。 把密码方案的安全基础建立在已知的数学难题上是密码设计常用的一种方法。一个好的密码方案除了要求是安全的,还应该是高效的。格是一种典型的线性代数结构,并且格上一些问题的困难性已经得到证明。如果利用格上难题设计新型密码方案,那么不仅可以期望方案的安全性能够得到证明,而且还可以期望格的线性结构能够使方案具有较高的运算速度。因此,在格上构造密码方案得到国内外许多学者的关注。 本文以现代通信国家重点实验室开放基金课题“NTRU公开密钥密码体制的研究”（No.51436010203QT2201）为基础,对格基规约理论和基于格上难题的新型密码方案进行了研究。本文前半部分研究的重点在格基规约理论研究。在这部分内容中,本文设计一种新型的格基规约算法——l次格基规约算法。这个算法得到规约基的质量不仅好于标准LLL算法,而且这个算法具有计算花费时间和规约结果质量之间可以相互转化的特点:通过牺牲更多的运算时间来获得质量更优的规约基。标准LLL算法最多仅能够解决近似因子为α（n-1）/2的近似最短向量问题（app-SVP）,而相同情况下,l次格基规约算法最多能够解决近似因子为α1/2的近似最短向量问题。尽管最短向量问题是NP问题,但是这并不意味着任何一个格的最短向量求解都是困难的。本文提出了最短向量已知格的概念,研究了判断一类格中最短向量的两个充分条件。讨论了如何利用这两个条件快速生成最短向量已知格。本文后半部分研究的重点在利用格上难题设计构造密码方案。在这部分内容中,首先分析了几个基于格上难题的公钥密码方案,针对这些方案都存在解密错误现象,介绍了完备公钥密码方案（PPKC）和非完备公钥密码方案（IPKC）的概念,分析了PPKC和IPKC在安全特性上的一些差异,提出了针对IPKC的解密错误探测攻击模型。依据现代通信国家重点实验室开放基金课题研究的成果,本文针对NTRU解密错误现象设计了高效的纠错补偿算法。在最后部分,利用前人研究的结果构造了一种基于格上难题的具有碰撞免疫特性的Hash函数。 本文的主要工作有如下几个方面:
论文目录:
第1章 绪论
1.1 密码学研究的新动向
1.2 国内外研究现状分析
1.2.1 格基规约算法研究进展
1.2.2 格理论在密码设计中研究进展
1.2.3 格基规约在密码分析中的研究进展
1.3 本文的技术路线
1.4 本文的主要内容
第2章 基本概念和结论
2.1 格的定义
2.2 格的特点
2.3 子格
2.4 对偶格(DUAL LATTICE)
2.5 正交格(ORTHOGONAL LATTICE)
2.6 MINKOWSKI几个有关结论
2.6.1 几个概念：
2.6.2 Minkowski第一定理：
2.6.3 Minkowski第一不等式：
2.6.4 Minkowski第二不等式
2.6.5 Minkowski第二定理
2.7 格上的难题
第3章 格基规约
3.1 格基正交性与基向量长度的内在联系
3.2 格基正交化与准正交化规约
3.3 MINKOVSKI规约
3.4 KORKINE-ZOLOTAREFF规约
3.5 高斯规约
3.5.1 基本定义和性质
3.5.2 高斯规约算法
3.6 LLL规约
3.6.1 基本定义
3.6.2 LLL规约基的基本性质
3.6.3 标准LLL规约算法
3.7 BKZ规约
3.8 l次规约
3.8.1 l次规约的基本性质
3.8.2 l次规约算法
3.8.3 测试结果
3.8.4 结论和改进
第4章 最短向量已知格
4.1 利用循环格生成最短向量已知格
4.1.1 利用二维循环格生成最短向量已知格
4.1.2 利用三维循环格生成最短向量已知格
4.1.3 利用n维循环格生成最短向量已知格
4.2 更加随机的最短向量已知格
4.2.1 伪循环格
4.2.2 随机等价线性变换
第5章 基于格理论的PKCS和对NTRU的研究
5.1 AD公钥密码算法
5.1.1 基础知识
5.1.2 AD密码算法基本思想
5.1.3 对AD系统的分析
5.2 GGH公钥算法
5.2.1 基础知识
5.2.2 GGH密码算法基本思想
5.2.3 GGH安全性分析
5.3 NTRU公钥密码方案
5.3.1 基本符号和概念
5.3.2 NTRU加密方案的描述
5.3.3 NTRU安全性分析
5.4 解密错误探测攻击
5.4.1 公钥密码典型攻击方式对PPKC的IPKC不同的影响
5.4.2 对NTRU的一种ESA攻击
5.4.3 增加NTRU抵抗ESA攻击的能力
5.5 NTRU解密错误研究
5.5.1 NTRU解密错误分析
5.5.2 NTRU参数与解密错误发生的关系
5.5.3 NTRU无解码错误的充分条件
5.5.4 NTRU参数优化
5.5.5 NTRU解密错误的纠正的新算法——补偿算法
5.5.6 一个解密错误的实例和采用补偿算法纠错
第6章 一种基于格上难题的HASH函数
6.1 格上的一个难题
6.2 压缩函数lc和LMAC
6.3 基于O.GOLDREICH压缩函数的新型的HASH算法
6.3.1 GHash算法描述
6.3.2 GHash的安全性分析
6.3.3 GHash参数选择
6.3.3 GHash性能分析
6.4 基于GHASH的应用
结论
致谢
参考文献
攻读博士学位期间发表的论文及科研成果
发布时间: 2006-03-06
参考文献
- [1].基于辫群的密码方案的设计与分析[D]. 王励成.上海交通大学2007
- [2].基于格与压缩感知的密码方案研究[D]. 谢冬.北京邮电大学2017
- [3].基于格的密码方案的研究与设计[D]. 蒋亚丽.山东大学2011
- [4].KDM安全及其相关密码方案研究[D]. 来齐齐.西安电子科技大学2015
- [5].可视密码技术的研究[D]. 韩妍妍.西安电子科技大学2009
- [6].标准模型下适应性安全门限密码方案的研究[D]. 甘元驹.北京邮电大学2013
相关论文
- [1].RSA密码算法的格攻击技术研究[D]. 郑永辉.解放军信息工程大学2009
- [2].后量子安全的格公钥密码设计[D]. 王凤和.西安电子科技大学2012
- [3].格理论在公钥密码分析和计算代数中的应用[D]. 毕经国.山东大学2012
- [4].格密码体制困难问题研究[D]. 刘明洁.清华大学2012
- [5].格基约化算法并行化及应用研究[D]. 刘向辉.解放军信息工程大学2013
- [6].基于格困难问题的公钥加密算法的设计与安全性证明[D]. 牟宁波.西安电子科技大学2009
- [7].基于格的密码方案的研究与设计[D]. 蒋亚丽.山东大学2011
- [8].抗选择密文攻击公钥密码体制的研究[D]. 梅其祥.西南交通大学2005
- [9].基于双线性对的数字签名体制研究[D]. 马春波.西南交通大学2005
- [10].几类快速公钥密码的设计与分析[D]. 王保仓.西安电子科技大学2006