格基规约算法研究

论文摘要

把密码方案的安全基础建立在已知的数学难题上是密码设计常用的一种方法。一个好的密码方案除了要求是安全的,还应该是高效的。格是一种典型的线性代数结构,并且格上一些问题的困难性已经得到证明。如果利用格上难题设计新型密码方案,那么不仅可以期望方案的安全性能够得到证明,而且还可以期望格的线性结构能够使方案具有较高的运算速度。因此,在格上构造密码方案得到许多学者的关注。格基规约是格理论研究的一个重要内容,也是密码设计和分析中的一个重要工具。在理论研究中,许多格上问题都可以通过规约来求解(或者近似求解)。在密码学应用中,对一些密码方案的分析最终都可以等价成一个格基规约问题。因此研究新型格基规约算法不仅具有理论价值,同时也具有重要的实用价值。本文提出了基于经典Schnorr算法的一种新的改进算法SDR,并对其性能进行了系统的分析

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 密码学的概述及研究动向
• 1.2 论文的主要工作与内容安排
• 第二章 格
• 2.1 格的基础知识
• 2.2 格中困难问题
• 2.3 格理论在密码设计的应用
• 2.3.1 Ajtai-Dwork （AD）公钥密码方案
• 2.3.2 Goldreich-Goldwasser-Halevi （GGH）公钥密码方案
• 2.3.3 NTRU公钥密码方案
• 2.3.4 其它密码应用设计
• 第三章 格基规约
• 3.1 格基正交性与基向量长度的内在联系
• 3.2 格基正交化与准正交化规约
• 3.3 格基规约（lattice reduction）基本知识
• 3.4 格基规约在密码分析中的研究进展
• 3.4.1 对基于背包的密码方案的分析
• 3.4.2 对截短的线性同余随机序列生成器的分析
• 3.4.3 对RSA加密方案的分析
• 第四章 格基规约算法分析
• 4.1 格基规约算法研究概述
• 4.2 LLL归约
• 4.2.1 基本定义
• 4.2.2 LLL规约基的基本性质
• 4.2.3 标准LLL规约算法
• 4.3 Schnorr算法和LLL算法比较
• 4.3.1 Schnorr算法分析
• 第五章 我们的工作：新的基于Schnorr的格基规约算法SDR
• 5.1 对偶格（Dual Lattice）与正交格（Orthogonal lattice）
• 5.2 SDR算法流程
• 5.3 SDR算法分析
• 5.4 SDR算法的进一步讨论
• 附录A
• 结束语
• 致谢
• 参考文献
• 研究成果