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

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评价说，“如此戏剧性和强大的攻击......令人震惊，”攻击背后的数学不仅令人惊讶，而且还减少了后量子密码学的（急需的）多样性。结果让后量子密码学界既震惊又鼓舞。

来自：量子认知

责任编辑：

关键词：