早在两千三百年前,古希腊哲学家亚里士多德提出一个论断:“用完全相同的正四面体可以无缝隙的堆满整个房间”.这一论断一直到1611年才被开普勒怀疑是错误的.1611年开普勒提出的猜想:“在一个容器中堆放等半径的小球所能达到的最大密度是时间推进到大约1840年,高斯引进了格的概念并证明: “在三维空间堆球,若所有的球心构成一个格,那么堆积密度所能达到的最大值是从此,格的研究正式拉开序幕.综合来看,格的研究分如下几个阶段:

第一阶段: (1840-1980)

在这一时期,Minkowski 、Hermite 、Bourgain 、Hlawka 、Kabatyansky 、Levenstein、Lovasz、Mahler、Rogers 等著名数学家围绕一般几何体的格堆积与覆盖理论问题系统地发展了格数学理论.可以说“确定一个给定几何体的最大格堆积密度和最小格覆盖密度”一直是这一时期的核心研究问题.

第二阶段: (1982-1996)

1982年,格的研究发生了一个大事件！著名的LLL算法被提出了[10].LLL算法通过计算一个上三角矩阵R的的QRZ分解: R = QˆRZ 其中Q为正交矩阵,Z为单模矩阵,能够将格的一组基约减为一组正交性较好,且基的尺寸较短的“好基”.一旦LLL算法凑效,格上著名的困难问题都将有效解决.而LLL 算法也不负众望,对低维数的格作用明显.从此,开启了格在密码学中的应用.从1982-1996,格在密码学的应用主要体现在密码分析中.以LLL算法为代表的格基规约算法对著名的背包密码、RSA等的攻击都取得效果.

注: 1994年,还有一件大事情必须一提,Shor,P.W.在1994年的FOCS（Proceedings of the 35th Annual Symposium on Foundations of Computer Science）证明了大整数的素分解和离散对数在量子攻击下都不再困难.这意味着一旦量子计算机诞生,基于数论假设的公钥密码学必将面临致命一击.因此提前未雨绸缪,关注密码系统的量子安全很容易在学术界达成共识.不过,上世纪90年代,正是公钥密码学进入快速发展的阶段,学术界并没有因为Shor勾勒的基于大整数素分解和离散对数公钥密码“悲剧”的“结局”而放弃现在.全球的密码学家一起合力在大整数素分解和离散对数问题的基础上搭建了“宏伟”的现代密码学的大厦,并快速的实现在工业界推广应用.(www.daowen.com)

第三阶段: (1996-2005)

1996年基于格设计密码方案首次出现.[11],[12],[8],[13](NTRU)等早期的格密码方案相继被提出.相对当前较成熟的格密码,早期格密码存在诸如不安全[14]、不能实现安全证明等不足.不过这并不能掩盖这一时期格密码发展的辉煌成果.这些成果的取得为后来格密码的快速发展奠定了坚实的理论基础[15],[16].

第四阶段:(2005-至今)

2005年第一个基于LWE问题的公钥加密算法被提出,从此格密码研究驶入快车道！特别是2008年以来,格上设计密码算法的工具和方法逐渐丰富和成熟.数字签名、身份基密码、标准模型安全性、选择密文安全、属性基密码、零知识证明、身份证明协议等等密码原语相继被提出[17–21],[22],[23] 基于格的密码体系日趋完善.格密码的研究也引起学术界和工业界广泛的重视.尤其2008年后,格密码研究声名鹊起,威名天下闻.为了推进格密码的研究,2010年在欧密会后专门举办了“格密码日”.格密码从公钥密码大家庭的一个“新秀”,一举成为炙手可热的“明星”.2016年,美国NIST（美国标准化技术研究院）已经公布了“后量子密码标准制定的路线图和时间表”,并计划在未来五年内完成算法征集及其相关分析工作.这其中格密码作为典型的后量子密码代表,成为候选后量子密码标准的主力军.