后量子密码项目的下一步是什么？NIST官员最新解读

光子盒研究院出品

上周二，美国国家标准与技术研究院(NIST)宣布了其首批后量子标准算法，新的加密算法将成为防范量子计算机攻击的标准。这四种算法分别是用于通用加密的CRYSTALS-Kyber和三种用于数字加密的方案：CRYSTALS-Dilithium、FALCON和SPHINCS+。

7月9日，NIST后量子密码标准化项目的负责人Dustin Moody博士在第二届雁栖湖国际抗量子密码标准化与应用论坛暨第六届亚洲抗量子密码论坛上，详细分析了第三轮的入选算法，以及NIST的筛选依据。

上周，Moody也接受了IEEE Spectrum杂志的采访[1]，以下为全文翻译：

问：什么是后量子密码，为什么NIST需要一个标准化过程？

Dustin Moody：来自不同背景的研究人员一直致力于构建所谓的量子计算机。如果构建了足够大的量子计算机，那么就可以在这台量子计算机上运行一种算法，该算法将破解我们今天在世界各地实施和使用的几种最广泛使用的密码系统。因此，后量子密码正在准备新的密码系统，以取代那些容易受到足够大的量子计算机攻击的密码系统。而NIST之所以这样做，是因为我们已经标准化的一些密码系统，例如，处理公钥密码的密码系统，它会很容易受到攻击。因此，我们希望用不易受到量子计算机攻击的新标准取代这些标准。

即使（高性能）量子计算机还不存在，你实际上也可能会面临量子计算机的风险。这通常被称为“现在窃取，以后解密”。

问：据我了解，现在你要替换两个不同的东西；既有密钥又有签名。你能谈谈这两者，以及两者之间的区别吗？

Moody：使用密码技术，你需要许多不同类型的工具，来保护你的信息。人们首先想到的是加密和加扰你的数据，因此你的敌人无法读取它。这通常是使用公钥加密启用的。然后，你创建一个共享密钥，你将实际使用该密钥作为另一种加密系统的密钥，这种加密系统可以更快地进行加密，一种称为AES的分组密码。但是这种公钥加密用于创建初始密钥。所以这是我们需要替换的第一个功能。二是数字签名。无需在信函底部签名以证明你是作者，你可以使用加密技术以数字方式执行相同的操作。众所周知，这也容易受到量子计算机的攻击。所以这是我们试图替换的第二个功能。

问：目前最大的量子计算机大约有200多个量子比特，而且它们不是容错的。其中一台机器使用Shor算法计算出的最大数字是21。对于破解RSA 2048所需的时间，外界有各种估计，但你至少需要数千个量子比特，而且它们都需要非常、非常高的质量。为什么这么着急？为什么我们现在要做这个？你在2016年开始了这个过程。这可能提前了几年，甚至几十年。

Moody：首先，将密码系统标准化，然后将其应用到世界各地的产品中，这需要漫长的时间。根据我们过去的经验，从一种加密算法切换到另一种可能需要10到20年。由于我们需要在量子计算机问世之前完成这项工作，因此我们必须提前完成所有工作。并且不能急于求成。假如密码系统是在两周前发明的，你就不会对它有信心。我们需要经验丰富的人来分析这些算法，才能对它们的安全性有信心。这就是原因之一：其准备工作需要时间。然后原因之二是你实际上可能会受到量子计算机的威胁，即使量子计算机还不存在。这通常被称为“现在窃取，以后解密”。这是你的敌人可以复制你的数据的想法，这些数据是加密的，他们现在就可以掌握它，即使他们现在读不懂。但也许10年后会出现一台量子计算机，然后他们就可以访问你的数据。如果你要保护的信息足够有价值，那么你已经因为这种威胁而陷入困境。这也是我们需要在量子计算机建成之前就提前做好准备的另一个原因。

问：现在窃取，以后解密有多现实？我知道有这种可能性，但这真的发生了吗？人们是否正在下载数据并将其存储起来，以便当他们的量子计算机启动并运行时，他们可以查阅这些数据？

Moody：我没有机会接触机密材料。NIST不在像美国国家安全局（NSA）和其他部门的那个级别上。但与我交谈过的人说过，这绝对是一种威胁，而且现在正在国家层面上发生。

我们将把一些东西进行标准化，以便我们有各种各样不同的数学问题来作为我们安全的基础。

问：公钥加密的漏洞是因为量子计算机最终能够以几乎指数级的速度分解大素数。正在使用哪些类型的策略来创建这些新的公钥？你能介绍一下其中的几个吗？

Moody：在加密领域，我们喜欢使用已经存在了一段时间的想法。自从Peter Shor的算法在90年代被发现，研究人员就一直在研究这个问题。许多解决方案都来自三大家族。最流行的一种涉及所谓的格（lattice），这是一个数学结构，你采用基向量，你对它们进行积分线性组合，你可以用密码学做一些非常有趣的事情。没有已知的量子算法比对基于格的密码系统的经典攻击做得更好。就密钥大小和效率而言，基于格的密码系统似乎是最有力的竞争者。因此，我们收到大量基于格的提交方案也就不足为奇了。第二个家族基于所谓的纠错码或基于代码的密码学。这些代码已经在信息安全中使用了很长时间，因为数据是在嘈杂的频道上发送的。如果你使用纠错码，你可以解释错误并恢复原本要发送的消息。我们使用类似于在这些代码中使用的点阵的想法。在那里，就密钥大小和效率而言，它们似乎只落后于格方案半步，但它们也相当不错。所以我们看到了一些基于代码的提交。第三大家族包括一些基于所谓的签名方案多变量密码。你将使用大量变量，x1到xn，并创建一个二次方程组。而定义和评估其中一个系统非常容易，但要解决却非常困难。所以事实证明，它适用于数字签名方案。

问：有点像你在图表上有一条大波浪线？画起来很容易，但实际上很难弄清楚是用什么函数来绘制它的。

Moody：是的，这就是很多密码系统的想法。有一件事是单向的，如果你知道这个秘密，你就可以快速轻松地做到这一点。这允许你解密或签名。攻击者不知道这个秘密，他们就不能做任何事情。

问：我大致了解你如何测试经典加密系统，因为我们有经典计算机。但是我们没有量子计算机。那么如何验证这些方法实际上是量子安全的呢？

Moody：不能保证真的没有人会出现并提出一些新想法。我们今天在经典计算机中使用的密码系统也是如此。

问：当然，我知道RSA并不难证明。

Moody：当你将量子计算机添加到组合中时，你可以使用更多的工具，你可以使用更多的量子算法。我们能说的最好的就是很多聪明人花时间看这些，没有人发现任何攻击，而且他们似乎没有接近。这些途径似乎根本没有用。这就是我们设置竞争的方式——确保我们拥有该领域的专家，花费数年时间研究这些密码系统，并确保没有攻击。

问：所以在这个过程中，你确实已经从最初的选择中缩小到几个决赛选手。（编者注：7月5日公告之前）

Moody：是的，我们开始时有82个，而现在我们在第三轮结束时有七个决赛算法和八个候补算法，这将在很短的时间内结束，可能是一两周，或者我们会有标准化的。

问：下一步是什么？

Moody：我们将开始编写标准。这些将是最广泛使用的算法。我们还将列举一些算法，继续进行第四轮评估，以便我们拥有一些其他算法。因为这是一个新的研究领域，我们不想把所有的鸡蛋都放在一个篮子里，例如只有格算法，然后攻击来了，我们就没有别的了。我们将对许多事物进行标准化，以便我们有多种不同的数学问题来作为我们安全性的基础。我们将开始编写标准，这将需要一两年的时间，并且会有一些继续进行评估，可能会在第四轮结束时被选中进行标准化。

问：决赛入围算法和标准化算法有什么区别？

Moody：一旦我们将这些算法标准化，人们就知道这些算法将会被广泛使用。已经有了实现，但人们将能够专注于标准化的实现。这是采用道路上的重要一步。行业需要标准才能真正得到广泛采用。

问：据我了解，存在一些与算法相关的专利纠纷。

Moody：在加密领域，大多数人不喜欢专利，因为它们往往会阻碍采用。公司不喜欢采用可能获得专利的算法。在我们的流程开始时，所有提交者都必须让我们知道他们拥有的任何专利。我们知道有些专利不是来自提交者，而来自一些第三方。NIST一直在与这些其他各方进行谈判，以协商一个对双方都有利的解决方案。我想你会在我们的公告中看到我们对结果感到满意。我们认为这些算法将能够被世界各地的人们广泛采用。

参考链接：

[1]https://spectrum.ieee.org/post-quantum-cryptography-nist

相关阅读：

每周一到周五，我们都将与光子盒的新老朋友相聚在微信视频号，不见不散！

你可能会错过：