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

根据Grover搜索的最优性[BBBV97]，我们知道我们必须至少执行√m许多测试都是为了找到一个好的H。因为测试一个H是否好需要时间| S | 2/3，所以总运行时间至少为√m | S | 2/3。由于经典的运行时间是m | S |，我们看到，与比特币目前的工作证明不同的是，如果S大于常量大小，量子计算机就无法实现二次优势。特别是，自√m | S | 2/3也最小化，当S=qn+`t时，即使最快的量子算法的运行时间也至少为T2/3，这大大大于T1/2。B、 后量子签名方案综述文献中提出了许多量子安全公钥签名方案。其中一些示例是基于哈希的签名方案（LMS[LM95]、XMSS[BDH11]、括约肌[BHH+15]、NSW[NSW05]）、基于代码的方案（CFS[CFS01]、类型名称安全级别（bits）PK长度（kb）Sig。长度（kb）PK+Sig。长度（kb）I.1 GPV 100 300 240 540I。2 LYU 100 65 103 168I。3福利斯128 7 5 12我。4二锂138 11.8 21.6 33.4II。1彩虹160 305 0.244 305III。1 LMS 128 0.448 20 20.5III。2 XMSS 128 0.544 20 20.5III。3括约肌128 8 328 336III。4新南威尔士州128 0.256 36 36 IV。1 CFS 83 9216 0.1 9216IV。2石英80 568 0.128 568表二。比较后量子签名方案的公钥（PK）和签名长度（kb）。给出的安全级别是针对经典攻击的。类型I基于晶格，类型II基于多元多项式，类型III基于哈希，类型IV基于代码。QUARTZ[PCG01]、基于多元多项式的方案（RAINBOW[DS05]）和基于晶格的方案（GPV[GPV08]、LYU[Lyu12]、BLISS[DDLL13]、DILITHIUM[DLL+17]、NTRU[MBDG14]）。每种密码系统都有不同程度的效率。

有关签名大小和密钥大小的比较，请参见表II。在区块链上下文中，签名方案最重要的参数是签名和公钥长度，因为这些必须以一定的容量存储以完全验证交易，以及验证签名的时间。看看表II，关于签名和公钥长度的总和，唯一合理的选择是哈希和基于晶格的方案。基于哈希的方案（如XMS）具有可证明安全性的优点，至少所选哈希函数的行为类似于随机oracle。针对这些方案的一般量子攻击是使用Grover算法，这意味着它们的量子安全级别是经典安全级别的一半。相比之下，138位经典安全级别下针对二锂的最著名量子攻击需要时间2。因此，在相同的量子安全级别上，基于晶格的方案在signatureplus公钥长度方面具有一定的优势。虽然基于格的方案BLISS在表2中的所有方案中具有最短的签名和公钥长度之和，但在实践中有一些理由不选择BLISS。BLISS的安全性依赖于NTRU问题的硬度，并且假设解决这个问题相当于在所谓的NTRU格中找到一个短向量。最近[KF17]表明，这种假设可能过于乐观，至少对于大参数而言是如此。此外，以前基于NTRU的签名方案也曾遭到过攻击【NR06，DN12】。也许最致命的是，BLISS很难以安全的方式实现，因为它很容易受到侧通道攻击。Pessl等人以这种方式攻击了BLISS的生产级strongSwanimplementation。

[PBY17]表示，在观察了大约6000代签名后，签名密钥可以恢复。函数CalculateFactoryResources（pg，nT） 迭代FactoryTool中的错误更正层←nT公司 （未修正）误差容限I← 0当ptol<10pgdoi时← i+1 添加layerdi← 明尼苏达州∈ 编号：192d·（100pg）d+1≥托洛 此图层中的代码距离← （ptol） 提高了容错能力← iτ← nT·10Playersi=1di 总时钟周期（仅计数T门）Qfactory← 50（层）·15层-1. factoryreturn（τ，Qfactory）end Function CalculateCircuitResources（pg，nC，nL）dC的总物理量子位← 明尼苏达州∈ N：（80pg）d+1≥nCo公司 电路（单层）返回Q电路的代码距离← 3.125nLdC circuitend函数的总物理量子位表III.计算量子攻击的空间和时间资源的算法。输入为pg，物理门错误率；nC，逻辑电路中的辅助门总数；nT，逻辑电路中T门的总数；和nL，逻辑量子位的数量。输出为τ，以时钟周期数表示的时间成本；nQ=Qcircuit+Qfactory，用于计算的物理量子位数，包括状态蒸馏。附录A：估算量子攻击的纠错资源开销我们描述了如何计算量子纠错的开销因子，以获得区块链和数字签名量子攻击的资源成本。该方法遵循参考文献中给出的分析。【FMMC12，MDMG+16】。我们首先确定算法中分别需要的T门和C门的数量。表III给出了计算开销的伪代码。

对于区块链攻击nL=2402量子位，这些值不=297784×π2√10·D，nC=29.4×nT。对于nL=2334量子位的数字签名攻击，值为1.28×10，nC=20×nT。如果我们展望未来几年，我们可以推测量子计算机技术可能会有哪些改进。如果我们假设一个量子纠错码支持量子门和非量子门，因此蒸馏过程不会减慢，并且以无需测量的方式进行，因此不会出现经典的错误综合征处理每个T门的量子门数量的系数20是基于T门的T门深度1表示的构造[选择13]。则一个oracle调用所需的周期数仅由电路深度2142094决定。这是基于如下计算的整体回路深度。oracle调用两个对SHA256哈希函数的调用，执行两次，一次用于计算，另一次用于解压。每个哈希的可逆电路深度为528768。类似地，使用了两个多控制相位门，一个用于求平均值，另一个用于函数调用，每个门的电路深度为13511，总深度为4×528768+2×13511=2142094（这些数字来自[SFL+13]，但可以进一步优化）。然后接受空间和物理量子位数方面的潜在开销，但假设纠错或非有效门蒸馏没有时间惩罚，这意味着提高了有效哈希率Hqc=0.04×s√D、 这要快得多。对于超导电路，超快几何相位门在~ 50 GHz，基本上受到微波谐振器频率的限制【RBW+12】。

使用上述非常乐观的假设，在D=10时，有效哈希率将为hQC=2.0×10/s。附录B：模拟比特币网络哈希率的发展，很难从区块链中获取整个比特币网络中每秒的哈希总数。信息。图5（a）中的数据点是1月1日（2012-2015）以及1月1日和7月1日（2016-2017）的哈希率。两条虚线对应于乐观和不太乐观的外推假设。乐观的外推假设目前的增长在五年内呈指数增长，然后随着充分优化的ASIC比特币矿商的市场饱和，饱和为线性增长。不太乐观的假设假设是以目前的速度呈线性增长。通过对比特币网络哈希率的外推，我们可以确定其难度是时间的函数。在10分钟（600秒）内查找块所需的预期哈希数由速率（t）·600给出，其中速率（t）是图5（a）中显示的总哈希速率。因此，比特币哈希难度计算为D（t）=速率（t）·600·2-32对于上述两种情况。在图5（b）中，我们将其与区块链的值进行比较。2015-2017年1月1日信息。附录C：量子计算机发展建模我们必须对量子技术发展的几个方面进行建模。由于在开发的早期阶段，可用的数据点很少，因此我们的估计中必然存在很多不确定性。因此，我们给出了两个不同的测试，一个对发展速度持乐观态度，另一个则相当悲观。

尽管如此，这些预测应被视为非常粗略的估计，可能需要在未来进行调整。首先，我们需要对任何时间点可用的量子比特数做出假设。由于我们只关注固态超导的实现，所以只有少数数据点可用。我们假设，在不久的将来，可用的量子比特数将呈指数级增长。乐观的假设是，数字将每10个月翻一番，而不太乐观的假设是，比特币网络中的数字每202015 2020 2025 2030 2035 204010141016101810201022哈希每秒翻一番（a）2015 2020 2025 2030 2035 204010111012101310141015哈希困难（b）图5。预测比特币网络的哈希率（以每秒哈希数为单位）和哈希难度随时间的变化。月。图6（a）绘制了这两种外推。数据点如下表所示：量子比特数年份参考2 2013年【CGC+13】5 2014年【BKM+14】3 2014年【CGM+14】5 2016年IBM16 2017年IBM20 2017年【Goo】49 2018年【Goo】我们预测量子门频率在未来几年呈指数增长。这假设经典的控制电路在这个频率下能够足够快地控制量子门。几年后，增长速度明显放缓，因为需要更大的经典控制电路来进一步加速量子门。我们将量子门频率分别限制在50 GHz（乐观情况下）或5 GHz（不乐观情况下），主要是因为我们预计经典控制电路将无法控制更高频率的量子门。（如需了解此方向的进展，请参阅[HHOI11]。）如图6（b）所示。

数据点取自下表：门时间年参考420NS 2013【CGC+13】433ns 2015【CMS+15】160ns 2016【SMCG16】42ns 2017【DBE17】25ns 2018谷歌，预计在20172015 2020 2025 2030 2035 20401001021041061081010量子比特数（a）2015 2020 2030 2035 20401071081091010比特频率（b）2015 2020 2025 2030 2035 204010-610-510-410-310-210-1交货期（c）2020 2025 2030 2035 204010-310-210-1100间接费用减少（d）图6。预测量子比特数、量子门频率（门内操作persecond）和作为时间函数的量子门精确度。第四个图模拟了由于理论进步而导致的开销减少。图6（c）显示了浇口入口的预测发展。我们假设入口供应量将继续呈指数级下降，但这一发展将停滞在5·10的供应量-6（乐观情况）或5·10-5（不太乐观的情况）。对于乐观主义的情况，我们预计，进口将继续遵循DeVincenzo的法律，该法律预测进口每年减少2倍。数据点摘自下表：门函数年份参考0.9347 2013【CGC+13】0.96 2014【CGM+14】0.97 2015【CMS+15】0.99 2016【SMCG16】0.995 2017【Goo】0.997 2018【Goo】最后，我们假设任何算法所需的量子位和时间步数将随着时间的推移而减少，原因有二。首先，闸门可靠性将随着时间的推移而增加，从而允许使用更高效的容错方案。其次，理论上的进步将允许减少实现算法和容错方案所需的量子比特和门的数量。

我们预计该系数将为开销（t）=βt-2017年，其中β∈ {0.75，0.85}分别表示乐观和不太乐观的假设。致谢MT和GB感谢Michael Bremner的初步讨论。TL感谢John Tromp对工作证明的有益评论和讨论，感谢Ronaldde Wolf对并行量子搜索的对话。【Amb07】A.Ambainis。元素区分的量子行走算法。《暹罗计算机杂志》，37:210–2392007。【AS04】S.Aaronson和Y.Shi。碰撞和元素区分问题的量子下界。ACM杂志，51（4）：595–6052004。亚当回来了。Hashcash–拒绝服务对策，2002年。提供地点：http://www.hashcash.org/papers/hashcash.pdf.【BBBV97】C.H.Bennett、E.Bernstein、G.Brassard和U.Vazirani。量子计算的优势和劣势。《暹罗计算杂志》，26:1510–1523，1997年。Michel Boyer、Gilles Brassard、Peter Hoyer和Alain Tapp。量子搜索的严格限制。Fortschritte der Physik，46（4-5）：493–5051998年。约翰·布克曼、埃里克·达曼和安德烈亚斯·赫尔辛。XMSS–一种基于最小安全假设的实用前向安全签名方案。《后量子密码术》，第117–129页，2011年。Daniel J Bernstein、Daira Hopwood、Andreas H¨ulsing、Tanja Lange、Ruben Niederhagen、Louiza Papachristodoulou、Michael Schneider、Peter Schwabe和Zooko WilcoxO\'Hearn。括约肌：实用的无状态哈希签名。密码技术理论与应用国际年会，第368-397页。Springer，2015年。Alex Biryukov和Dmitry Khovratovich。Equihash：基于广义生日问题的不对称工作证明。分类账，2:1–30，2017年。【BKM+14】R.Barends、J.Kelly、A.Megrant、A.Veitia、D.Sink、E.Jeffrey、T.C.White、J.Mutus、A.G.Fowler、B。

坎贝尔、Y.Chen、Z.Chen、B.Chiaro、A.Dunsworth、C.Neill、P.O\'Malley、P.Roushan、A.Vainscher、J.Wenner、A.N.Korotkov、A.N.Cleland和John M.Martinis。用于容错的表面代码阈值超导量子电路。《自然》，508（7497）：500–5032014年4月。米希尔·贝拉尔和菲利普·罗格威。随机预言是实用的：设计高效协议的范例。1993年，ACM计算机和通信安全会议，第62–73页。尼古拉斯·考托伊斯、马蒂厄·菲尼亚斯和尼古拉斯·森德里。如何实现一个基于mceliece的数字签名方案。《亚洲加密》（Asiacrypt），第2248卷，第157-174页。斯普林格，2001年。[CGC+13]A.D.C\'orcoles、Jay M.Gambetta、Jerry M.Chow、John A.Smolin、Matthew Ware、Joel Strand、B.L.T.Plourde和M.Ste ff en。通过随机基准测试对两个量子比特量子门进行过程验证。体检A，87（3）：030301–，2013年3月。【CGM+14】杰瑞·M·周杰伦、杰伊·M·甘贝塔、伊斯瓦尔·马格桑、大卫·W·亚伯拉罕、安德鲁·W·克罗斯、B·R·约翰逊、尼古拉斯·A·马斯鲁克、科尔姆·A·瑞安、约翰·A·斯莫林、斯里坎特·J·斯里尼瓦桑和M·斯特芬。实现可伸缩容错quantum computingfabric链。《自然通讯》，2014年6月5日。Daniel Crow、Robert Joynt和M.Saffman。改进了无测量误差校正的误差阈值。《物理审查函》，117（13）：130503–，2016年9月。Andrew M Childs、Robin Kothari和Rolando Somma。量子线性系统算法对精度的依赖性呈指数级提高。arXiv:1511.023062015。【CMS+15】A.D.C'orcoles、Easwar Magesan、Srikanth J.Srinivasan、Andrew W.Cross、M.Steffen、Jay M.Gambetta和Jerry M.Chow。使用四个超导量子比特的方形晶格演示量子错误检测码。《自然通讯》，6:6979，2015年4月。[DBE17]邓秀浩、埃德温·巴恩斯和索菲亚·E·Economou。

腔耦合transmon量子比特中纠错门的鲁棒性。体检B，96（3）：035441–，2017年7月7日。L’eo Ducas、Alain Durmus、Tancr’ede Lepoint和Vadim Lyubashevsky。晶格特征和双峰高斯。《密码学进展–加密2013》，第40-56页。Springer，2013年。[DLL+17]L\'eo Ducas、Tancr\'ede Lepoint、Vadim Lyubashevsky、Peter Schwabe、Gregor Seiler和Damien Stehl\'e.晶体–二锂：模块晶格的数字签名。技术报告，IACR Cryptology ePrint Archive，2017:6332017。[DN12]L’eo Ducas和Phong Q Nguyen。学习zonotope等：ntrusignantractives的密码分析。《亚洲加密》（ASIACRYPT），第7658卷，第433-450页。Springer，2012年。[DS05]丁金泰和施密特。彩虹，一种新的多变量多项式符号方案。ACNS第5卷第164–175页。斯普林格，2005年。【FMMC12】奥斯汀·G·福勒、马特奥·马里安东尼、约翰·M·马丁尼和安德鲁·N·克莱兰。表面代码：走向实用的大规模量子计算。物理。修订版。A、 2012年9月86:032324。蒂姆·古尼苏、瓦迪姆·柳巴舍夫斯基和托马斯·佩尔曼。实用的基于晶格的密码术：一种用于嵌入式系统的签名方案。在CHES中，第7428卷，第530–547页。Springer，2012年。[咕]https://www.newscientist.com/article/2138373-google-on-track-for-quantum-computerbreakthrough-by-end-of-2017/.[GPV08]Craig Gentry、Chris Peikert和Vinod Vaikuntanathan。硬格的陷门和新的密码结构。第四十届ACM年度计算理论研讨会论文集，第197-206页。ACM，2008年。洛夫·K·格罗弗。一种用于数据库搜索的快速量子力学算法。过程中。ACMSTOC 1996，第212-219页。ACM，1996年5月。罗伯特·M·金里奇、科林·P·威廉姆斯和尼古拉斯·J·塞尔夫。具有并行性的广义量子搜索。物理回顾A，61（5）：052313–，04 2000。【HHL09】阿拉姆W。