格密码理论初论
摘 要：格密码是一类最新备受关注的抗量子计算轨道大数据攻击的公开密钥密码体系。格密码理论的研究涉及到的密码数学问题很多, 学科具有明显的交叉特色, 研究方法趋于多元化。格理论的研究发源于开普勒的猜想，第一个基于格的密码体制是 1997 年提出来的。格密码的发展有三大阶段，量子计算技术加速了格密码体系的研究。
关键词：格密码 公钥 发展 签名 Ajtai
- 简介
格密码是一类最新备受关注的抗量子计算轨道大数据攻击的公开密钥密码体系(下文简称：公钥密码体制)。格密码理论的研究涉及到的密码数学问题很多, 学科具有明显的交叉特色, 研究方法趋于多元化。格密码的发展大体上可分为两条主线： 一是从悠久历史的格经典数学问题的研究开始发展到近30多年来高维格困难问题的求解算法和计算复杂性理论研究;二是从使用格困难问题的求解算法，分析非格公钥密码体制的安全性发展到基于格困难问题的密码体制的设计。
- 格理论的起源
格理论的研究发源于1611年开普勒所提出的如下猜想： 在一个容器中堆放半径相等的小球所能达到的最大密度是pi/。 1840年前后，高斯引进了格的概念并证明：在三维空间堆球,如果所有的球心构成一个格，那么堆积密度所能达到的最大值是pi/。在过去的一个半世纪中, Minkowski、Hermite、Bourgain、Hlawka、Kabatyansky、Levenstein、Lovasz、Mahler、Rogers等著名数学家系统地发展了一般几何体的格堆积与覆盖理论。在这一发展过程中，确定一个给定几何体的最大格堆积密度和最小格覆盖密度一直是这一学科的核心问题 。
- 格密码研究发展现状
第一个基于格的密码体制是 1997 年提出的Ajtai-Dwork密码体制。该体制的安全性基于Ajtai的 average-case 到 worst-case 的归约。之后，Goldreich, Goldwasser和Halevi提出了更加实用的 GGH 密码体制。设计者首先选择一组短的格基，生成格，然后将短的格基随机化生成另一组格基作为公开密钥 ,短的格基是秘密密钥。但是这种方法生成的格不是Ajtai提出的那类随机困难格。虽然后来Micciancio对GGH 的格基生成算法进行了改进，这个体制的安全性仍然没有被证明出来 。
格密码中格最短向量问题是数论中的经典问题，1850年Hermite 证明了对于任意一个n维格最短向量的长度小于，其中是Hermite常数。1905年Minkowski 证明了。1978年Kabatyanskii和Levenshtein将的上界改进到1.744n/2。这些结果给出了最短向量长度的一个上界，为密码学家在该问题的研究提供了重要的参考。
到了1999 年Ajtai提出了一种构造随机格和它的短格基的方法。这种生成方案相对来说有一个很重要的优势 , 这类随机格服从合适的分布而且是Ajtai于 1996 年所提出的那一类具有可证明安全性的随机格。具体地说，给出了一种构造随机格和随机格对应的垂直格的线性无关短向量组的方法。
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
