摘要
本文是由Ritik Bavdekar等人于2022年2月发表的有关后量子密码学研究的文章。文章围绕后量子密码学的技术及其对经典密码学的挑战，以及NIST后量子密码学标准化进程展开分析，最终提出了后量子密码学领域的未来研究方向。
关键词：后量子密码学；量子计算机；Shor算法；NIST后量子密码学标准化进程
一、问题的提出
量子计算机的出现将彻底改变我们目前使用的经典计算机的功能，其将能够执行当今高性能多核系统无法执行的某些计算。量子计算机的想法很大程度上基于量子物理学，其以量子比特的形式接受输入并产生输出。量子计算机可以用来解决经典计算机在限定时间内无法解决的问题，其应用数不胜数，包括导航系统、地震学、物理学研究、制药等。
但量子计算机的出现也是一把双刃剑。一方面，量子计算机能以惊人的速度执行计算；另一方面，量子计算机在某些场景下可能会带来潜在的安全威胁，其中一种场景便是密码分析。
密码分析是对不同技术的研究，这些技术可用于理解加密数据的含义，而无需访问发送方和接收方用来加密和解密数据的秘密信息。密码分析是破译密码的艺术，但不幸的是，我们当今的密码算法所依赖的数学难题将在量子计算机上得到解决，这将使破解数字通信中广泛使用的密码算法变得容易。
后量子密码学是对量子计算机和经典计算机都无法破解的新密码系统的研究。根据建立安全性的基本问题，密码系统分为几个系列，主要包括基于格的密码学、基于同源的密码学、非交换密码学、基于编码的密码学、基于哈希的数字签名和多变量密码学。
本文讨论了量子计算机对当前使用的各种密码算法的影响，并提出了后量子密码学领域的未来研究方向。
二、经典密码学的安全性与后量子密码学
量子计算机基于量子叠加、量子纠缠和量子不确定性等概念。量子叠加使一个粒子可以同时出现在多个地方。量子纠缠描述了粒子之间的相关性，这在经典世界中是不可能的。量子不确定性指出，如果我们观察到一个粒子的一个性质，则其他性质的信息就会丢失。
量子计算机的出现对经典密码学算法的安全性提出了质疑。对称密码学的安全性被量子计算机降低了一半。同时，随着量子计算资源的发展，非对称密码学将变得过时。
后量子密码学是不受量子计算机攻击影响的密码学领域，其中开发的加密算法是安全的。众所周知，所有当前的非对称算法（RSA、ECC、DH、DSA）都可以被量子计算机破解，因为其基于整数因子分解问题或离散对数问题，这些问题很容易在量子计算机上使用Shor算法解决。相较而言，对称算法和哈希函数在后量子世界中相对安全。Grover算法可以通过增加平方根复杂度来提高攻击速度，但大多数算法可以通过增加密钥长度来再次确保安全。
三、后量子密码系统的性能比较
表1显示了研究中涵盖的后量子密码提供的安全级别。算法的性能通常是通过完成所需的时钟周期数以及在硬件平台上实现该算法所需的电路/面积来衡量。它还取决于密钥长度或算法中使用的任何其他类似度量。为此，许多算法都有不同的版本，这些版本具有影响性能的不同参数。
表1 PQC算法家族及其对应的安全级别
例如，kyber512、kyber768和kyber1024在本质上是相同的算法，但其使用不同的密钥长度和其他影响密码性能和安全性的指标。为了公平地比较具有相同安全级别的性能算法，必须对上述指标进行比较。
在Kanad Basu等所做的分析中，作者发现在使用关键封装技术的算法中，NTRU-HRSS具有最高的延迟（以时钟周期为单位）。在1级签名算法中，CRYSTALS-Dilithium具有最低的延迟。对于解封装技术，NTRU-HRSS（第3级）和Classic McWliece（第5级）具有更高的延迟，而CRYSTALS-Dilithium具有最短的延迟。
从这些结果中，我们可以得出结论，当使用基本算法而不进行任何修改时，CRYSTALS-Dilithium是物联网封装和解封装的良好候选者。然而对于解封装，唯一可行的选择是服务器的1级算法，因为所有测试的5级算法都不具有低延迟。由于IoT实施通常是在FPGA上进行硬件实施测试，因此可以作为算法如何在IoT设备上执行的良好基准。循环展开和循环流水线等技术可以减少整体延迟。
Brian Hession等使用tended eXternal Benchmarking eXtension(XXBX)在32位ARM微控制器(EK-TM4C123GXL)上测试PQC算法的性能。这些算法根据RAM、ROM、速度/延迟（时钟周期）和使用的能量进行了基准测试。
在RAM使用方面，NTRU是迄今为止最昂贵的，而Kyber的使用最少（在所有3个安全级别中）。就ROM使用而言，NTRU仍然是最昂贵的，但是第二昂贵的算法是Saber，尽管它使用的ROM空间只有NTRU的一半。说到速度（时钟周期），SIKE是最慢的，差距很大，一次封装耗时7分钟。Kyber、Saber和NTRU的耗时相当接近，安全级别更高所需的时间更长。在消耗的时间中看到的相同模式存在于消耗的能量中，这仅仅是因为算法运行的时间越长，所需的电力越多，因此耗能就越多。
四、向后量子密码学迁移面临的挑战
向PQC迁移的必要性是一个非常热门的话题，但是，从经典密码学向PQC迁移的问题到目前为止一直被忽视。由于向PQC迁移是不可避免的，因此研究如何迁移非常重要。然而，由于互联网的广泛应用和几乎每个行业的数字化，这种迁移将比其看起来更具挑战性。以下列出了向PQC迁移的一些挑战。
第一，量子计算的发展进度不可预见：第一个风险源于量子计算发展的进度不可预见，其发展速度超出预期。
第二，向PQC迁移的复杂标准：从当今的公钥密码学到后量子密码学的迁移并不像升级到更新版本的软件那么简单。NIST也承认了这一事实。
第三，“追溯解密”型攻击：在这一类加密攻击中，由于当今大多数私人信息都是以加密形式共享的，如果信息仍然相关，则其会在几年后被量子计算机捕获和利用。
第四，NIST标准相关性的选择：在NIST的PQC标准化期间评估向PQC迁移的影响至关重要。
要更好地理解向PQC迁移的问题并解决集成、安全、性能和其他问题，以确保在全球工业生态系统中安全部署量子解决方案，仍有许多工作要做。在讨论研究问题时应关注两个重叠的领域：
一是向PQC迁移的研究：研究候选算法如何在特定情况下使用以及关于任何特定密码使用域的安全迁移。
二是迈向密码敏捷性的科学：组织采用密码敏捷性作为数据加密技术，以确保对密码攻击做出快速响应。加密敏捷性的目标是快速适应新的加密标准，而无需对基础设施进行大规模更改。
向PQC迁移的大空间与密码领域的敏捷性有很多相似之处。二者之间的相关相似性表明要解决的困难范围，以允许将密码域向PQC算法迁移。
（一）向PQC迁移之前面临的挑战
如前所述，从当今的公钥密码学向后量子密码学的迁移，并不像升级到NIST认可的更新版本的软件那么简单。PQC解决了密钥、密文和签名大小以及交互和计算的需求。但NIST表示只会选择一种算法作为替代技术，因为其他算法在密钥大小和计算要求方面具有明显不同的权衡。总体而言，NIST认为在新的PQC标准下提供多种选项是安全的。文章讨论了几个可以从研究中获益的领域：
1.性能考虑：众所周知，PQC算法具有更高的计算、存储、内存和通信要求，因此在各种部署场景中的性能考虑至关重要。
2.安全考虑：由于公钥密码算法的变化，将会产生很多安全问题。与现有的RSA和ECC算法相比，由于PQC不太为人所知，因此可能会引发对密钥大小、计算时间等方面的担忧。另一个需要解决的领域是PQC算法的密码分析。
3.实现的注意事项：PQC算法的实现会比看起来更加复杂。数学算法的复杂性，例如将其转化为特定于平台的体系结构和设备的复杂性。
以下是一些用于引入新算法的方法：
第一，通常探索实现迁移的策略是采用混合策略，其中使用两种加密算法，一种算法采用我们目前的标准集，另一种算法采用最近一组PQC集。这为抵御“追溯解密”型攻击提供了一种安全机制，对于迁移的早期阶段可能是至关重要的。这种方法的优点在于其允许组织在向更新的候选标准过渡的同时保持认证。当然，不可否认的是，其缺点在于计算、内存、互联性和其他需求的大幅提高。
第二，另一种选择是使用cypher套件协商，其用于IETF协议，例如TLS[68]。在协议的初始交互阶段，交互方提供支持的密码套件列表，以选择双方都支持的最稳健的选择。组织可以协商密码套件版本号，以及有关密钥大小和参数设置的更多信息。使用这一框架可以将新的PQC算法添加为密码套件选项，并且可以删除过时的算法。
第三，形式化建模。密码迁移的形式化建模是一个亟需研究的领域。无论使用何种迁移技术，系统的安全性仍然是一个问题。对于给定的方案，形式化的方法可以帮助以更基本的方式回答这一问题。组织还需要此建模来评估将迁移所需的框架合并到广泛使用的加密协议中的安全性。例如，广泛使用的TLS协议可能会被分解成可以抵御量子计算机攻击进行研究的常规组件。
第四，自动化工具。如果不使用自动化方法，由于加密基础设施的规模，迁移几乎是不可能的。因此，也需要在此方面展开研究。
（二）密码敏捷性领域的扩展
密码敏捷性是研究界的一个既定概念，向PQC迁移的广泛性使得扩展研究领域成为必要。因此应开发一种密码敏捷性科学，以涵盖更大范围的目标、计算域、敏捷性模式和时间尺度。为了实现加密敏捷性，应在广泛的计算环境中开发和研究框架与体系结构，以及满足众多用户角色的可接受接口。
几乎没有其他定义性挑战，例如在加密解决方案中识别正确区域后嵌入敏捷性。CA应该预测未来可能出现问题的区域，并使用该信息来设计系统。
另一个挑战是如何解决旧设备中的加密敏捷性问题，这些旧设备可能无法重新配置。需要考虑的最重要的方面是：为软件产品的供应商和开发人员创建正确的激励措施，以将加密敏捷性纳入所有必需的产品，而客户和政府在此方面发挥着重要作用。
五、未来研究方向的展望
后量子密码学是一个新的研究课题，在未来几年将无处不在。密码系统建立在6个主要家族之上，其在安全性、大小和内存以及计算要求方面各有优缺点。研究人员可以找到量子计算机难以解决的新数学问题，并以此为基础建立新的密码系统。
第一，研究人员正在努力开展研究，对NIST算法的候选者和替代方案的安全性进行密码分析将有助于提高算法的安全性，并防止可能不安全的算法标准化。
第二，研究人员还可以通过实施新的硬件和软件设计来优化算法，这有助于减少算法的时间和空间成本。
第三，研究人员可以研究轻量级后量子密码学。不可否认，物联网设备的增加使得轻量级密码学成为一项要求。物联网设备使用加密数据相互通信，因为某些数据可能是私有的（商业秘密）。因此，轻量级后量子密码学也是一个重要的研究领域。
第四，数论和算法研究是研究人员可以研究后量子难题的另一个领域。他们可以研究新的数学技术来破解后量子密码系统的安全性所基于的难题。关于多元二次映射问题和基于格的难题已有大量研究。在此方面，研究人员正在提出新的解决方案和技术来解决难题。
第五，量子密码分析和开发新的量子算法是另一个鲜为人知的研究领域。Shor提出了两种量子算法，破解了当今非对称密码算法的安全性。后量子密码算法也可能有不同的量子算法，这可能会危及它们的安全性。因此，必须在该领域进行更多的研究。（方婷 赵婧琳）
声明：本文来自苏州信息安全法学所，版权归作者所有。文章内容仅代表作者独立观点，不代表安全内参立场，转载目的在于传递更多信息。如有侵权，请联系 anquanneican@163.com。
