量子时代密码学概述（第三部分）

在 Google 新闻上关注 Kryptus

通过: Waldyr Benits 博士 | Kryptus 密码学主管

量子时代密码学概述（二）：NIST PQC 标准化流程

1. NIST PQC标准化流程

O 美国国家标准与技术研究所 (NIST) 于 2017 年中期发起了一项国际竞赛，旨在提交潜在的后量子算法以供标准化。这个过程被称为 NIST PQC 标准化流程。因此，最初提出了 69 种后量子标准候选算法，经过大约一年的时间，经过该研究所的技术分析，选择了 1 种候选算法来继续上述竞争进程。预计获胜者将于 26 年至 2022 年间公布。

2020 年 3 月，NIST 公布了进入第三轮的最终入围者和备选方案。一些算法未能进入第三轮，因为在其构造中发现了严重的安全漏洞。 NIST 指出，与 DES 和 AES 标准化过程不同，它并不期望只选择一种算法作为“赢家”。理想情况下，会出现几种算法作为“好的选择”，并且应该有一种以上的算法被指示为后量子标准，这样，用户就可以为每个应用选择最合适的 PQ 标准。

O NIST 05 年 07 月 2022 日发布了第 3 轮选出的后量子算法以及进入下一阶段评估（第 4 轮）的算法，如下图 1 所示。

图1

2. 入选算法及晋级第四轮算法的简要分析

Kyber 基于结构化格子。其安全前提是 LWE 问题（错误中学习）。它表现良好（就效率和密钥/密文大小而言）。

经典 McEliece 创建于 1978 年，至今尚无已知的有效攻击方法。它基于纠错码，具有非常大的公钥但密文非常小。

BIKE 和 HQC 基于结构化代码。两者的按键尺寸都比 Classic McEliece 小得多。

SIKE 基于椭圆曲线同源性。 SIKE 的主要缺点之一是其执行时间较长，这使得该方案目前成为最慢的候选方案。然而，这一缺点被所有候选者中最小的密钥大小所抵消。

至于数字签名算法，Dilithium 和 Falcon 算法基于结构化格。 Dilithium 是 Fiat-Shamir 风格，而猎鹰是 哈希然后签名。两者表现都很好。 NIST 预计最多选择一个进行标准化。

SPHINCS+ 基于哈希函数的安全性。从好的方面来看，SPHINCS+ 的安全性非常容易理解。

3. 第三轮结果公布时提出的考虑

NIST在发布第三轮结果的报告中提出了以下考虑：

CRYSTALS-KYBER（PKE/KEM）和CRYSTALS-KYBER算法Dilithium（数字签名）因其强大的安全性和出色的性能而被选中，NIST 预计它们将在大多数应用中发挥良好作用；

CRYSTALS-KYBER 已获得专利。 NIST 预计将在发布标准之前签署各种合同。如果这些合同在 2022 年底前未能签署，NIST 可能会考虑选择 NTRU 而不是 KYBER。

Falcon 也将由 NIST 进行标准化，因为在某些用例中 CRYSTALS-Dilithium 签名可能太大；

此外，SPHINCS+ 将实现标准化，以避免仅仅依赖格子安全进行签名；

BIKE 和 HQC 都基于结构化代码，并且都适合作为非基于格的通用 KEM。 NIST 预计在第四轮结束时最多从这两个候选方案中选出一个进行标准化；

SIKE 因其密钥和密文较小而仍然是标准化的有吸引力的候选者，并将在第四轮继续研究。

经典麦克埃利斯 (McEliece) 赛事已入围决赛，但目前尚未标准化。尽管 Classic McEliece 被广泛认为是安全的，但由于其公钥规模较大，NIST 预计它不会得到广泛应用。 NIST 可能会选择在第 4 轮结束时对 Classic McEliece 进行标准化。

在本系列的下一篇也是最后一篇文章中，我将报告针对其中一些算法已经发布的主要攻击，重点介绍一种意味着破解 SIKE 的攻击。