目前量子计算算法的Grover算法和Shor算法已经可以破译当今广泛使用的密码。Shor算法是一种量子计算机求解离散对数问题的算法，它能够攻破RSA、DSA和ECDSA密码，Grover算法没有Shor算法有效，它的作用相当于把密码的秘钥长度减少一半，密码技术人员可以通过加长秘钥长度来抵抗Grpver算法攻击。
    值得注意的是，国外的量子计算机发展迅速，已有像谷歌这样的著名公司将量子计算机投入使用，用于提高信息搜索效率和研究量子人工智能。如今的量子计算机还不足以通过执行Shor算法或Grover算法来大肆攻击现有密码，尽管如此，随着科技发展，总有一天信息安全将受到威胁。因此，在威胁到来之前，科学家应尽快研究出能够有效抵制量子计算机和电子计算机的新型密码体制。除了RSA、DSA和ECDSA密码之外还有许多重要密码是能够抵抗量子计算机攻击的。如基于Hash函数的密码、基于纠错码的密码、基于格的密码、多变量二次方程组密码和秘密钥密码。这些密码被认为是能够抵抗两种计算机攻击的，目前还没有人能够给出一种用Shor算法攻击这些密码体制的有效方法。[1]本文将对这几种抗量子计算密码进行介绍，并对其优劣进行分析。
基于Hash函数的密码
Hash算法有MD4，MD5，SHA-1和SHA-2，RIPEMD，以及HAS。HAS函数从未真正被使用过，而MD4的安全性严重缺乏抵抗力。[3]MD5最初为代替MD4而设计，但却不是碰撞稳固的。[3][4]至于RIPEMD，它是在开放的学术社区被设计出，因而容易被攻击者攻破，[4][3]并且从报告中看出它不常被使用。[3]SHA-1和SHA-2在几乎每个密码系统及安全协议中，都被用在认证和数字签名服务上。[6]尽管SHA-1被查出有一些安全缺陷，[3]但这些都被认为是非关键缺陷，并且没有成功延伸到SHA-2中。[6]2004年中国密码专家王小云教授研究小组宣布已破解MD5、SHA-1等加密算法，随着密码学研究的不断深入和计算机技术的快速发展，美国政府计划从2010年起不再使用SHA-1，全面推广使用SHA-256、SHA-384和SHA-512等加密算法。SHA256、SHA-384和SHA-512算法是SHA-1的变体，也被称作SHA-2。
SHA-2算法安全性
基于Hash函数的公钥签名方案需要一个标准的密码学Hash函数，它产生位的输出。对于，一个可选的Hash函数是SHA-256。[1]目前已有的对Hash函数攻击的方法包括生日攻击、彩虹表攻击、差分攻击等，下面介绍SHA-256在生日攻击和差分攻击下的安全性。
用于消息唯一性和数据完整性验证的Hash函数，其安全性全依赖于函数本身的属性和对碰撞的抵抗。Hash函数的算法结构特点和Hash值的长度是决定函数抗碰撞性的主要因素，Hash值越长，越能抵抗生日攻击。SHA-256有256比特Hash值，MD5和SHA-1分别有128和160比特的Hash值。因此，SHA-256比MD5和SHA-1能抵抗生日攻击。通过对Chabaud-Joux攻击SHA-256的分析，找到了SHA-256的一个部分碰撞，其复杂度为，但无法找到SHA-256的一个整体碰撞，因此，SHA-256也能抵御现有的差分攻击。
Merkle数字签名方案
基于Hash的数字签名源于一次签名体制，经典的一次签名体制称为Lamport-Diffie一次签名体制，之后又出现更多改进方案，Bos-Chaum方案、Winternitz方案等。然而一次签名方案具有“一次一密”的特点，即每个密钥对只能签署一条消息，否则签名将以很高的概率暴露更多的私钥信息，因此很容易伪造针对新消息的签名。[3] 虽然一次签名具有较高的安全性，但缺乏实用性。更先进的基于Hash函数签名体制是Merkle Hash树签名体制，其树的层数与要签名的消息数有对数关系。[1]Merkle数字签名方案的优点是签名和验证签名效率较高；缺点是签名和密钥较长，产生密钥的代价较大。随着研究的发展，出现了一些修改方案，如CMSS方案、GMSS方案、DMSS方案等。Buchmann，Dahmen等提出了XOR树算法，只需要采用抗原像攻击和抗第二原象攻击的Hash函数，便能构造出安全的签名方案。而在以往的Merkle树签名方案中，要求Hash函数必须是抗强碰撞的。这是对原始Merkle签名方案的有益改进。上述这些成果，在理论上己基本成熟，在技术上已基本满足工程应用的要求，一些成果已经应用到了Microsoft OutLook以及移动代理路由协议中。[8]
目前，基于Hash函数的数字签名的理论和技术都还需要深入研究，仍有许多开放性课题。如增加签名的次数、减小签名和密钥的尺寸、优化认证树的遍历方案以及实现相比其他公钥体制所不具备的功能（如基于身份的认证）等均值得进一步研究探讨。[8]

格理论起源于1611年天文学家开普勒（J.Kepler）的断言：球堆积的最大密度是。即在一个立方体中放满小球，小球总体积与立方体体积之比不会大于。1840年左右，高斯引入格的概念，并用正定二次型的方法证明了：球的格堆积的最大密度是。后来，数学家们又发展了格理论。
格的基本概念
1．格是维空间中有着周期性结构的点集，即给定个线性无关的向量，格是由它们生成的一个向量集：

向量被认为是格的一组基。[1] 格的基中的向量个数称为格的维度。
2．设是一个维度为的格，且是的基。对应于这个基的基础区域是如下的向量的集合：

格难题
首先给出三个最知名的格难题。
最短向量问题（SVP）：在格中寻找一个最短的非零向量，即寻找一个非零向量，使它的欧几里得范数最小。
最近向量问题（CVP）：给定一个不在格中的向量，寻找一个向量，使它最接近，即寻找一个向量，使欧几里得范数最小。
最短独立向量问题（SIVP）：在格中寻找个线性独立向量，且使得值达到最小
最短基问题（SBP）：给定格，寻找长度最短的基。然而在SBP问题中，不同情况下对“长度”的定义有所不同，因而要视具体情况而定。
另外还有一些SVP问题与CVP问题的变形的形式，在理论和实践中都有重要应用。如、近似最短向量问题（apprSVP）以及近似最近向量问题（apprCVP）。
格密码的优势   
格理论的研究使得抗量子密码的使用成为可能。它享有最差条件下的强安全性证明，相对高效的实现，以及非常简明。[1] 以下，我将对已有对格理论在密码学中的研究进行总结。
     格密码是在格的计算性难题的基础之上构造的。与格相关的基本计算难题有：在格中寻找最短的非零向量和在格中寻找与指定非格向量最为接近的向量。[9] 分别名为：最短向量问题（SVP）和最近向量问题（CVP）。
1.到目前为止，学术界还没有找到求解最短向量问题（SVP）、最近向量问题（CVP）及其变体的多项式时间的经典算法，更没有比经典算法求解更有效的量子算法，Shor算法与Grover算法在格难题面前均束手无策。因此我们有理由相信格密码是抗量子计算的。
2.最短向量问题（SVP）、最近向量问题（CVP）在最差条件下被学者证明是强安全的，为格密码的安全性提供保障。
3.格本身是线性空间上的离散加法子群，其良好的代数性质使其很容易在计算机中实现，与现有公钥体制相比效率更高。
综上几点格密码的优势，格理论在国外迅速发展，但在国内研究寥寥。
格密码的密码分析
最短向量问题（SVP）和最近向量问题（CVP）都是十分复杂难解的数学难题。在低维度下，可以使用格基约减算法，比如二维格中的高斯格基约减算法，或最为人们熟知的的LLL算法来求解SVP问题与CVP问题。二维格中的高斯格基约减算法的作用是找到格中正交性质最优的基，从而求解二维格中最短非零向量。LLL算法是在1982年，被Lenstra和Lovasz等人提出[3]。LLL算法不一定能够找到格中最短向量，但在多项式时间内它能够求解不超过最短非零向量的倍的向量。但随着格维度的增加，LLL算法的求解作用也将越来越弱。LLL算法在密码分析中有着非常重要的应用，此前被LLL算法攻破的实例有：1982年4月，Shamir 就用LLL算法攻破了Merkle- Hellma 基于背包问题的公钥体制[4]。

参考文献
[1]（美）伯恩斯坦（Bernstein,D. J.），（德）布赫曼 （Buchmann,J. ），（德）达门（Dahmen,E.）， 张焕国，王后珍，杨昌等译，抗量子计算密码[M]，北京：清华大学出版社，2015
[2] Y. Sasaki, L. Wang, K. Ohta and N. Kunihiro, New message difference for md4, Fast Software Encryption[J], ed. A. Biryukov, Vol. 4593 of Lecture Notes in Computer Science(Springer Berlin, Heidelberg, 2007), pp. 329-348.
[3] Y. Sasaki, L. Wang, N. Kunihiro and K. Ohta, New message differences for collision attacks on md4 and md5[J], IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E91-A(2008) 55-63.
[4]W. Xiaoyun, F. Dengguo, L. Xuejia and Y. Hongbo, \Collisions for hash functions md4,md5, haval-128 and ripemd."[J]
[5]X. Wang and H. Yu, How to break md5 and other hash functions[J], Advances in Cryptology EUROCRYPT 2005, ed. R. Cramer, Vol. 3494 of Lecture Notes in Computer Science(Springer Berlin/Heidelberg, 2005), pp. 561-561.
[6] J. Joshi, Network Security: Know It All [J](Morgan Kaufmann Publishers (imprint of Elsevier), Burlington, USA, 2008).

[7] X. Wang, Y. Yin and H. Yu, Finding collisions in the full sha-1[J], Advances in Cryptology CRYPTO 2005, ed. V. Shoup, Vol. 3621 of Lecture Notes in Computer Science (SpringerBerlin/Heidelberg, 2005), pp. 17-36.
[8]张焕国 王后珍，抗量子计算密码体制研究[J]，1671-1122（2011）06-0056-04
[9]周福才，徐剑 著，格理论与密码学[M]，北京：科学出版社，2013

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！