在上一篇文章中，我们了解到量子电脑攻击是如何发生的，在这篇文章中，我们将讨论後量子密码学标准。本文源自 BTQ 所着文章 《Blockchain security in the quantum era》，由 动区编辑部 整理。
（前情提要：BTQ研究》後量子时代的区块链资安(上)：量子攻击将发生？密码学面临的困境 ）
（背景补充：浅析量子密码学与加密技术：更强大的安全系统 ）
本文目录
後量子密码学的标准化
美国国家标准技术研究院（NIST）是一个隶属於美国商务部（United States Department of Commerce）的机构，该机构制定了保护敏感数据和关键资料的标准。任何为美国国防部（DoD）、联邦总务署（GSA）、美国国家航空暨太空总署（NASA）以及其他政府机构处理、储存或传输敏感讯息的人都必须遵守 NIST 的标准，因此大家普遍认同 NIST 为全世界制定密码学标准的机构。
从 2016 年起，NIST 宣布开始一系列的後量子密码学（Post-quantum crypography）竞赛，过程中徵求、评估并标准化抗量子攻击的公钥加密演算法和数位签章演算法，确保即使在量子电脑出现之後，这些演算法仍然可以保护敏感资讯。等待了近六年後，在 2022 年 7 月，NIST 正式宣布了这个後量子密码学竞赛第三轮的演算法标准。以下我们会把重点放在後量子数位签章演算法。
後量子数位签章演算法
可以实现後量子安全数位签章的密码演算法可以分为以下几类：
在这三者之中，格密码学因其弹性和归约安全性（Reductionist security），在近年来受到了许多关注。密码系统的安全性通常是基於「某些数学问题是困难的」这个假设上，以及一个「如果攻击者可以破解该密码系统，那麽我们可以把这种攻击转变为一种解决底层难题的有效演算法」的归约性证明（reductionist proof）。另外，许多格密码系统都依赖於所谓的「可归约最坏情况到平均情况」的难题。这大致的意思是，这个难题在「高维度中的一般实例」和在「低维度中最难的实例」的困难度是一样的。因此，我们可以对这些格密码系统的安全性有更高的信心，因为我们有更强的证据证明某个难题在平均情况下确实是困难的。
杂凑签章的实现方法是将安全性假设最小化。杂凑函数在现代密码学中是不可或缺的，没有它，区块链就不可能实现。就算假设我们只有一个安全的杂凑函数，那麽我们仍然可以构建一个数位签章，大致过程是这样：首先，我们使用一次性杂凑签章，例如 Lamport’s signature 或 Winternitz signature，作为实际签名和验证讯息的基础。这些一次性杂凑签章的公钥和私钥最多只可以用来签名和验证一次，所以我们还需要一种有效的方法将许多这样的密钥对捆绑在一起，以实现安全和实用的数位签章。这里我们使用 Merkle tree 的概念来组合一次性公钥，并使用 Merkle root 作为我们的公钥。每次我们使用一次性密钥对签名时，除了发送签章本身，我们还需要将验证路径（authentication path），也就是从 Merkle root （树根）到此密钥对（叶子）的路径一并发送出去，以便验证者可以确认该签名确实来自於正确的公钥。当然，我们也需要纪录哪些私钥已经被使用，例如 XMSS in RFC8391 就是一种已被标准化的有状态杂凑签章（stateful hash-based signature）。
还有一种多变量密码学，其安全性主要基於解决多变量多项式方程式（multivariate polynomial equations）的困难性，以及其他例如判定两个多项式是否同构（isomorphic）的 IP 问题。在用於数位签章时，多变量密码系统的签章大小相对较小，但公钥相对较大，这使得它应用范围较小，比较适合系统中只有少数公钥这样的场景。在区块链中，因为大多数公钥只使用一次，所以并不适合这样的签章方式。然而，NIST 似乎仍然对多变量密码学非常感兴趣，因此也把它纳入在後量子密码学标准的名单中。
接下来，我们一一讨论 NIST 选择进行标准化的三种数位签章。
後量子密码学应用於区块链的困境
为了使区块链在下一个世代仍保持安全和可行，我们必须设法过渡到後量子安全标准，不过，这并非想像中容易，因为相较现行密码学标准，後量子数位签章演算法的公钥和签章大小都增加了许多。在 NIST 认证的数位签章演算法中，即使是最小的 Falcon 公钥（897 B）也比现行的 ECDSA （32 B）大了 28 倍以上。如果比特币和以太坊今天采用後量子密码学安全标准，两条链的大小都将会爆炸。即使用最节省空间的 NIST 後量子数位签章演算法，公钥和数位签章在比特币和以太坊中将分别多消耗 21.2 倍和 24.3 倍的空间，它们各自的帐本的大小将增加 2.2 倍和 2.22 倍，遑论使用其他的後量子数位签章演算法。这不仅影响交易速度、gas 费用 ，也可能影响整个网路的去中心化。升级区块链安全并不只是替换演算法那麽简单，我们必须设计一种方案让安全性与效率达成平衡。
後量子区块链
目前有许多团队正在研究中长期的解决方案，要将现今的区块链转换为使用後量子密码学的区块链。像是 Algorand 就使用 NIST 认证的 Falcon 签章在他们的状态证明中，使 Algorand 链能够与其他链进行相互作用，也防止未来量子电脑够成熟时可能可以回溯并产生新分叉链的问题。以太坊研究团队的成员们也开发了一种多签章方案，将多个独立的签章压缩成一个短签章，从而同时验证所有签章。当有多个验证者需要对进行区块同步的情况下，这种技术尤其有用。另外，BTQ 也已经完成 Falcon 签章替换以太坊 ECDSA 的测试链，并加入了概念类似於前述以太坊的 PQScale 聚合签章技术（aggregate signature），已达到效率和安全的平衡。
总结
量子电脑对现今的密码系统带来了威胁，而为了保护数位资产和区块链系统，我们极需找到新的密码演算法和数位签章演算法。区块链系统的创新和发展需要与密码技术的发展并行，以确保未来在量子电脑真正问世并普及时，我们所使用的区块链与所拥有的资产仍然能维持安全。
📍相关报导📍
量子物理专栏｜论 Google 的量子霸权实验 ( Quantum Supermacy )
量子物理专栏｜谈谈「量子掏金热」与泡沫
100%安全跨链？详解跨链代币标准：xERC20
