编者按：本文来源嘉楠耘智，创业邦经授权转载。
热捧的量子计算究竟会对比特币区块链有何影响？
最近很多人在关注谷歌的量子计算，也怀疑比特币区块链是否还安全，关于量子计算，我们团队一直在跟踪和研究，为此我们做了一些梳理，先将一些内容展现给大家，不一定全面，但从目前来看，现有的量子计算对比特币区块链不构成任何威胁。后续我们也会持续关注和研究，随着量子计算和加密技术的发展，两者应该能相辅相成，从而共同推进科技的进步。
——嘉楠耘智联席董事长 孔剑平
量子计算的历史
量子计算是根据物理中量子力学的规律，来控制每一个信息单元的新型计算模式。
在赛迪智库电子信息研究所的《2019年量子计算发展白皮书中》，将量子计算的发展分为三个阶段。
1，量子计算的研究探索阶段
将20世纪90年代以前对量子计算的研究称为理论的探索阶段。早在上个世纪70年代就有了量子计算相关的概念，1982年贝尼奥夫（Benioff）提出了量子计算机的概念，同年费曼（Feynman）提出利用量子系统进行信息处理的设想，此时量子计算才真正的成为了一个理论。1985年，多伊奇（Deutsch）首次验证了量子计算的并行性，表明了量子计算具有强大的计算能力。
2，量子计算编码算法的研究阶段
20世纪90年代带21世纪的这段时间被称为量子计算编码算法的研究时期，这段期间出现了两个轰动性的量子算法，分别为1994年提出的针对整数分解的秀尔（Shor）算法和1996年提出的用于数据库搜索的葛罗佛（Grover）算法。后来证明，秀尔（Shor）算法也可以用于离散对数问题的求解上。
相较于传统方法而言，这两个量子算法分别在各自的问题上展现出巨大优势，也为量子计算的发展提供了相当的理论基础。
3，技术验证和原理样机研制阶段
21世纪以来，由于量子计算在前面两个阶段已经有了相当的理论储备，量子计算进入了技术验证和原理样机研制的阶段。
2000年，迪温琴佐（DIVincenzo）提出建造量子计算机的判据。此后，加拿大D-Wave公司率先推动量子计算机商业化，IBM、谷歌、微软等科技巨头也陆续开始布局量子计算。
2019年，IBM发布最新IBM Q System One量子计算机，提出衡量量子计算进展的专用性能指标——量子体积，并据此提出了“量子摩尔定律”,即量子计算机的量子体积每年增加一倍。若该规律成立，则人类有望在10年内实现量子霸权（量子霸权是指量子计算拥有的超越所有经典计算机的计算能力）。
2019年10月24日，英国《自然》（Nature）杂志刊登了谷歌在计算机研究领域取得了一项突破——打造出了第一台能够超越当今最强大的超级计算机能力的量子计算机 “西克莫（Sycamore）”。谷歌称该量子系统只用了 200 秒完成了采样任务，而同样的计算用当今最强大的超级计算机执行，需要约 10000 年。由此，谷歌公开宣布实现“量子霸权”。
量子计算对传统密码学的影响？
密码学作为现代通信系统中一个重要的组成部分，切实的满足了用户在实际通信过程中的安全、认证等服务需求，而现代通信协议主要依赖于三个核心的密码功能:公钥加密、数字签名和密钥交换。这些密码功能的安全性，是通过假设“一些数学问题无法被有效解决”来实现的，而这些密码功能常用的数学难题有大整数的因数分解、离散对数问题等。
1994年，秀尔（Shor）提出了一种可在量子计算机中运行的算法，该算法可有效求解大整数分解和离散对数问题，这使得原本用于保障密码学安全的困难问题假设不在成立，至此量子计算机就成为传统密码学领域中挥之不去的阴霾。
单向函数假设是公钥密码体制中的基本假设，其假设存在一些函数正向计算很容易，但求逆过程却非常困难。例如，我们可以很容易通过a和b求得ab，但根据ab很难求得a和b。
单向函数又可以分为两种，即单向陷门函数和无陷门的单向函数。公钥密码体制中使用的都是单向陷门函数，即对于某个加密消息，如果我们知道了私钥可以很容易对消息解密，但对于不知道私钥的人却很难知道正确的消息，此时的私钥就被称为陷门。而常用的哈希函数是无陷门的单向函数，即任何信息都无助于你对逆函数的求解。
单向陷门函数都是基于一些数学上的困难问题实现的，量子计算机可以通过解决这个数学难题找到其陷门，从而很快的求得其逆运算，使得单项陷门函数不再具有安全性。对于无陷门的单向函数而言，量子计算机只能通过其超高的计算能力，搜索单向函数的输出空间，从而得到单向函数的映射以解决求逆问题。
量子计算对区块链的影响？
区块链在密码学领域有着极其特殊的地位，它的出现使得许多先进的密码学理论可以投入到应用之中。区块链通过大量的基于公钥密码体系的协议，解决了“陌生人之间相互可信”这一社会矛盾。正因如此，量子计算对传统密码学的影响，也极大程度的威胁了区块链系统的稳定发展。
比特币是区块链技术最早也是最著名应用场景，量子计算机的飞速发展甚至会给比特币带来毁灭性的打击，其中冲击最大的两个方面为工作量证明和支付过程。
工作量证明是通过反复改变块头中nonce值并计算块头哈希值，直至找到满足条件的哈希值所对应的nonce值。当网络中出块速度变快时，网络会减少满足条件的哈希值的个数，从而使得网络出块速度总是趋近于一个稳定值。而量子计算机的发展会极大地提高计算机计算哈希的能力，从而破坏出块速度的稳定性。
而在支付过程中，用户使用自己的私钥从过去的事务中获得自己的货币，并通过他人的公钥来表明自己的支付对象，此外用户还需要对自己的交易进行签名认证，而这一系列通过公钥密码体制实现的支付过程，对量子计算机而言是毫无意义的。量子计算机可以轻易地根据用户的公钥信息伪造用户的私钥和签名，冒充用户进行任何货币交易，从而使得整个比特币系统没有任何的安全性可言。
但并不是所有的密码学理论都失去了作用，由于秀尔（Shor）的算法解决的仅是大整数的因数分解和离散对数等困难问题，因而安全性不依赖于此的密码工具仍可以发挥他们的用途，如哈希函数和AES等。
当然，葛罗佛（Grover）的基于量子计算机的搜索算法可能会在一定程度上增加哈希碰撞的概率，但该算法被证明并不能接受搜索空间的指数增长，故而仅需要通过增加哈希空间的安全位数，便可以使哈希函数重新回到安全的状态。因此，对后量子密码学的发展研究主要分为“寻找现如今量子算法不能攻破的数学难题”和“引入安全性不基于易攻破的困难问题假设的密码工具”。
尽管在理论上，量子计算对公钥密码体系安全的影响，会波及到比特币等区块链系统，但实际上整个互联网安全受到的影响要更加深远，因为公钥密码体系可以认为是互联网生态的基础。但考虑到现实世界中量子计算硬件的发展现状，实际上量子计算离其对公钥密码体系产生威胁还有很长的路要走。
当下量子计算存在的问题
量子计算机同电子计算机的功能一样，都是用来解数学问题，不同的是，量子计算机用的是量子芯片，采用并行运算模式。电子计算机用的是电子芯片，采用串行运算模式。
相较于传统的计算机，量子计算机的突出优势表现在：
1、将NP问题转化成P问题，打破“P≠NP”的世纪难题；
2、可提高P类问题的求解速度。
目前量子计算机研究还需要解决两方面难题。
一是量子计算机是人造量子系统，在宏观环境下量子相干性会自动消失，从而丧失其量子信息功能。
二是人类采用经典工具去操控量子器件的状态和演化，这种操控能力目前还很差，有待提高。
郭光灿院士在《量子计算机的研究进展》中将量子计算机的发展分为三个阶段：
第一阶段包含少数的量子比特，仅需保证其确实是按照量子力学运行规律的数据处理器。
第二阶段是量子霸权，不考虑它的纠错容错，只要能解决某一类问题，这类问题可以在相干时间内完成。
最后一个阶段就是能够纠错容错而比特数又足够多。
目前量子计算机的发展还处于向第二阶段迈入的时期，我们仍需要提高量子比特的数量，对于谷歌宣称的“量子霸权”也需要相关的考证。
后量子密码学的发展
目前，针对量子计算攻击的抵御主要包括五种途径：
1.基于编码的密码
2.基于哈希函数的密码
3.多变元密码
4.格基密码
5.同源密码
基于编码的密码——1978年，在McEliece密码中首次被提出，且一直都没有出现有效的解法。在其后的一段时间里，其他基于纠错码的系统也不断涌现。
该类密码系统虽然速度很快，但大多数都存在密钥过大的问题。在近期的研究中，人们常常试图引入一些额外的结构以解决密钥过大的问题，但引入的结构往往本身存在一定的安全隐患。但基于编码的密码确实是后量子时代保障安全的重要手段，其思想还可以继续发展并应用于梭数字签名等其他功能。
基于哈希的签名——即使用哈希函数构造的数字签名。由于哈希函数本身具有一定的抵抗量子攻击的能力，故此类构造必然能保障系统在后量子时代的安全性。现有的许多高效的基于哈希的签名方案都存在一个共同的缺点，即签名者必须记录先前签名消息的确切数量，且任何错误的记录都会导致严重的安全性问题。此外，由于哈希函数的输出空间是有限的，故它们只能生成有限数量的签名。我们当然可以通过扩展输出空间的大小来增加签名的数量，但作为代价，签名的大小也会增大。
多元多项式密码——这些方案的构造是基于“有限域上多元多项式的困难问题”。在过去的几十年里，人们提出了许多的多元密码系统，尽管其中有些已经被破解，但该思想仍能在后量子时代为系统的安全性提供一个有效的选择。
基于格上困难问题的密码——基于格的密码系统近些年重新引起了人们的兴趣，原因如下：
首先，许多密码学引用都可以将格作为底层结构进行设计，如全同态加密、程序混淆和基于属性的加密等；
此外，大多数基于格的密钥建立算法相对简单、高效、并行性强；
并且，某些基于格的系统的安全性在最坏情况的困难假设下是可证明安全的，而不是在平均情况下。
另一方面，即使是已知的密码分析技术，也很难对格方案的安全性给出精确的估计，由此大大的保证了通信的安全性。
基于超奇异椭圆曲线的同源密码——量子计算机上的秀尔（Shor）算法可以有效地解决椭圆曲线上的离散对数问题，而超奇异曲线上的同源问题则没有类似的量子攻击。但像其他一些方案一样，例如基于共轭搜索问题和辫子群中的相关问题的方案，随着研究不断的深入我们也不能一直确保其安全性。
