经典密码学如何在量子计算机中生存

J去年，加拿大总理乌斯汀•特鲁多(ustin Trudeau)无疑将量子计算的知名度提高了几个档次，当时他在游戏中——如果是含糊地说的话¹-在新闻发布会上描述了它。但在过去的几年里，我们已经听说了很多关于量子计算机的事情，比如谷歌，ibm，美国国家航空航天局，还有很多很多大学，都在研究量子计算机，或者投入资金用于各种用途。例如，正如斯诺登的文件所披露的那样，nsa希望建造一台用于破解密码的计算机，人们似乎普遍认为，如果建造出一台全面、实用的量子计算机，它在这方面可能会非常有用。一个《纽约客》文章例如，今年早些时候，量子计算机“在其运行的第一天，将能够破解互联网上最广泛使用的代码。”但也许它们并不像我们所相信的那样有用。

一些人正在寻找“用量子对抗量子”的方法——但还有另一个(而且更便宜)的选择。

量子计算是基于量子物理的叠加原理。普通计算机中的位不是0就是1。量子物理学允许比特以同样的方式在0和1的叠加中薛定谔的猫可以是“活着”和“死去”的叠加。这有时会让量子计算机比普通计算机更快地探索可能性。对于一个一般性的搜索问题，比如试图通过尝试所有的搜索方法来找到一个密码的密钥，量子计算机被期望有二次加速。例如，美国政府批准的高级加密标准最多有2个²⁵⁶或者大概是1后面跟着77个零键。量子计算机可以做同样的搜索，就像只有两个一样¹²⁸键，大概是3后面跟着38个零。一方面，这快多了。另一方面，仍然有大量的搜索工作要做。

但是还有另一种密码学，叫做公开密钥密码学，它是在20世纪70年代发明的。顾名思义，这些系统是两个人通过交换公开信息就密钥或密钥的一部分达成一致意见的系统。这在现代电子商务中非常有用——例如，如果你想通过互联网安全地将你的信用卡号码发送到亚马逊(Amazon)，你肯定不想先开车去他们的总部开个秘密会议。公钥系统依赖于这样一个事实，即某些数学过程似乎是单向的——它们很容易做，但很难撤销。例如，取两个大的整数相乘就比较容易了。但对某些人来说，把结果分解成原始数字似乎要困难得多。这个特殊的单向函数用在RSA加密是最流行的公开密钥系统之一。

不幸的是，对于RSA来说，不是所有单向函数都是一样的。分解问题属于一类叫做"隐藏的子群问题群是一种特殊的数学结构，而隐藏的子群是它内部的另一种结构，破解程序是不知道的——在因式分解的例子中，乘积生成群，未知因子生成隐藏的子群。在隐子群问题上，预测量子计算机将得到指数加速。分解比搜索要快，所以一台普通的计算机可以分解大小为2的数¹⁵³⁶⁰在搜索的时间里²⁵⁶钥匙。但量子计算机可以把同样的数字考虑进去，更像是搜索2万个密钥所需的时间。这是一个巨大的加速。它几乎会摧毁RSA，这种情况与目前所有其他常用的公开密钥系统类似。

T这将是公开密钥密码学的一次大变革，但密码学家们不会就此放弃。一些人正在寻找“用量子对抗量子”的方法——但还有另一个(而且更便宜)的选择。人们也在研究所谓的后量子密码学，尽管更确切的名字可能是抗量子密码学。这些系统运行在普通计算机上，但基于不属于隐藏子组类别的问题。这些问题包括求解多变量多项式系统，求点到点的最短距离n其他点的维歪斜网格，并找到与其他位串集最近的位串。

例如，如果Alice想给Bob发送一条消息，她可以用Bob的一个点来识别它n-维度网格，然后添加一些“杂色”，将它移出网格一小部分。如果n非常大，而且网格中的角度是歪斜的——远远不是直角——对于窃听者伊芙来说，弄清楚爱丽丝的原始点似乎很困难，量子计算机似乎也帮不上什么忙。但如果Bob(而且只有Bob)通过相同的点绘制了一组不同的线，但角度接近90度，那么他就有了一个“陷阱门”，可以让他恢复这个点和信息。这个想法的变体被称为lattice-based密码学它们是后量子时代应用的一些领跑者。

后量子密码学的方法在过去没有被使用过，因为它们比当前的公开密钥方法效率低，但它们正在变得更好。2015年8月，nsa宣布计划推出一份获得批准的加密方法清单，以抵制量子计算机。2016年4月，美国国家标准与技术研究院(National Institute of Standards and Technology)紧随其后，启动了一项持续4至6年的公开审查程序。

为了确保加密方法的安全性，这并不是一段不合理的时间。例如，在2014年，政府通信总部的研究人员，或多或少相当于英国的国家安全局，开发了一种基于晶格的加密算法，最初似乎是抗量子的。然而，经过几年的研究，研究人员发现了如何使用代数数论领域的工具来识别隐藏的格子，从而揭示陷阱门。他们使用的问题毕竟属于隐藏子组范畴。

对于新的密码标准来说，4到6年的时间也不是不合理的。政府机构担心数据在未来几十年仍需保持安全，所以他们现在正在为10年或20年后的计算机做准备。

如果你担心量子罪犯从互联网上窃取你的信用卡号码，你可以稍微松一口气。当量子计算机到来的时候，密码学家们希望为它们做好准备。而且你不用自己买量子计算机也能安全地购物，尽管我相信亚马逊会很乐意卖给你一台。

约书亚·霍尔顿是罗斯-胡曼理工学院的数学教授，著有《秘密的数学:从凯撒密码到数字加密的密码学。

请注意

1.看到“给特鲁多的量子计算打分，”在Scott Aaronson的博客上，Shtetl-Optimized。

观察:理论计算机科学家斯科特·亚伦森(Scott Aaronson)与量子计算机公司D-Wave之间的矛盾。

这篇经典的事实如此浪漫的文章最初发表于2017年2月。