量子时代，区块链安全何去何从？

被吹捧的量子计算会对比特币区块链产生什么影响？

最近很多人都在关注谷歌的量子计算，同时也怀疑比特币区块链是否还安全。 关于量子计算，我们团队一直在跟踪研究，所以做了一些梳理，先给大家展示一些内容。 一定是全面的，但从目前来看，现有的量子计算对比特币区块链没有任何威胁。 今后我们将继续关注和研究。 随着量子计算和加密技术的发展，两者应相互补充，共同推动科技进步。

——嘉楠耘智联席董事长孔建平

量子计算的历史

量子计算是一种新的计算模型量子技术对比特币的影响，它根据物理学中的量子力学定律来控制各个信息单元。

在赛迪电子信息研究院发布的《2019年量子计算发展白皮书》中，将量子计算的发展分为三个阶段。

1. 量子计算研究探索阶段

20世纪90年代以前的量子计算研究称为理论探索阶段。 早在 20 世纪 70 年代，就有了与量子计算相关的概念。 1982年，贝尼奥夫（Benioff）提出了量子计算机的概念。 同年，费曼（Feynman）提出了利用量子系统进行信息处理的想法。 这时候量子计算才真正成为一种理论。 1985年，Deutsch首次验证了量子计算的并行性，表明量子计算具有强大的计算能力。

2. 量子计算编码算法研究阶段

1990年代到21世纪这段时期被称为量子计算编码算法的研究时期。 这一时期出现了两个轰动一时的量子算法，即1994年提出的整数分解算法和Grover数据库搜索算法于1996年提出的算法。后来证明，秀尔算法也可以用来解决离散对数问题。

与传统方法相比，这两种量子算法在各自的问题上都表现出极大的优势，也为量子计算的发展提供了相当的理论基础。

3、技术验证及原理样机开发阶段

进入21世纪以来，量子计算进入技术验证和原理原型研制阶段，因为量子计算在前两个阶段已经有了相当的理论储备。

2000 年，DI Vincenzo 提出了构建量子计算机的标准。 此后，加拿大的D-Wave公司率先推动了量子计算机的商业化，IBM、谷歌、微软等科技巨头也开始布局量子计算。

2018年，谷歌发布了72比特的超导量子计算处理器芯片。

2019年，IBM发布了最新的IBM Q System One量子计算机，提出了衡量量子计算进步的一个特殊性能指标——量子体积，并在此基础上提出了“量子摩尔定律”，即量子体积为量子计算机每年翻一番。 如果这个定律成立，人类有望在10年内实现量子霸权（量子霸权是指量子计算所拥有的超越所有经典计算机的计算能力）。

2019年10月24日，英国《自然》杂志刊登称，谷歌在计算机研究领域取得突破——创造出第一台能够超越当今最强大超级计算机能力的量子计算机。 “Sycamore”。谷歌声称，量子系统仅需 200 秒即可完成采样任务，而同样的计算用当今最强大的超级计算机大约需要 1 万年才能完成。为此，谷歌公开宣布实现“量子霸权”。

量子计算对传统密码学的影响？

密码学作为现代通信系统的重要组成部分，有效地满足了用户在实际通信过程中的安全、认证等服务需求，而现代通信协议主要依赖三个核心密码功能：公钥加密、数字签名和密钥交换. 这些密码函数的安全性是通过假设“某些数学问题无法有效求解”来实现的，这些密码函数常用的数学问题包括大整数因式分解、离散对数问题等。

1994年，Shor提出了一种可以在量子计算机上运行的算法，可以有效解决大整数分解和离散对数问题，这使得原本用来保证密码学安全性的难题假设不再有效. 迄今为止，量子计算机已成为传统密码学领域挥之不去的阴霾。

单向函数假设是公钥密码学的基本假设。 它假设有一些函数正向计算很容易，但逆向过程就很困难了。 例如，我们很容易从a和b中得到ab，但是从ab中得到a和b却很困难。

单向函数可以分为两种类型，单向陷门函数和单向无陷门函数。 单向陷门函数用在公钥密码体制中，即对于一条加密的消息，如果我们知道私钥，就可以很容易地解密出这条消息，但是不知道私钥的人就很难解密了要知道正确的消息，此时的私钥称为陷门。 常用的散列函数是没有陷门的单向函数，即任何信息都不会帮你解反函数。

单向陷门功能是基于一些数学上的难题来实现的。 量子计算机通过解决这个数学问题就可以找到它的陷门，从而快速得到它的逆运算，这样单向陷门函数就不再安全了。 . 对于没有陷门的单向函数，量子计算机只能通过超强的计算能力搜索单向函数的输出空间，从而得到单向函数的映射来求​​解反演问题。

量子计算对区块链的影响？

区块链在密码学领域有着非常特殊的地位。 它的出现使许多先进的密码学理论得以付诸应用。 区块链通过大量基于公钥密码学的协议解决了“陌生人之间相互信任”的社会矛盾。 正因为如此，量子计算对传统密码学的冲击也极大地威胁着区块链系统的稳定发展。

比特币是区块链技术最早、最著名的应用场景。 量子计算机的快速发展，甚至会给比特币带来毁灭性的打击。 两个最具影响力的方面是工作证明和支付流程。

工作量证明就是反复改变区块头中的nonce值，计算区块头的hash值，直到找到符合条件的hash值对应的nonce值。 当网络中的出块速度变快时，网络会减少满足条件的哈希值个数，从而使网络的出块速度始终趋于一个稳定值。 量子计算机的发展将大大提高计算机计算哈希的能力，从而破坏出块速度的稳定性。

在支付过程中，用户使用自己的私钥从过去的交易中获取自己的货币，使用他人的公钥来表明自己的支付对象。 此外，用户还需要对自己的交易进行签名和认证，而这一系列通过公钥密码学实现的支付过程对量子计算机来说是没有意义的。 量子计算机可以很容易地根据用户的公钥信息伪造用户的私钥和签名，冒充用户进行任何币种交易，使整个比特币系统没有任何安全可言。

但并不是所有的密码学理论都是无用的。 由于秀尔算法只解决大整数因式分解和离散对数等难题，安全性不依赖于此的密码工具仍然可以发挥其用途，如哈希函数和AES等。

当然，Grover基于量子计算机的搜索算法可能会在一定程度上增加哈希碰撞的概率，但已经证明该算法无法接受搜索空间的指数增长，因此只需增加哈希空间即可通过增加安全位数可以使散列函数恢复到安全状态。 因此，对后量子密码学发展的研究主要分为“寻找当今量子算法无法破解的数学问题”和“引入安全性不基于易破解难题假设的密码工具” ”。

虽然理论上，量子计算对公钥密码安全的影响会影响到比特币等区块链系统，但实际上对整个互联网安全的影响会更加深远，因为公钥密码可以看作是一个重要的组成部分的互联网生态系统。 基础。 然而，考虑到现实世界中量子计算硬件的发展现状，事实上，量子计算距离对公钥密码学构成威胁还有很长的路要走。

当今量子计算的问题

量子计算机具有与电子计算机相同的功能，都是用来解决数学问题的。 不同的是，量子计算机使用量子芯片，采用并行运行方式。 电子计算机使用的是电子芯片，采用串行操作方式。

与传统计算机相比，量子计算机的突出优势如下：

1、将NP问题转化为P问题，打破“P≠NP”的百年难题；

2、可以提高P类问题的求解速度。

目前，量子计算机研究还需要解决两个问题。

一是量子计算机是人造的量子系统，量子相干性在宏观环境中会自动消失，从而失去其量子信息功能。

二是人类使用经典工具来控制量子设备的状态和演化。 这个控制能力还是很差，有待提高。

郭光灿院士在《量子计算机研究进展》中将量子计算机的发展分为三个阶段：

第一阶段由少量的量子比特组成，只需要确保它们确实是按照量子力学定律运行的数据处理器。

第二阶段是量子霸权。 不管它的纠错和容忍度如何，只要能解决某一类问题，就可以在相干的时间内完成这一类问题。

最后一个阶段是能够纠错和容错并且位数足够。

目前，量子计算机的发展还处于第二阶段。 我们仍然需要增加量子比特的数量，我们也需要对谷歌宣称的“量子至上”进行相关研究。

后量子密码学的发展

目前针对量子计算攻击的防御主要有五种方式：

1. 基于编码的密码

2. 基于哈希函数的密码

3.多元元密码

4.格密码

5. 同源加密

Encoding-based ciphers - 1978年在McEliece密码中首次提出，一直没有有效的解决方案。 在随后的一段时间里量子技术对比特币的影响，其他基于纠错码的系统不断涌现。

尽管这些密码系统速度非常快，但它们中的大多数都存在密钥过大的问题。 在最近的研究中，人们经常尝试引入一些额外的结构来解决密钥过大的问题，但引入的结构往往存在一定的安全隐患。 但基于代码的密码确实是后量子时代确保安全的重要手段，其思想可以继续发展并应用于其他功能，如穿梭数字签名。

基于散列的签名——即使用散列函数构造的数字签名。 由于哈希函数本身具有一定的抗量子攻击能力，因此这种结构必须保证后量子时代系统的安全性。 现有的许多高效的基于哈希的签名方案都有一个共同的缺点，即签名者必须记录之前签名消息的准确数量，任何错误的记录都会导致严重的安全问题。 此外，由于哈希函数的输出空间有限，它们只能生成有限数量的签名。 我们当然可以通过扩大输出空间的大小来增加签名的数量，但是是以增加签名的大小为代价的。

多元多项式密码——这些方案是基于“有限域上多元多项式的难题”构建的。 在过去的几十年里，许多多元密码体制被提出。 虽然其中一些已经被破解，但是这个思路仍然可以为后量子时代的系统安全提供一个有效的选择。

Lattice-Based Cryptography——基于格的密码系统近年来重新受到关注，原因如下：

第一，很多密码学参考文献可以设计格作为底层结构，例如全同态加密、程序混淆、基于属性的加密；

此外，大多数基于格的密钥建立算法都比较简单、高效且高度可并行化；

此外，一些基于格的系统的安全性在最坏情况下的困难假设下可证明是安全的，但在一般情况下则不然。

另一方面，即使采用已知的密码分析技术，也难以准确估计格方案的安全性，从而极大地保证了通信的安全性。

基于超奇异椭圆曲线的同源密码学——量子计算机上的秀尔算法可以有效解决椭圆曲线上的离散对数问题，而超奇异曲线上的同源问题没有类似的量子攻击。 但与其他一些方案一样，例如基于共轭搜索问题和编织群相关问题的方案，随着研究的继续，我们不能始终保证其安全性。