假设区块链在大规模的量子电脑攻击下，是否能抵挡住其攻势，本文将探讨在量子电脑威胁下，区块链可能面临的挑战以及应对方法。本文源自 BTQ 所着文章 《Blockchain security in the quantum era》，由 动区编辑部 整理。
（前情提要：浅析量子密码学与加密技术：更强大的安全系统 ）
（背景补充：量子物理专栏｜谈谈「量子掏金热」与泡沫 ）
本文目录
区块链通常使用公开金钥密码系统（public-key cryptography），而现今大部分常用的系统皆建立在「整数因数分解（integer factorization）」和「离散对数问题（discrete logarithm problems）」这两个数学问题之上，然而，在大规模的量子电脑攻击之下，这两者都会被破解。在此系列文章中，我们将探讨在量子电脑威胁下可能的挑战和应对的方法。
传统电脑与量子电脑
早在半个世纪前，我们就已经开始使用传统电脑。从树莓派到全世界最强大的超级电脑，我们所有的设备都是来自於古典电脑计算典范（classical computing paradigm），且这个计算典范是建立在二进位状态之上。而量子电脑是一种迅速崛起的技术，其利用量子力学来解决传统电脑难以解决的问题。
从计算的角度来说，传统电脑和量子电脑的主要区别在於讯息处理的方式。传统电脑将讯息储存在二进位位元中，也就是每个位元只能处於两种状态中的一种（例如：开／关，高电压／低电压）。量子电脑将讯息储存在量子位元（或称量子比特， 即 qubits）中，讯息是以叠加态（superposition state）存在，每种状态都有自己的机率幅（probability amplitude）。美国理论电脑科学家 Scott Aaronson 曾说：
「自然界不是由机率描述的（机率总是正数），而是可以由正数、负数或甚至是复数的振幅描述的。」
量子计算的特殊之处，就是在将机率理论推广、允许负数，因为将两个非零机率相加可以导致零机率，从而产生一种被称为量子干涉的效应。多个量子位元群可以创造出高度复杂的多维空间，使得量子电脑能够解决传统电脑无法解决的问题。
何谓密码系统中的「安全」？
我们通常使用以下两种框架用来评估密码系统的安全性：
然而，讯息论安全实际上非常难实现，所以大多数现代密码协议都在对手的计算能力做了一定的假设。为了更好地理解计算安全框架中的这些假设，让我们转向计算复杂度理论来看看复杂度类别。
我们用 「P」表示可以在传统电脑上有效解决的问题，「BQP」 表示可以在量子电脑上有效解决的问题，而 “NP” 表示可以在传统电脑上有效验证（但不一定可以解决）的问题。 过去数十年，许多电脑科学家和数学家对计算复杂度进行研究，并建立了密码演算法之安全性分析的理论基础，每个问题类别都由其是否可以被传统电脑或量子电脑有效地解决或验证来定义。现在，我们继续讨论这些复杂度类别与计算安全性的关联。
在 「P」中的问题已知可以由传统电脑有效解决，无论是从计算安全或讯息论安全的角度，这些问题都不会有太多的帮助，因此如果要用来保护敏感资讯，我们会倾向选择那些不在「P」中的问题。如果我们从 「NP」 的问题中选择，可能仍然需要依赖计算能力上的假设，即我们假设对手不会在计算效率上有重大突破。所以，如果所选择的问题不在 「P」中，但在 「BQP」 内，那麽这样的演算法在量子时代可能会不安全，而这就是我们目前所处的情况。
在数十年前，当我们选择各种难题作为密码系统的假设时，我们选择了不在 「P」中的难题，但从今日的观点，这些难题仍在 「BQP」 内，这表示我们当时并不了解量子电脑的计算能力，或对「如何实现量子电脑」根本没有头绪，所以从当时的计算安全角度来看，这些难题依旧可以提供足够的安全性。事实上，量子复杂度理论在 1992 年开始被提出，而 Shor 演算法（可有效破解椭圆曲线非对称密码系统的演算法）则是在 1994 年才出现的。意外的是，早在 1978 年，McEliece 就提出了一套非对称密码系统，它是基於一般线性错误更正码的解码困难度，此问题是 NP-hard，直至今日仍被认为不在 「BQP」 中，故能抵抗量子攻击。
区块链中的公钥密码系统
公钥密码系统是基於公钥和私钥的一对密钥。密钥对的生成是基於某些数学问题的难解性，因此私钥计算出公钥很容易，但反方向计算却很难。公钥会被传送到区块链上，私钥则必须被保管起来，因为私钥代表了区块链地址的所有权和该地址所有资产的取得权。这种机制也形成了区块链交易中至关重要的「数位签章」。每个链上的交易都由私钥签署，以验证发送者的合法性。签署和验证的流程如下：
每一个区块的每一个交易都需要进行数位签章，而目前的数位签章演算法大多基於 ECDLP（elliptic curve discrete logarithm problem，椭圆曲线离散对数问题）。ECDLP 已知可以被量子电脑有效解决，因此我们需要找到新的抗量子电脑攻击的演算法。
量子攻击如何破坏公钥密码系统
区块链上的每个交易都需要使用私钥签署产生数位签章，後由对应的公钥来验证交易的合法性。不幸的是，公钥密码系统的安全性是基於椭圆曲线离散对数问题（ECDLP）的困难度，而 Shor 演算法已提供了一个有效解决的量子演算法，也就是说，给定一组公钥，一个够强的量子电脑可以有效地计算出和它关联的私钥，如此公钥密码系统的游戏规则将完全被破坏。典型的量子攻击可能会经过以下过程：
区块链的记帐方法大致分成两种架构：UTXO（如比特币区块链） 和 Account-based（如以太坊）。简单来说，前者比较像是现金交易，使用者可以同时从钱包动用多个钱堆进行交易；而後者比较像是银行帐户，一次只能进行一笔交易，交易完成才会进行下一笔。量子攻击对於这两种架构的影响如下：
现在我们已经了解量子攻击的原因、过程和结果，在下一篇文章中，我们将讨论可抵抗量子攻击的演算法。
下篇文章：BTQ研究》後量子时代的区块链资安（下）：更强的加密？浅谈NIST後量子密码标准
📍相关报导📍
深度｜ConsenSys领军的「Linea」：突破ZK Rollup限制、EVM完全相容
加密货币被破解？美国国家安全局 NSA 正在开发「量子密码学」，抵御量子电脑造成的资安问题
量子物理专栏｜论 Google 的量子霸权实验 ( Quantum Supermacy )
