葱一根 - one sat on Nostr: II Preparing for the Quantum Break 为量子破解做准备 Chapter 6: ...

 II
Preparing for the Quantum Break
为量子破解做准备
Chapter 6: Quantum-Resistant Cryptography
第六章：抗量子密码学
Chapter 7: Quantum Cryptography
第七章：量子密码学
Chapter 8: Quantum Networking
第八章：量子联网
Chapter 9: Preparing Now
第九章：现在准备

6
抗量子密码学
 
我们将在后量子世界中使用的密码学，是量子抵抗密码学和基于量子的密码学的结合。量子抵抗密码学是一种传统的、基于二进制的密码算法，能够抵抗已知的量子攻击。量子密码算法是使用量子计算和属性，来保护信息的密码学。本章将介绍抗量子密码，第7章将介绍基于量子的密码。
这一章充满了密码技术和高级数学术语。一般的计算机安全读者可能想知道为什么他们应该对特定算法背后的所有技术细节感兴趣。他们可能会觉得他们真正需要知道的是量子后算法…的名字。这也许是真的。
但是它对于任何涉及实现加密的人理解所涉及的加密的基本知识，都是非常有帮助的。本章给出了二十多个抗量子算法的基本概述，这样你就可以理解它们，就像你可能已经理解大素数给RSA和Diffie-Hellman密码带来的内在保护一样，以及为什么对素数的依赖使它们容易受到量子攻击。当有人（无论是最终用户还是老板）就你特定的后量子实施计划提出更具体的问题时，知道更多的密码算法的名称才能有所帮助。另外，在与同行讨论后量子计划时，你会更有信心。您不必了解特定算法的每一个细节，但对它的工作原理有一个大致的了解是有帮助的。

NIST量子后竞赛

现有几十种抗量子密码和数字签名，其中大多数已经由世界各地的各种密码专家和团体进行了多年的评估。2015年，欧洲电信标准研究所（ETSI）与世界各地的科学家和研究人员一起，成为第一个认真研究抗量子密码的大型公共团体，随后包括美国在内的许多其他国家的团体也开始研究。
美国国家标准与技术研究所（NIST；见www.nist.gov）多年来一直举办公开的“类似竞赛”的竞赛，以评估各种新提出的加密技术，以取代现有的、正在削弱的加密技术。获胜的算法成为较新的美国密码标准，它们的创造者同意允许它们免费使用。
在美国国家安全局（NSA）的大力协调和参与下，以前的NIST竞赛选择了SHA-3作为新的散列标准，选择了AES作为新的对称密钥加密标准。总的来说，这些以前的公开密码竞赛被视为巨大的成功。不仅有许多合格的候选人得到提交和公开评价，但大多数人认为，比赛和比赛的优胜者是适当的（虽然这并不总是与每一个NIST/NSA加密评估的情况下；见侧边栏"可疑的NIST/NSA竞赛"）。

可疑的NIST/NSA竞赛

尽管NIST/NSA竞赛目前相对为大多数利益相关者所信任，但至少有两次此前的案例表明，NSA似乎主动削弱了密码标准，从而使NSA更容易打破密码标准。这是在1977年选择数据加密标准（DES）对称密码时首次完成的。NSA说服IBM（DES的创造者，当时被称为Lucifer密码）将提议的保护密钥长度从64位缩短到56位，他们正试图将其缩短到48位。IBM的妥协，使DES使用64位密钥，但大部分的保护实际上是在最初的56位。
NSA在2006年再次招致批评，当时他们要求所有电脑制造商（卖给美国政府，通常是电脑最大的买家）包括一个新的，但超级脆弱的，随机数发生器（RNG）被称为Dual_EC_DRBG。它包含了一个数学缺陷，创建了一个秘密后门进入任何依赖它的密码系统。当然，NIST和NSA并没有宣传它有一个后门，从来没有人能够证明这个缺陷是故意的。但即使在漏洞被发现后，NIST表示，涉及的RNG必须包含在任何出售给美国政府的计算机中，作为密码集合Suite B的一部分，此外（因为只制造一个版本的电脑更容易），几乎每台卖给非政府客户的电脑都将包含该软件。即使供应商在他们的计算机上包括它，世界上大多数国家并没有使用它。
美国国家安全局没有被阻止，甚至秘密支付非常流行的计算机设备供应商使用的漏洞RNG，这意味着任何客户使用他们（可能不知情）使用严重削弱保护。这是一个加密噩梦成真。在应用密码学领域，最大的谜团之一是为什么那些商家在被发现接受美国政府的贿赂后，却没有得到更多的公众反对。布鲁斯·施奈尔（Bruce Schneier）在2007年对该问题进行了出色的总结:www.schneier.com/blog/archives/2007/11/the_strange_sto.html. 2013年，美国中央情报局泄密者爱德华·斯诺登披露了之前所有关于故意安装窃听器的RNG和美国国家安全局主动将其推给人们的阴谋的怀疑。
这两起事件严重损害了许多人对美国政府选择真正安全的加密标准的信心。它表明，负有保护和监视公民双重责任的政府实体往往会让薄弱的加密技术赢得更好的保护。尽管这两个问题的严重和相应的不信任，大多数观察家认为，NIST/NSA比赛挑选最近的新密码标准（即SHA-2、SHA-3、AES和后量子密码）可以被信任。
从2016年2月开始，NIST开始了一项名为NIST后量子密码标准化进程（https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf)选择用于公钥交换和数字签名的后量子(即抗量子、量子安全)密码标准。第一轮候选人必须在2017年11月之前提交审议。NIST收到了82份独特的意见书，并允许69人继续作为正式的“第一轮”候选人。其中，17个非对称加密算法和9个数字签名方案于2019年1月被选中，继续进入“第二轮”（https://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf).第三轮候选人预计将于2020年或2021年正式宣布。最终的后量子密码学新标准预计将在2022年至2024年期间公布。本章将总结所有正式的第二轮候选人。
NIST/NSA竞赛的获胜者通常通过NIST联邦信息处理标准（FIPS）出版文档成为美国联邦政府的官方标准。美国政府以及任何政府分包商销售和使用的所有政府计算机和设备都必须遵循这些标准。这将导致在美国销售的所有设备和计算机都包含和使用这些标准，因为美国政府是计算机设备的最大买家。计算设备和软件供应商发现，将美国联邦标准纳入他们制造的所有设备中，比制造政府和非政府版本更容易，成本效益更高。因为美国是世界上最大的经济体，美国的标准经常成为事实上的全球标准（尽管许多较大的国家，如俄罗斯和中国，创建和使用自己的国家标准）。出于这个原因，非常重要的是放在NIST/NSA密码标准的比赛。它们的结果影响了我们世界上使用的许多计算机和软件。
如果您对每个NIST加密提交的细节感兴趣，我强烈建议您下载算法提交者提交文档，位于https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-2-Submissions.大多数最好的细节都包含在团队提交的zip文件的Supporting_Documentation文件夹下的PDF文档中。NIST要求每个加密提交都有大量相关信息，包括算法如何工作、弱点、优势、攻击弹性、演示的性能统计数据、代码示例、NIST安全强度级别建议（稍后将进一步详细介绍）等。您可以在NIST竞赛提交网站上阅读支持者和批评者的评论，以了解该算法在密码专家审查下的表现。

NIST安全强度分类

在NIST Post-Quantum竞赛中，所有提交的算法必须包括符合特定保护强度的具体实现，如表6.1所示。增加保护是通过增加NIST安全级别数目来表示的（例如，NIST安全级别4比安全级别3提供更多的保护）。
表6.1:NIST安全强度分类和等效保护
NIST认为，所有五个等级都是抗量子的，尽管它描述安全级别1为“在可预见的未来可能是安全的，除非量子计算机的改进速度比预期的更快”，也就是说相当弱。这是因为使用格罗弗算法的量子计算机可以有效地将AES-128的保护强度削减到只有64位。目前还没有公开的攻击可以破解64位强度的AES，但未来的攻击可以做到这一点并不遥远。因此，许多密码学专家并不认为仅仅满足NIST安全级别1的密码学实现是真正的长期抗量子性。然而，NIST认为它们目前是可以接受的，并将它们视为在时间和资源允许的情况下使用更抗加密的“桥梁”。
NIST认为安全级别2和3“在可预见的未来可能是安全的”，而安全级别4和5“可能过度”。加密人信任“可能过度”的抗加密，但性能和实现方面的考虑可能会阻止它们目前的部署。例如，许多当前的软件程序和设备默认使用AES-128，不能使用AES-256或更大的（目前还不能）。
大多数NIST的竞争对手提交了他们的算法实现，以满足NIST的安全级别1，3和5，和大多数跳过级别2和4。也有例外。NTRU Prime没有提交NIST安全级别1和5。ThreeBears没有提交NIST安全级别1和3密码，但提交了级别2和4。SIKE提交了NIST安全级别2的示例，NTRU Prime也提交了级别2和4。CRYSTALS-Dilithium和MQDSS没有提交5级示例。FALCON没有提交第2级、第3级或第4级实施。LUOV没有提交1级或3级样品。
有关NIST安全强度分类的更多信息和详细信息，请参阅以下NIST文档的第4.A.5节"安全强度类别":
https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf (https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions), at Privacy News Online (www.privateinternetaccess.com/blog/2019/02/nist-round-2-and-post-quantum-cryptography-the-new-asymmetric-algorithms-part-2/), and by many other sources, including Wikipedia (https://en.wikipedia.org/wiki/Post-quantum_cryptography).
在NIST项目网站上有关于每种算法的优秀总结讨论（https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Round-1-Submissions),在隐私新闻在线
(www.privateinternetaccess.com/blog/2019/02/nist-round-2-and-post-quantum-cryptography-the-new-asymmetric-algorithms-part-2/),和许多其他来源，包括维基百科（https://en.wikipedia.org/wiki/Post-quantum_cryptography).
下面的章节总结了NIST第二轮的候选人。每个加密算法都被描述为它做什么，涉及什么基本原则，有时有点历史（如果有必要的话），以及每个提交团队的国家组成。团队的组成也包括在内，以显示他们往往是多国的组合。在讨论密码和方案之前，将定义相关的术语和类型。
注：本章所涉及的许多算法也是在开放量子安全（https://openquantumsafe.org/)项目中。Open Quantum Safe-开放量子安全项目是一个代码库和组织，帮助我们为后量子世界做好准备。当加密实现被记录为参与该项目时，这意味着组织可以在今天的测试和现实世界场景中实现特定的后量子算法，使用来自以前实现者的经验教训和信息，并共享挑战和新的经验教训。

PKE与KEM

传统的公钥加密技术，也称为公钥加密（Public Key Encryption，PKE），通常用于传输对称密钥，然后用于加密需要加密保护的明文内容。对称密钥比非对称加密更快、更强（对于较小的密钥大小），因此PKE通常仅用作对称密钥的安全传输工具，而对称密钥实际上完成了所有直接加密工作。PKE几十年来一直发挥着巨大的作用，但它们至少有一个很大的内在缺陷。
当公钥比被加密的内容长时（例如在密钥交换中对称密钥通常是这种情况），它允许攻击者通过一种非常简单的方法获得原始私钥。为了防止这种情况，当要加密的消息内容（例如对称密钥）比用于加密的非对称私钥短时，PKE通常会向要加密的消息添加额外的“填充”（例如对称密钥）以消除漏洞。不幸的是，填充的随机生成往往是PKE系统中最薄弱的环节。PKE攻击者往往集中在填充中的逻辑缺陷，并发现漏洞。对称密钥很可能只会变得更长，特别是为了减轻改进的量子攻击。这是一个潜在的持续风险。
密钥封装方法（Key encapsulation methods，KEM），也称为密钥封装方案（key encapsulation scheme），是一种非对称加密技术，旨在提高对称密钥的安全传输（或生成），因为它们不需要在短消息中添加随机填充来保持安全。许多后量子密码算法特别有利于创建KEM，因为后量子算法通常具有更长的非对称密钥，您将看到许多抗量子团队提供KEM而不是PKE。这有时通过在算法的名称中包含KEM来表示，例如在FrodoKEM和NTS-KEM中。一些后量子密码算法将同时提供PKE和KEM两种版本。

形式上的不可区分性保证

您将在一些密码名称和描述中看到的CPA和CCA字母是指一种始终需要的密码属性，即密文不可区分性。密文不可区分性意味着生成的密文看起来非常随机，以至于攻击者无法使用密文找到对相关加密密钥的更容易的攻击。注册会计师的指定意味着攻击者甚至可以知道，选择明文提交（即，选择明文攻击），看到产生的密文，仍然没有得到有关所涉及的秘密加密密钥的线索。CCA代表选择密文攻击，攻击者可以选择一个特定的密文并将其解密为明文，但仍然得不到有关秘密加密密钥的提示。见https://en.wikipedia.org/wiki/Ciphertext_indistinguishability了解更多详情。
数字安全系统的安全性，有时被描述为EUF-CMA和/或SUF-CMA，这在某种程度上，可以被视为类似于用于总结基本非对称密码系统安全性的CPA和CCA描述符。EUF-CMA表示选择消息攻击下的存在不可伪造性，SUF-CMA表示选择消息攻击下的强存在不可伪造性。使用这两种指定，攻击者可以要求对任何内容进行签名，并获得签名，但仍然无法确定用于对内容进行签名的私钥。使用安全性略强的SUF-CMA，攻击者无法创建不同的数字签名，该签名仍然可以在原始数字签名方案下验证来自相同的内容和私钥（即，对于相同的唯一内容使用相同的数字签名方案生成两个不同的有效签名将是不好的形式）。然而，拥有这些属性和证明一个算法绝对拥有这些属性，是能够声称一个或两个描述符之间的区别。有关EUF-CMA和SUF-CMA的更多信息，请参见https://blog.cryptographyengineering.com/euf-cma-and-suf-cma/.
所有好的PKE和KEM通常会尝试满足CPA和CCA安全要求，数字签名通常会尝试EUF-CMA安全。要使用这些名称，加密算法必须首先从理论上证明其安全性，并随着时间的推移保持持续的攻击。NIST要求成功的加密候选者是CPA和CCA安全的或EUF-CMA安全的，这取决于加密算法类型。大多数提交的算法在其提交文件中明确指出满足这些安全保证目标，虽然NTRUPrime和NTS-KEM没有明确指出满足CPA目标。

密钥和密文大小

所有非对称密码都有两种相关的加密密钥：秘密密钥和公开密钥。密钥（也称为私钥）用于对内容进行签名，应该只有密钥对持有者知道。在一些后量子算法（如CRYSTALS-Dilithium、 SPHINCS +和 LUOV ）中，密钥只是一个种子值，用于生成其他执行实际工作的密钥。在这些实现中，秘密密钥通常很小（16到64字节），并且对于任何安全强度实现来说，其大小都是恒定的。在这些情况下，相关的公钥通常也非常小。对于不同的版本，抗量子算法可以针对不同的强度级别以及不同的实现意图（例如，更快但更不安全的实现）使用可变长度的密钥。
公钥用于加密内容和验证由相关私钥签名的内容。公钥理论上可以被全世界所知道和使用，而受保护的秘密仍然是秘密。公钥意味着每个人都可以使用。这是非对称系统的工作方式。对于非对称密码，相关的公钥是从私钥生成的。
密文，一般来说，是指任何加密的内容，虽然在比较不同提交的密码的上下文中，它是指最小的加密明文在加密后会变得多大。例如，如果您只使用现代密码对字母A进行加密，那么生成的密文通常会比单个字符大得多。
数字签名是散列内容的唯一结果。在数字签名方案中，公钥和数字签名的大小在数学上是成反比的。如果你减少其中一个的大小，另一个就会增加，反之亦然。因此，在大多数后量子数字签名提交中，如果您看到一个小公钥，您也会看到一个大的数字签名，反之亦然。
NIST要求所有加密算法提交者为每个NIST安全级别声明声明这些变量的大小。非对称加密密码也被要求提交最小密文的大小。要求数字签字方案提交所产生的数字签字的大小。大小非常重要，因为非常大的大小通常会有性能和存储问题（与较小的竞争对手相比），并且通常会占用更多的内存空间、存储空间和网络带宽。然而，特定算法的计算复杂度通常对整体加密性能有更大的影响。
许多算法具有更大的不同密钥大小的潜在实现，而不仅仅是为了满足特定的NIST安全强度级别而提交的实现。一些算法允许使用任意大小的密钥（在边界内），这取决于实现者所需的安全性与性能要求。

后量子算法的类型

在讨论不同的后量子算法时，了解算法的主要类型并总结它们针对基于量子的攻击的保护方法是很有帮助的。

基于代码的密码学

基于代码的加密（也称为代数编码或纠错码【 ECC 】）是一组众所周知的具有抗攻击性的加密和签名加密技术，它基于数学算法，故意将“错误”（即加密）引入明文内容，从而使原始内容变得模糊/加密。相应的“纠错”代码/算法可用于删除“错误”并将加密的内容呈现回原来的明文表示(即解密)。
举个简单的例子，假设发送方要加密的明文是1111。“错误”将被有意地引入到内容中，例如生成011101，然后将其传输到接收器。接收方的“纠错”过程将消除“错误”并可靠地再现原始1111内容。
基于代码的加密是基于类似ECC的方法，这种方法是如此复杂，以至于在不知道所涉及的密钥的情况下解决“错误”是非常困难的（即，不平凡的）。在20世纪70年代和80年代，俄罗斯/苏联数学家Valery Denisovich Goppa将几何形状和组合与ECC联系起来。今天，这些码被广泛称为Goppa码，并被密码学家所采用。最成功的基于代码的密码之一，McEliece（本章稍后将介绍）是基于二进制Goppa码，一般来说，大多数基于代码的密码都是基于二进制Goppa码。提交给NIST的第二种最流行的非对称加密密码是基于代码的密码。基于代码提交的密码包括BIKE、Classic McEleece、HQC、LEDAcrypt、NTS-KEM、Rollo和RQC。
基于代码的密码学面临两大技术挑战。首先，ECC加密需要比通常更多的密钥位（与其他密码类型相比）来加密数据。基于代码的加密密钥，特别是公钥，可以轻松地覆盖超过300,000位。在20世纪70年代和80年代，当McEliece第一次被引入时，这曾经是一个巨大的问题，但今天它不是一个大的计算障碍。此外，许多基于代码的密码必须能够显著减少其密钥大小（例如，许多密码使用40字节的密钥）。但是，如果您看到与非对称加密密码相关联的绝对巨大的密钥，它很可能是基于代码的。
其次，由于ECC正在纠正假定的“错误”，如果没有适当的设计，“错误”总是有机会通过，这意味着即使使用正确的解密密钥，合法的解密也可能失败。这意味着，解密可能必须执行一次或多次额外的时间，甚至有机会，一个特定的ECC解密实例可能永远不会工作，或可能会停留在一个临时的，自我诱导的，拒绝服务的循环事件。大多数ECC密码试图防止这种锁定，锁定是极其罕见的--几乎为零。但是，如果您了解到ECC密码具有“非零”解密失败率（如HQC），那么至少要注意理论上的可能性。
关于ECC和Goppa代码的一个很好的总结讨论可以在这里找到：
https://surface.syr.edu/cgi/viewcontent.cgi?article=1846&context=honors_capstone

基于哈希的密码学

基于哈希的密码学是基于密码散列的，顾名思义，通常适用于数字签名方案(相对于加密)。如前几章所述，散列是一种单向函数，它将散列的内容转换成一组具有代表性的位（称为散列、散列结果、签名或消息摘要）这是唯一的独特的内容。小型管理系统（扩展的Merkle签名方案），莱顿-米卡利签名（LMS）、区块链后量子签名（BPQS）、SPHINCS和SPHINCS +数字签名方案是基于散列加密的。SPHINCS +是 NIST 在第二轮比赛中提交并接受的唯一基于散列的数字签名。
Ralph Merkle基本上发明了加密哈希领域，他还参与了第一个公开的公钥加密实现（与Whitfield Diffie和Martin Hellman一起）。因此，在讨论基于散列的密码学时，您经常会听说Merkle树(即散列树)和Merkle方框和谜题。Merkle树是一个分层的散列序列，散列其他散列，散列原始内容。有兴趣的话，请看https://en.wikipedia.org/wiki/Merkle_tree关于Merkle树的更多细节。
基于散列的密码学被认为是量子抵抗的，因为散列不容易受到Shor算法的影响，尽管它们容易受到Grover算法的影响。量子计算机上的Grover算法在处理特定类型的问题（如破解散列）时，比二进制计算机的平方根算法有更大的改进。这有效地将任何基于散列的加密技术的强度减半。这也意味着将散列的密钥大小增加一倍可以抵消Grover算法和量子计算所获得的攻击收益。
附注：底层散列必须符合一个好的、安全的散列的所有属性（前面讨论过），这一点至关重要。如果一个散列随着时间的推移不能成为一个“好的散列”，那么任何基于该散列的密码学将变得不仅容易受到量子计算的影响，而且也容易受到二进制计算的影响，其强度远远低于其所声明的密钥强度。
所有的散列都受到它们可以保护的消息数量的限制，在散列结果对于它们可以散列的所有可能的唯一输入变得（过早地）冗余之前。例如，在撰写本文时，所有微软Windows登录密码都被转换为NT哈希值。您可以在Windows中创建多个千万亿的唯一可能的密码（近265535种不同的组合），但是相同的NT散列对于许多不同的密码最终会是相同的（在散列攻击理论中，这被称为第二个原像冲突的例子），因为散列及其密钥空间的固有限制（即所有可能的选择）。
如果基于哈希的密码术“意外地”为两个不同的输入重复相同的一次性密钥，那么攻击者将能够深入了解私钥。因此，哈希和基于哈希的密码学开发人员会竭尽全力防止一次性密钥重复。有几种不同的方法来减少重复。
解决这种风险的一种方法是通过提高哈希算法的准确性来区分唯一的内容。如果散列总是产生唯一的散列输出，那么重复的问题就没有了。这可能很难做到，因为散列的键空间总是受到比它试图散列的潜在内容更多的限制。为了抵消这一风险，散列开发者还可以增加所得到的数字签字的大小（即提供更多的钥匙空间）。数字签名越长，散列结果的可能性就越大。因此，具有128位哈希结果的散列可能比仅限于64位结果的哈希更精确。非常大的数字签名可能会变得过于庞大和笨拙，从而导致性能和存储问题。大多数密码学专家认为，一个好的散列，利用其固有的算法准确性，不应该导致非常大的数字签名。其他人则认为，大型数字签名是确保准确的散列而没有内置的散列结果冗余的唯一方法。无论哪种方式，都要额外考虑非常小和非常大的数字签名。
另一种防止密钥重复的常用方法是使散列有状态（相对于无状态）。有状态哈希跟踪它使用的每一次密钥，并确保它不会再次重用它。大多数传统的基于签名的散列是有状态的。如果检测到重复的密钥，则再次运行该算法，或者选择较长密钥流的不同部分来生成另一个唯一的一次性密钥。
有状态散列和无状态散列各有优缺点。无状态散列不能保证唯一的密钥，但通常具有较大的密钥大小。有状态散列通常具有更小的密钥大小，但是因为它们必须存储一个“状态表”，所以从资源、存储和安全的角度来看，它们是庞大的。有状态散列还会在数据恢复事件期间创建一个关键问题。如果处理得不够小心，恢复的有状态散列实现可能会覆盖其以前的状态表，擦除以前使用过的密钥的证据，然后散列可能会意外地在将来的加密操作中再次使用相同的密钥。知道状态表已被覆盖的攻击者可能会寻找重复密钥的迹象，并在加密攻击中利用这一优势。这是一个相当不可能的事件，风险相当低，但如果密码学家发现任何理论上的弱点，它被认为是一个很大的弱点。因此，NIST不允许有状态的基于散列的加密算法被提交考虑，从而淘汰了几个在其他方面很强的竞争对手。

基于格的密码学

格是一个三维的，分布式的，重复的几何排列/模式的东西，例如，对象或点，在一个空间。格子在自然界中随处可见，如分子或晶体中，人们经常使用它来创建其他更大的物体，包括网、栅栏或编织图案。许多数学公式和算法创建格。基于格的公式和结果已经被创造出来，这些公式和结果是很难分解的（称为计算格问题）。在密码学中最常见的格问题被称为带错误学习（LWE）、带错误的环学习（RLWE）、带误差的模块学习（MLWE）、带舍入的学习（LWR），以及几十个变体。每种类型的问题都有自己的优点和缺点。一般来说，与经典LWE相比，LWE涉及环的速度更快，密钥尺寸更小，但也包含新的数学结构，这些结构还没有经过充分的测试。
注意：当你学习密码学，特别是后量子密码学时，你会读到很多关于“环”的东西。环是抽象代数中的一种基本而复杂的数学结构。见https://en.wikipedia.org/wiki/Ring_(mathematics)了解更多详情。
这些非常难以解决的格问题已被用于创建公钥加密和数字签名方案，这些方案对二进制和量子计算机都具有抵抗力。使用基于格的密码术，创建一个复杂的格函数作为私钥。公钥是作为原始格的修改版本生成的。使用修改后的版本（公钥）对内容进行加密，只有原始格版本（私钥）的持有者才能轻松地将加密消息恢复到原始明文状态。
基本上，基于格的密码学创造了一个数学工作量问题，它在某种程度上相当于或大于分解大素数所需的工作量，但不依赖于大素数来保护它们。随后，基于格的密码学被认为不受Shor算法或任何影响素数的量子算法的影响。
从消极的理论上讲，与其他密码类型相比，基于格的密码可能需要相对较大的密钥大小，尽管非常重要的是，这并不适用于大多数向NIST提交的基于格的候选方案，包括CRYSTAL-KYBER、LAC、NewHope、NTRU、NTRU Prime、Round5、SABER和ThreeBears。只有FRODO-KEM有一个相对较大的密钥大小，虽然几个基于代码的算法是大得多。
第一个基于格的密码是NTRU，于1998年推出，其次是基于LWE和RLWE数学问题的多重密码。今天，基于格的密码是提交给NIST的最流行的后量子密码类型。此外，2009年克雷格·金特里在他的论文（https://dl.acm.org/citation.cfm?id=1834954)使用基于格的密码学创建了第一个现实世界中的完全同态加密系统，如前一章所述，该系统允许第三方在不首先解密的情况下正确地操纵加密数据。
注：大多数基于格的密码及其相关问题是基于最短向量问题（SVP），这需要至少超指数时间来解决。不幸的是，由最短向量问题（SVP）提供的整体安全性是不完全理解，和一些理论上的攻击已经显着削弱了其保护。因此，所有基于格的密码学(尤其是那些基于svp而没有抵消效应的密码学)都不是完全可信的，而且可能会被发现比以前在未来所理解的要弱。这可能是有问题的，当再加上事实上，大多数后量子密码（提交给NIST）是基于格的密码。

多元密码学

多元简单地说就是“多个变量”。多元加密是指依赖于多元多项式数学方程的非对称加密和签名方案，如x+ y + z = n ，形成密码基元。您还将听到基于多元多项式数学的密码术称为多元二次（MQ）多项式方程密码术。这是指至少一个变量被提升到第二次幂（例如， x的2 次方+ y + z = n ）的事实。正确创建的多元密码学不能在多项式时间内解决，也不依赖于大素数的保护。因此，它们被认为是抗量子的。它们的固有特性也使它们的硬件实现，如专用集成电路（ASIC）和现场可编程门阵列（FPGA）的良好的性能候选。
多元加密包括HFE、GUI、平衡油和醋、不平衡油和醋（一些算法的名字是故意幽默的）和驯服变换签名。提交的多元数字签名方案包括GeMSS、LUOV、MQDSS和Rainbow。彩虹是一个多层次的实现不平衡的油和醋。

超奇异椭圆曲线同构密码

超奇异椭圆曲线等基因密码学（简称等基因密码学）依赖于生成超奇异椭圆曲线和等基因图的数学方程和算法，来对其进行加密保护。椭圆曲线是由表示不自相交（也称为非奇异）的代数曲线的数学公式创建的。所有的超奇异曲线都是非奇异的，“超”部分指的是异常大的环。等价类是指在彼此之间共享相关值相交的独立代数群。举个简单的例子，假设你有一组数字1、2、3和4，另一组有字母A、B、C和D，每个数字都与相应的字母有关。它们是同源的。等基因曲线将是两条曲线（当然是用数学表示的），这两条曲线可以相互映射。
在同源密码学世界中，两个不同的算法方程正在创建一个可用于加密和解密的同源链接。公钥是一对椭圆曲线，私钥是它们之间的等价键。找到这个同构只给对超奇异椭圆曲线被认为是一个非常困难的问题来解决。如果这听起来很复杂，要知道，超奇异椭圆曲线isogeny方程是有史以来最困难的数学问题，但已经研究得很好，足以欣赏它们的长处和短处。
2012年，中国研究人员创建了第一个基于超奇异椭圆曲线等同性和多元密码学的量子安全数字签名（https://pdfs.semanticscholar.org/527a/4abe13ee6ce7858e040ceaa7cd0b983969d8.pdf).等元密码技术往往具有非常小的密钥大小，并且允许简单、完美的前向保密。完美前向保密（Perfect forward secrecy）是一种加密保护，涉及频繁更改会话密钥，使得将来的密钥泄露不能被用来更容易地破解以前的会话，因为它们使用不同的密钥。完美的前向保密性通常是一个理想的密码学特性，尽管它往往不能达到。同质异能符合完全的前向保密性。不利的一面是，同源密码学相对较新，所以它还没有像其他后量子密码学类型那样被测试和攻击。虽然早期的等基因实现已经受到损害，如使用超奇异等基因，而不是仅仅非奇异曲线的变化防止了已知的攻击。NIST在第二轮评估中提交并接受的唯一同构密码是SIKE。

零知识证明

零知识证明（ZKP；也称为零知识协议）是一种方法，其中一方（称为证明者）可以向另一方（称为验证者）证明他们知道值x，不需要传达或证明任何信息，除非他们真的知道值x，实际上不提供值x或泄漏任何额外的，不必要的信息。
常用ZKP系统的一个示例是在现代的“挑战-响应”认证系统中使用的登录密码。让我们假设一个用户想使用一个有效的密码登录到服务器，但同时不允许服务器知道或存储明文密码（这样它就不会被窃取或泄露）。在不提供正确密码的情况下，用户如何向服务器证明他们拥有（并且可以使用）正确的密码呢？
ZKP的一个解决方案是使用基于密码的加密质询-响应散列，但不使用实际密码。例如，假设用户的明文密码是frog。当用户第一次创建它时，让我们假设frog的明文密码立即被散列，散列结果是1234。散列结果是发送到服务器并存储在服务器上的密码的唯一版本。服务器无法知道原始的明文密码。
ZKP的一个解决方案是使用基于密码的加密质询-响应散列，但不使用实际密码。例如，假设用户的明文密码是frog。当用户第一次创建它时，让我们假设frog的明文密码立即被散列，散列结果是1234。散列结果是发送到服务器并存储在服务器上的密码的唯一版本。服务器无法知道原始的明文密码。
当用户想要登录到服务器时，他们会发起到服务器的连接。服务器创建一个随机值，比如9876，并将其发送给用户（称为挑战）。用户从9876中减去密码哈希值1234，得到结果8642，并将其发送回服务器（称为响应）。服务器使用用户存储的密码散列1234对随机生成的数字执行相同的减法，这样做将得到相同的结果（8642），并将其与用户返回的结果进行比较。只有原始密码为frog的用户才能得到正确的哈希值1234，并能从随机生成的值9876中减去该值，从而得到正确的结果。因此，用户可以成功地向验证服务器证明他们拥有正确的原始密码，而无需透露明文密码是什么。大多数现代身份验证系统，包括微软Windows密码，都使用类似的（尽管更复杂）方案。
许多计算机供应商都声称ZKP实现。就像之前的其他计算机安全术语（如人工智能或区块链）一样， ZKP 被过度使用。许多供应商错误地使用它来不准确地描述比实际使用它更多的产品。因此，当您看到供应商使用ZKP短语时，请首先持怀疑态度。话虽这么说，密码学家是一个相当严肃和真实的群体。当密码学说他们的算法使用ZKP时，他们通常不会轻易地说出来或没有支持。ZKP密码学通常涉及证明一些加密的知识，如离散对数函数，而不透露函数本身。在加密界，您可能会听到"证明和验证"步骤，也称为sigma协议或（三步或三条消息）证明。唯一使用ZKP的抗量子算法是Picnic数字签名方案。

对称密钥量子电阻

这是指传统对称密钥加密和认证算法固有的抵抗量子攻击的能力。如前所述，对称密码不容易受到Shor算法的影响，Grover的算法将它们的保护减半。因此，从某种意义上说，对称密钥密码已经是量子抵抗的，只要它们的密钥大小足够抵御Grover算法的攻击。今天，这意味着使用密钥大小为256位或更长的对称密码，以实现长期保护。NIST和其他标准将128位密钥的对称密码视为弱量子抵抗，192位对称密钥被视为中等量子抵抗。因此，对称密码并没有出现在NIST最新的后量子竞赛中。
所有提交的算法使用传统的对称密钥密码和散列作为其实现的一部分。当今世界上使用的最常见的对称密码是高级加密标准（AES），这也适用于抗量子密码。大多数抗量子密码都使用AES。
您还将看到SNOW 3G抗量子对称密码，尽管它远没有那么流行，也没有在任何提交的密码方案中使用。SNOW是一种基于字的同步流密码，由瑞典隆德大学的Thomas Johansson和Patrik Ekdahl开发。SNOW（版本1）、SNOW 2.0和SNOW 3G（适用于蜂窝网络使用）已在多个产品和应用中实现。您可以在这里获得更多关于SNOW和SNOW 3G的详细信息:www.gsma.com/aboutus/wp-content/uploads/2014/12/uea2designevaluation.pdf.
所有提交的密码也使用传统的散列，它像对称密钥加密一样不容易受到Shor算法的影响。大多数使用SHA-3（另一种NIST标准），尽管许多也使用SHA-3使用的流密码SHAKE。抗量子密码必须使用这些传统密码的适当的密钥长度来保持抗量子性，并且提交者使用的密钥大小通常相对于他们试图满足的特定实现的NIST安全级别有所变化。
表6.2显示了所有NIST Round 2算法名称及其加密类型。
所有这些类型的算法都被用于创建抗量子加密，下一节将对每种算法进行总结。
表6.2:NIST第二轮加密类型

抗量子非对称加密密码

抗量子密码是一种对运行基于量子算法的量子计算机不太敏感的密码，特别是Shor算法（或任何可以非常快地分解大素数方程的量子算法）。它们不使用基于量子的属性来击败攻击。尽管NIST的17个第二轮非对称加密候选方案中有一个或多个很可能成为最终的NIST联邦标准，但目前仍有几十种量子密码。NIST第二轮非对称PKE和KEM候选人（按字母顺序排列）如下：
BIKE
自行车
Classic McEliece
经典麦克利希
CRYSTALS-Kyber
CRYSTALS网络
FrodoKEM
弗罗多凯姆
HQC
LAC
紫胶
LEDAcrypt
LE DA密码
NewHope
新希望
NTRU
NTRU Prime
NTRU总理
NTS-KEM
ROLLO
罗洛
Round5
第5轮
RQC
SABER
军刀
SIKE
小溪
ThreeBears
三头熊
这17个密码中的一些是在第一轮比赛中分别提交的多个密码的组合，这些密码被组合成一个具有相似特征的单一密码家族。例如，HILA5和第2回合最终成为第5回合。
注：算法名称都是大写字母，或根据其创建者的原始用途而加首字母封顶。全大写的名字通常是缩写，代表较长的整字名字。
附注：这个列表绝不包括所有可能的强后量子非对称算法。许多现有的后量子加密算法（非对称和数字签名）没有提交，原因有很多，包括创建者不想放弃他们的算法供公众免费使用；许多算法在提交后受到攻击和破坏（其中22个）；许多提交论文薄弱或不符合NIST接受标准（如XMSS，LMS和BPQS）。最初提交第一轮审议但未提交第二轮审议的算法包括：大地震、CFPKM、紧凑型LWE、DAGS、DME、DRS、DualModeMS、Edon-K、徽标/R.EMBLEM、Giophantus、再次猜测、Gui、him-3、HK 17、KCL、Kindi、Lepton、利马、L火龙、Lotus、McNie、Mersenne-756839、pqNTRUSef、Odd曼哈顿、后量子RSA-加密、POST-量子RSA-签名、QC-MDPC KEM、RaCOSS、Ramster、RankSef、RLCE-KEM、RSRPI、TSRPI、TIPV、DSA和DSA。此外，还有几十个抗量子算法没有提交，包括GGH、XMSS和UOWHF。这些密码算法已经或可能被其他标准机构和国家所接受。

BIKE 
自行车

位翻转密钥封装（BIKE），是一个基于代码的KEM套件。由一个多国团队（主要来自法国，但参与者来自德国、以色列和美国）创建，它有三种不同的变体，分别称为BIKE-1、BIKE-2和BIKE-3。它基于McEliece加密、QC-MDPC（准循环中密度奇偶校验）码、CAKE、衔尾蛇（一种第一轮NIST的候选者，但没有单独进入第二轮）和临时密钥。临时密钥是为每次执行密钥建立过程而生成的加密密钥，而不是使用单个静态密钥。短暂密钥允许密码使用完全的前向保密性。
BIKE具有类似于基于格的密码系统的性能和密钥大小。在NIST要求的安全实现的第二轮开始时，密钥的范围从1988到4,110字节，公钥的范围从20,326到65,498字节，密文的范围从20,326到65,498字节。BIKE有一些最大的公钥和所有提交的候选项的密文，尽管它的密钥的大小得到了一个平均排名。一个相当有趣的特征，只有少数几个后量子密码拥有，那就是BIKE加密的数据有一个可识别的“签名”，可以被对手和安全控制用来识别和操纵它。你通常不能告诉什么密码是用来创建大多数加密，这使得任何攻击变得复杂。BIKE不是这样的。BIKE是Open Quantum Safe项目的一部分。
BIKE的更多信息，请访问：https://bikesuite.org/.

Classic McEliece
经典麦克利希

1978年，Robert J. McEliece发明了一种公钥密码，它经受了40多年的攻击。它是一种基于密码的密码，使用Goppa码。McEliece 1978年介绍McEliece公钥加密的论文可以在这里找到：https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF.
注意：你会经常看到相关的Niederreiter密码系统在与McEliece相同的地方被提及。Niederreiter密码系统的速度要快得多，可用于数字签名。
Original McEliece速度快（与RSA相比）并且抗量子，但需要较大的密钥大小（300 KB或更长，通常大于1 MB）。多年来，几个不同的团队试图修改它，以减少所需的密钥大小，但最终几乎所有的新实现被发现远远低于原来的安全性。
NIST提交团队，其中包括著名的密码学家和安全编码软件开发商丹尼尔·伯恩斯坦，成功地修改了McEliece，使其能够使用减小的密钥大小，同时保持量子耐零解密失败。对于NIST所需的安全实现的第二轮的开始，密钥的大小范围从6,452到13,892字节，公钥的大小范围从261,120到1,044,992字节，密文的大小范围从128到240字节。Classic McEliece的公钥大小是第二大的，仅次于NTS-KEM。两者都有最小的密文。虽然它们仍然比传统的公钥密码和它们的大多数后量子竞争大得多，但它们在使用今天的计算机和网络时非常容易管理。经典的McEliece有一个额外的好处，即具有非常小的密文大小，并且在基于硬件的实现中速度非常快。
有关Classic McEliece的更多信息，请访问https://classic.mceliece.org.
附注：如果您对密码学或编写安全代码感兴趣，Daniel J. Bernstein编写或发布的任何内容都会受到广泛的尊重。他发表过数百次演讲，写过几乎同样多的论文，开发过许多不同的、非常安全的、低bug数的程序。他发明了后量子密码学这个术语，并且是让世界其他地区了解这一即将到来的问题的早期领导者之一。鼓励读者访问他的个人网站：https://cr.yp.to.

CRYSTALS-Kyber
CRYSTALS网络

Crystal（代数格加密套件）包含两个基于格的加密原语:Kyber，一个CCA安全的KEM，和二锂，一个强EUF-CMA安全的数字签名算法。CRYSTALS-Kyber基于早期的ML WE加密问题，但使用正方形而非矩形矩阵作为公钥以及多项式环（https://en.wikipedia.org/wiki/Polynomial_ring)而不是整数。它具有良好的性能，可以很容易地缩放时，需要更大的密钥大小。
根据其跨国开发团队的说法，Kyber-512的安全保护大致相当于aes-128。（NIST安全级别分类1）,Kyber-768的安全性大致相当于AES-192（NIST安全级别分类3），而Kyber-1024的安全性大致相当于AES-256（美国国家标准技术研究院安全等级分类5）。对于NIST要求的安全实现的第二轮开始，密钥的大小范围从1,632到3,168字节，公钥的大小范围从800到1,568字节，密文的大小范围从736到1,568字节。CRYSTAL-Kyber一直排名平均到较小的密钥尺寸。它是开放量子安全计划的一部分。
有关晶体的更多信息，请参见https://pq-crystals.org/和https://pq-crystals.org/kyber/index.shtml.

FrodoKEM 
弗罗多凯姆

FrodoKEM是一个CCA安全和CPA安全的基于格的密码系统，它依赖于LWE问题求解来保护自己。与其他基于格子的模型（基于LWE环）相比，它具有稍大的密钥大小和较慢的性能。它有三个关键尺寸：
FrodoKEM-640，声称其安全性相当于AES-128
FrodoKEM-976，声称其安全性相当于AES-192
FrodoKEM-1344，声称其安全性相当于AES-256
在NIST要求的安全实现的第二轮开始，密钥的大小范围从19,888到43,088字节，公钥的大小范围从9,616到21,520字节，密文的大小范围从9,720到21,632字节。FrodoKEM是最大的公钥和密文大小之一。
FrodoKEM团队有很多来自微软和谷歌的成员。成员们采用了一个早期版本的FrodoCCS，这是一个短暂的密钥交换方案，并将其改进为IND-CCA-KEM。FrodoKEM是一个更简单的版本，它涉及的代码更少。这使得它可能更可靠和更有弹性的攻击。如果发现了一个缺陷，它可能会使它更容易修复。它是开放量子安全计划的一部分。
目前的FrodoKEM也是“恒定时间”作为构建。它不需要重新优化安全智慧，以防止某些类型的窃听攻击。恒定时间是一种密码保护属性，旨在减轻多种类型的侧信道定时攻击。简而言之，由于各种原因，许多密码和许多早期的密码实现引入了与密码所涉及的内容直接相关的CPU延迟（例如，计算密钥）。任何密码处理，改变处理时间的关系，一些检查变量的长度可能会创建一个可测量的和可预测的定时差，并给攻击者知识渊博的洞察力，否则秘密信息。这些信息可能会让攻击者做出假设，以加快他们的攻击。在密码学的世界里，这些类型的信息被称为“婴儿床”。你会在这里找到一个伟大的关于定时侧信道攻击的基本讨论：www.chosenplaintext.ca/articles/beginners-guide-constant-time-cryptography.html.
有关FrodoKEM的更多信息，请参见https://frodokem.org/.
注：比利时鲁汶恩智浦半导体公司的密码学研究员Joppe W. Bos是三种后量子密码的提交者：FrodoKEM、CRYSTALS-Kyber和NewHope。

HQC 

HQC（Hamming Quasi-Cyclic）是一种基于随机准循环码难以解码的公钥加密方案，它使用了带有重复码的Bose-Chaudhuri-Hocquenghem（BCH）码。BCH代码发明于1959年和1960年，它被认为是简单的控制什么“错误”，他们纠正，从而使其易于解码时，你有正确的钥匙。BCH代码已被广泛应用于CD、DVD、条形码和计算机存储设备几十年。即使HQC使用“易于解码”的BCH代码，它也受到“非零”的限制“（但仍然非常罕见的）解密失败。
HQC有2的负128次方的机会，任何特定的解密轮将不会导致原始明文内容。计算机，一般来说，有许多其他更常见的错误，有一个更高的机会发生，我们接受使用这些计算机就好了。失败将意味着它可能需要额外的解密轮才能成功，但这些额外的轮将发生得非常快，几乎没有人会注意到。但是概率是非零的，所以我们注意到了。密码学家必须遵守严格的报告标准。
对于所有NIST所需的安全实现，HQC的密钥大小为40字节（与其他三个提交的密钥大小并列为倒数第二小）。对于NIST要求的安全实现的第二轮开始，HQC的公钥范围从3,125到8,897字节，密文范围从6,234到17,777字节。像BIKE一样，HQC具有可用于识别HQC加密流量的标记，并且它使用临时密钥来实现完美的前向保密。HQC团队由多个国家组成，其中许多人向NIST竞赛提交了其他算法（例如，法国人Philippe Gaborit也参与了BIKE、HQC、RQC和ROLLO）。
有关HQC的更多信息，请参阅https://pqc-hqc.org.