比特币的量子攻击及其防范

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文标题：
《Quantum attacks on Bitcoin, and how to protect against them》
---
作者：
Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, Marco
  Tomamichel
---
最新提交年份：
2017
---
英文摘要：
  The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum computer. One particular area at risk are cryptocurrencies, a market currently worth over 150 billion USD. We investigate the risk of Bitcoin, and other cryptocurrencies, to attacks by quantum computers. We find that the proof-of-work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years, mainly because specialized ASIC miners are extremely fast compared to the estimated clock speed of near-term quantum computers. On the other hand, the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates. We analyze an alternative proof-of-work called Momentum, based on finding collisions in a hash function, that is even more resistant to speedup by a quantum computer. We also review the available post-quantum signature schemes to see which one would best meet the security and efficiency requirements of blockchain applications.
---
中文摘要：
当今用于保护互联网和金融交易安全的关键密码协议都容易受到足够大的量子计算机开发的攻击。面临风险的一个特定领域是加密货币，该市场目前价值超过1500亿美元。我们调查比特币和其他加密货币受到量子计算机攻击的风险。我们发现，比特币所使用的工作证明相对而言，在未来10年内，量子计算机的大幅加速是难以实现的，这主要是因为专用ASIC矿工与近期量子计算机的估计时钟速度相比，速度非常快。另一方面，比特币使用的椭圆曲线签名方案风险更大，最乐观的估计是，最早可能在2027年被量子计算机完全破坏。我们分析了另一种称为动量的工作证明，其基础是在哈希函数中发现碰撞，这种碰撞更能抵抗量子计算机的加速。我们还审查了可用的后量子签名方案，以确定哪种方案最能满足区块链应用程序的安全性和效率要求。
---
分类信息：

一级分类：Physics        物理学
二级分类：Quantum Physics        量子物理学
分类描述：Description coming soon
描述即将到来
--
一级分类：Quantitative Finance        数量金融学
二级分类：General Finance        一般财务
分类描述：Development of general quantitative methodologies with applications in finance
通用定量方法的发展及其在金融中的应用
--

---
PDF下载：
--> Quantum_attacks_on_Bitcoin,_and_how_to_protect_against_them.pdf (2.56 MB)

2022-6-1 15:25:32 上传

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：比特币 Quantitative Applications Transactions Requirements

比特币的量子攻击，以及如何防范Themdelah Aggarwal，1，2 Avin K.Brennen，TroyLee，4，2 Miklos Santha，5，2和Marco Tomachels National University of Singapore，National University of Singapore，Macquarie University，Sydney，AustraliaSPMS，Nanyang Technology University，SingaporeCNRS，IRIF，Universit\'e Paris Diderot，澳大利亚悉尼法国理工大学（FranceUniversity of Technology Sydney，Australia）当今用于保护互联网和金融交易安全的关键密码协议都容易受到大型量子计算机开发的攻击。面临风险的一个特定领域是加密货币，该市场目前价值超过1500亿美元。我们调查比特币和其他加密货币受到量子计算机攻击的风险。我们发现，比特币所使用的工作证明相对而言，在未来10年内，量子计算机的大幅加速是难以实现的，这主要是因为专用ASIC矿工的速度与近期量子计算机的估计时钟速度相比非常快。另一方面，比特币使用的椭圆曲线签名方案风险更大，最乐观的估计是，最早在2027年，量子计算机可能会完全破坏该方案。我们分析了另一种称为动量的工作证明，该证明基于哈希函数中发现的碰撞，它甚至更能抵抗量子计算机的加速。我们还审查了可用的后量子签名方案，以确定哪种方案最能满足区块链应用程序的安全性和效率要求。一、 简介比特币是一种由密码学保护的分散数字货币。

自2008年中田聪（Satoshi Nakamato）[Nak09]开发以来，比特币已被证明是一种非常成功和安全的系统，并在目前价值超过1500亿美元的市场上激发了数百种其他加密货币和区块链技术的发展。比特币的安全性源于其协议的几个不同特征。第一个是将交易写入比特币数字账本所需的工作证明。这样做所需的工作是防止拥有网络计算能力不足50%的恶意方创建替代交易历史。第二种是用于授权交易的加密签名。比特币目前使用基于椭圆曲线的签名方案。量子计算机的未来发展对目前用于保护互联网和金融交易的几乎所有加密技术以及比特币构成了严重威胁。本文全面分析了比特币对量子攻击的脆弱性。我们发现，比特币所使用的工作证明相对而言，在未来10年内不会受到量子计算机的实质速度的影响，这主要是因为与短期量子计算机的估计时钟速度相比，专用ASICminers的速度非常快。这意味着交易一旦进入区块链，即使在量子计算机的存在下，也会受到相对保护。众所周知，比特币使用的椭圆曲线签名方案被Shor\'salgorithm[Sho99]在计算离散对数时所打破。

我们准确地分析了从未来量子计算机上发布的公钥中获得密钥可能需要多长时间。这在比特币环境中至关重要，因为这种攻击的主要窗口是从事务广播开始，直到事务被处理成区块链上的一个块，后面有几个块。据我们最乐观的估计，早在2027年，可能就有一台quantumcomputer可以在比特币所用的10分钟内破解椭圆曲线签名方案。我们还提出了一些可以采取的对策，以确保比特币免受量子攻击。我们分析了另一种称为动量（Momentum）[Lar14]的工作证明方案，该方案基于散列函数中的发现碰撞，并表明其允许的量子加速比比特币使用的工作证明更少。我们还回顾了被认为是量子安全的其他签名方案。二、区块链基础在本节中，我们对比特币的工作原理进行了基本概述，以便我们在描述可能的量子攻击时可以参考协议的特定部分。我们将把这一讨论保持在抽象的层次上，因为许多原则同样适用于与比特币具有相同基本结构的其他加密货币。所有比特币交易都存储在称为区块链的公共分类账中。单个事务被捆绑到块中，块中的所有事务都被视为同时发生。通过将这些事务置于链中，对其进行时间排序。链中的每个块（第一个块或genesis块除外）都有一个指向其前面的块的指针，其形式为前一个块头的哈希。矿工们将石块添加到链条上。矿工可以将未处理的事务捆绑到一个块中，并通过工作证明（PoW）将其添加到链中。

比特币和许多其他货币都使用了Adam Back开发的名为Hashcash[Bac02]的PoW。Hashcash PoW是为了找到一个格式良好的块头，使得h（头）≤ t、 其中h是加密安全哈希函数，header是块头。格式良好的头包含块的摘要信息，例如从块中的事务派生的哈希、前一个块头的哈希、时间戳，以及可以自由选择的所谓nonce、32位寄存器。可在表I中找到块的图示。参数t是一个目标值，可以更改以调整PoW的难度。在比特币中，该参数每2016个区块动态调整一次，这样网络平均需要大约10分钟来解决PoW。在比特币中，用于工作证明的哈希函数是SHA256的两个连续应用程序：{0，1}*→ {0，1}哈希函数，即h（·）=SHA256（SHA256（·））。当h的范围为2时，需要尝试用参数t完成哈希现金工作证明的预期哈希数为2/t。比特币工作证明通常是根据难度D（其中D=2/t）来指定的，而不是t。这是完成工作证明所需的预期哈希数除以2（可用的nonce数）。换句话说，困难是事务版本0x2000012上一个块头哈希00的Merkle树哈希根的预期变化数。0d OFF f7669865430b。Merkle根730d68233e25bec2。时间戳2017-08-07 02:12:18困难860221984436.22当前941660394事务1事务2。。。表I.块的图解。

顶部的数据构成块标题。在对块头进行哈希运算时，以及在尝试对事务和时间戳进行预处理时，需要尝试的事务和时间戳所有nonce。矿工们可以随意将未处理的交易捆绑到一个区块中，并分配大量比特币以成功完成PoW任务。“生成”交易支付挖掘奖励也是块中包含的一项交易，确保不同的人将在不相交的块头上搜索良好的哈希预映像。一旦矿工找到一个收割台，将其固定在h（收割台）上≤ t、 他们将此消息通知网络，并将块添加到链中。请注意，很容易验证声明的标题是否满足PoW条件-它只需要对哈希函数进行一次评估。PoW的目的是使一方不能单方面操纵区块链，例如，为了加倍支出。区块链是有可能工作的，但在任何时候，协议都规定矿工应该在当前最长的分叉上工作。一旦一个区块在最长链中有k多个区块紧随其后，想要创建一个不包括该区块的最长链的一方就必须在落后k个区块的情况下赢得PoWrace。如果该党控制的网络计算能力远远少于一半，那么随着k的增长，这种情况就变得非常不可能了。在比特币中，一笔交易通常被认为是安全的，因为它后面有6个区块。我们将在第三节A中看到的第一个问题是，量子计算机在执行hashcash PoW时会有什么优势，以及它是否可以单方面“从后面来”操纵区块链。比特币的第二个重要方面是交易的形式。当Bob想将比特币发送给Alice时，Alice首先创建（理想的新鲜）私有公钥对。

公钥被散列以创建地址。这个地址是Alice提供给Bob的，作为发送比特币的目的地。比特币使用公钥哈希作为地址，而不是公钥，这不是出于安全原因，只是为了节省空间。正如我们稍后看到的，这种设计选择确实会对量子安全性产生影响。要将比特币发送给Alice，Bob还必须指向区块链上的交易，比特币被发送到他控制的地址。这些referencedtransactions收到的比特币总和必须至少等于Bob希望发送给Alice的比特币金额。Bob通过声明每个地址对应的公钥，并使用该地址对应的私钥在消息上签名，表示他正在将这些比特币送给Alice，从而证明他拥有这些地址。在比特币协议的早期版本中，公钥可以用作地址。三、 比特币的量子攻击。攻击比特币工作证明在本节中，我们研究量子计算机在执行比特币使用的hashcash PoW时所具有的优势。我们的发现可以总结如下：使用Grover搜索[Gro96]，量子计算机可以通过执行比经典计算机所需的二次哈希更少的哈希来执行hashcash PoW。然而，当前用于执行hashcash-PoW的专用ASIC硬件的极端速度，加上当前量子体系结构的预测门速度要慢得多，在当前困难的水平上，基本上否定了这种二次加速，使量子计算机没有任何优势。

未来量子技术的改进，使门速度达到100GHz，可能使量子计算机解决PoW的速度比当前技术快100倍左右。然而，这样的发展在未来十年内是不可能的，在这一点上，经典硬件可能会快得多，量子技术可能会如此广泛，以至于没有一个启用量子的代理可以主宰PoW问题。我们现在详细讨论这些结果。回想一下，比特币PoW任务是查找有效的块头，例如h（头）≤ t、 其中h（·）=SHA256（SHA256（·））。区块链的安全性取决于没有一个代理能够以大于50%的概率首先解决PoW任务。我们将研究在执行这项任务时，与一台量子计算机相匹配所需的经典计算能力。我们将在随机oracle模型[BR93]中工作，特别是假设pr[h（header）≤ t] =t/2其中，概率统一适用于所有格式良好的块头，这些块头可以在任何给定时间使用池中可用的事务创建（此类格式良好的块头可以通过改变nonce、块中包含的事务以及头的时间戳的最小重要位来找到）。在经典计算机上，为了找到散列值最多为t的块头和none的预期数量为D×2，其中D是由D=2/t定义的散列数。对于随机oracle模型中的量子计算机，我们可以将注意力限制在使用Grover算法解算PoW任务的通用量子方法上【Gro96】。根据Grover的算法，在一个包含N个项目的数据库中搜索一个标记的项目可以用(√N） 许多对数据库的查询（而任何经典计算机都需要Ohm（N） 完成相同任务的查询）。设N=2be为以下h范围的大小。

根据我们的假设，在概率至少为0.9999的情况下，一个由10·N/t组成的随机集，许多块头将至少包含哈希最多为t的tone元素。我们可以将一些确定性函数g映射={0，1}dlog（10·N/t）固定到不同的格式良好的块头。我们还定义了一个函数fw，该函数确定块头是“好”还是notf（x）=如果h（g（x）），则为0>如果h（g（x）），则为t1≤ t、 量子计算机可以在输入的叠加上计算f，即执行映射xx∈Sαx | xi→Xx号∈S(-1） f（x）αx | xi。根据区块链。信息，2017年8月8日，哈希难度为D=860·10，目标为2184。4此操作的每个应用程序都称为oracle调用。使用Grover算法，aquantum算法可以通过计算#O=πp10·N/t=π2来搜索s以找到一个好的块头√10·D oracle呼叫。即使事先不知道解的数量，即使不存在解，Grover算法也可以适应这种缩放运行【BBHT98】。虽然oracle调用的数量决定了需要执行的哈希数，但在计算每个哈希、构造适当的块头和进行量子错误更正时会产生额外的开销。现在，我们通过两种方式分析这些因素，以确定对运行时间的更现实的估计。首先，我们基于一个经过充分研究的带有误差校正的通用量子计算机模型来估计运行时间。在经典计算机上，哈希函数（如SHA256）使用基本布尔门操作，而在量子计算机上，这些基本布尔门被转换为可逆逻辑量子门，这会带来一些开销。SHA256协议中总共有64轮哈希运算，每轮都可以使用带有683到ffoli量子门的优化电路完成【PRS15】。

大多数量子纠错码使用T门而不是F门作为代表性的耗时门，仔细分析执行SHA256函数调用的成本以及Grover算法中使用的平均值的反转，发现一次oracle调用的总T门计数为474168[SFL+13]。在该电路分解中，T门只能由大约三个因数并联。量子计算机需要额外的开销来执行纠错。在决定一个好的量子纠错码时，需要考虑各种权衡因素：对特定物理错误模型的容忍度、子程序的通用性、使用的量子比特数、逻辑门复杂性以及错误综合征和反馈的经典处理量。采用具有相对高容错错误阈值和局部综合征测量优点的表面码，我们可以采用文献[SFL+13]中的分析来估计量子算法的总运行时间。运行Grover算法并成功挖掘块所需的时间为τ=#O×#G/s=π2√10·D×#G/s，其中#G是一次oracle调用所需的周期数，s是量子计算机时钟速度。使用表面代码，其中主要的时间成本是提取魔术状态来实现T门，一个结果是#G=297784×cτ（D，pg），其中第一个因素包括逻辑T门深度，用于调用SHA256函数，两次按比特币PoW的要求调用，两次使电路可逆，以及关于平均值的反转。第二个因素cτ是量子误差校正所需的时间开销因素。它统计每个逻辑T门的时钟周期数，并且是难度和物理门错误率pg的函数。