格密码：为什么是可以免受未来量子计算机进攻的加密方案？

1994年，闻名计算机科学家、麻省理工学院的利用数学系传授彼得·秀尔提出了在量子电脑利用上的“秀尔算法”，又称量子量因数合成算法，因其证明量子电脑能做出对数运算，并且速度远胜传统电脑，关于如今通行于银行及收集等处的RSA加密算法能够破解而构成威胁。

也就是说，假设有一天量子计算机被实正创造出来，它们将摧毁今天的许多用于庇护在线共享信息的根底设备。那种可怕的可能性使科学家们力争上游地造造新的"后量子"加密计划，以尽量制止信息落进量子黑客的手中。

假设今天的密码协议失败，就不成能庇护在线毗连发送奥秘信息、停止平安的金融交易或验证数据。任何人都能够拜候任何工具；任何人都能够假装成任何人。数字经济将瓦解。

当或者假设功用齐全的量子计算机可用时，那恰是可能发作的工作。美国国度原则与手艺研究院 (NIST) 于 2017 年倡议了一项国际竞赛，以觅觅实现“后量子”密码学的更佳办法。上个月，评选出了第一批获胜者：四个参赛进围计划，此中有三个利用"格密码"，那是一种受格启发的计划，即空间中点的规则摆列。

基于格密码是涉及格的密码原语构造的通用术语，无论是在构造自己仍是在平安证明中。基于格的构造目前是后量子密码学的重要候选者。与更普遍利用和已知的公钥计划差别，例如RSA、Diffie-Hellman或椭圆曲线密码系统，理论上能够在量子计算机上利用Shor 算法击败，一些基于格的构造似乎能够对抗典范计算机和量子计算机的进攻。此外，在某些颠末足够研究的计算格问题无法有效处理的假设下，许多基于格的构造被认为是平安的。

展开全文

格密码和其他后量子可能性在关键方面与当前原则差别。但它们都依靠于数学上的不合错误称性。目前许多密码系统的平安性是基于乘法和因式合成。任何计算机都能够快速地将两个数字相乘，但要将一个密码上的大数字合成成其素数，可能需要几个世纪。那种不合错误称性使得奥秘随便编码，但难以解码。

肖尔在他1994年的算法中所显示的是，因式合成的一个奇异是使其随便遭到量子计算机的进攻。"科罗拉多大学博尔德分校的数学家凯瑟琳-斯坦格说："那是量子计算机能做的一件十分详细、特殊的工作。因而，在肖尔之后，密码学家们有了新的工做。找到一套别致的数学运算，那些运算很随便做，但几乎不成能被撤销。

格密码是迄今为行最胜利的测验考试之一。它最后是在1990年代开发的，依靠的是对点的总和停止反向工程的难度。

格密码的数学布景：

格密码的工做原理：

有人可能会问，格密码详细是若何实现量子平安的，能够免受将来量子计算机进攻？下面我们通过简单例子来阐明它的工做原理。

下面是描述格密码的一种办法。想象一下，你的伴侣有一个格，那只是一堆在平面上有法例、反复的点。你的伴侣想让你说出那些点中的10个。但他很为难，他不会画出整个格。相反，他只列出了两个点，第一个点的X值为101，Y值为19，另一个点的坐标为[235, 44]。

幸运的是，在格上找到新的点很随便，因为当你在格上加减任何两个点时，你会在统一个格上得到第三个点。所以你要做的就是把你伴侣给你的点加起来，或者把它们乘以整数，然后再加起来，或者那两者的组合。如许做了八种差别的办法，你就能答复你伴侣的问题了。

但是你的伴侣仍然不称心。他给了你同样的两个起点，然后问你能否能在统一格上找到靠近[0，0]的点。 为了准确答复那个问题，你必需找到[101，19]和[235，44]的组合，使你接近[0，0]。那个问题比第一个问题要罕见多，你最末可能只是揣测和查抄来得到谜底。那种不合错误称性是格密码的根底。

假设你实的想用格密码来分享信息，你能够施行以下操做。想象一下，一个伴侣（一个比力好的伴侣！）想给你发送一条平安信息。你从一个正方形的数字网格起头。假设它有两行和两列，看起来像如许：

如今你想出了一个只要你本身晓得的"私钥"。在那个例子中，我们假设你的私钥只是两个奥秘数字：3和-2。你将第一列中的数字乘以3，第二列中的数字乘以-2。 将每一行中的成果相加，得到第三列中的两个条目。

把新的一列贴在你的网格的末端。那个新的三列网格就是你的公钥，可自在地分享它。

(现实情状会略微复杂一些。为了避免黑客破译你的私钥，你必需在最初一列加进一点随机噪音。但在那里，为了简单起见，我们将漠视那个步调）。

如今你的伴侣将利用公钥向你发送一条信息。她想到了她本身的两个奥秘数字：2和0。她把第一行的数字乘以2，第二行的数字乘以0，然后把每一列的成果加起来，得到第三行。

如今她把新的一行附在网格的底部，并把它送回给你。(同样，在一个实在的系统中，她需要在她的行中加进一些噪音）。

如今你将阅读那个信息。要做到那一点，你要查抄一下你伴侣的最初一行能否准确。将你本身的私钥利用于她那一行的前两个条目。成果应该与最初一个条目相符。

你的伴侣还能够抉择在最初一列中向你发送带有错误数字的行。她晓得那个数字与你的计算不符。

假设你的伴侣发送的最初一行数字是准确的，你会把它阐明为0；假设她发送的数字是错误的，你会把它阐明为1。该行编码一个位：0 或 1。

请重视，外部进攻者无法获得你和你伴侣的私钥。没有那些，进攻者将不晓得最初的数字能否准确。

在理论中，你期看发送的信息长于1比特。因而，想要领受100位信息的人将产生100个新列，而不是只要一个。然后，信息的发送者将创建一个新的行，修改最初100个条目，为每个条目编码一个0或1。

假设现实地实现格密码，会有无数的细微区别没有被涵盖在那个计划中。例如，假设你想让信息实正不被窥视，矩阵需要有一个不可思议的条目数，使整个工作变得如斯不随便而不值得利用。为领会决那个问题，研究人员利用具有有用的对称性的矩阵，能够削减参数的数量。除此之外，还有一整套的调整，能够利用于问题自己，以及纳进误差的体例，等等。

当然，老是有可能有人会在格密码中找到一个致命的缺陷，就像肖尔对因式合成所做的那样。我们无法包管一个特定的加密计划在面临任何可能的进攻时都能发扬感化。密码在被破解之前老是有效的。

事实上，在本年7月30日，一个有前途的后量子密码计划不是用量子计算机，而是用一台通俗的条记本电脑被破解的。许多人认为该协议是匹敌量子计算才能的一种有期看的防备办法。两名研究人员在一小时内用条记本电脑破解了该加密协议。从那以后，其别人使进攻速度更快，在几分钟内就予以破解。

数学家和计算机科学家Steven Galbraith评判说，“如斯戏剧性和强大的进攻......令人震动，”进攻背后的数学不只令人骇怪，并且还削减了后量子密码学的（急需的）多样性。成果让后量子密码学界既震动又鼓励。

来自：量子认知