（燕宝）量子密码和后量子密码

2017-12-01 上海保交所 燕宝 量子密码和后量子密码

近日，由中国金融科技50人论坛（CFT50）与证券信息技术研究发展中心（上海）举办的“区块链里的密码学技术”闭门研讨会议，在上海证券大厦举行。

主题演讲，上海保交所区块链底层首席架构师 燕宝

以下为发言实录（经本人审核修改）。

《区块链技术体系中的加密技术 - 量子密码和后量子密码》

非常感谢CFT50论坛提供一个区块链技术交流的平台，白老师（白硕）、王老师（王励成）的演讲都非常精彩，我在这里跟大家简单分享一下我们近期的在区块链技术的研究方向。

我们在实际应用当中，碰到了很多像白老师前面讲解内容一样的需求，特别突出是在数据安全防护、身份和交易数据的隐私保护方面。在某些应用案例中，银行方面提出

“区块链中的数据是通过现有的加密算法是保证安全，目前是安全的，但不代表一直是安全的；数据多方存储（分布式存储），存在潜在的安全风险”。

在交流的过程中，他们提出了量子计算攻击和后量子密码算法方面的意见和看法，我们就和上海交大-密码与计算机安全实验谷老师的团队，针对于这方面去做了一些深入的交流和研究，今天将我们学习研究的内容跟大家简单分享一下。

首先和大家介绍一下分享的议程，

• 第一阶段，背景知识（量子力学、量子通信、量子计算与量子计算机）；
• 第二阶段，量子密码与后量子密码（量子密码体系、量子攻击方法、后量子密码标准化、主流的后量子密码）；
• 第三阶段，区块链世界里的攻击与密码破译的量子算法（针对区块链基础设施、智能合约以及冷热钱包的攻击、密码破译的Grover算法、Shor算法）。

一、背景知识

在分享量子密码与后量子密码之前，了解一下量子相关的背景知识。先从量子力学说起吧，量子力学里面描述微观物质理论，与相对论一起被认为是现代物理学的两大基础支柱。

微观世界里，粒子嗡嗡跳跃的概率云，它们不只存在一个位置，也不会从一个A点通过一条单一路径到达B点；此外，微观粒子具有波粒二象性。微观体系里的状态的有两种变化，

• 一种是按运动方程式演进，这种是可逆的变化；
• 另一种是测量改变体系状态不可逆的变化。

量子就是量子世界中物质客体的总称，他既可以是光子、电子、原子、原子核、基本粒子等微观粒子，也可以是波色-爱因斯坦凝聚、超导体、“薛定谔猫”等宏观尺度下的量子系统，他们的共同特征就是必须遵从量子力学的规律。

后面我们看一下从量子力学里几个重要理论。

• 第一个理论：量子态叠加原理，量子态是量子力学里边来描述量子系统的状态，其运动规律遵循薛定鳄的方程；量子态也被称为波函数或几率幅，记为|ψ⟩，假定量子客体有两个确定的可能状态0或者1，通常写成|0⟩、|1⟩，由于量子状态是不确定的，它一般不会处于|0⟩或|1⟩的确定态上，只能处于这两种确定态按某种权重叠加起来的状态上，这就是量子世界独有的量子态叠加原理，用数学表示即为：|ψ⟩=|0⟩+|1⟩，其中，为复数，且满足+=1。
• 第二个理论：海森堡测不准原理，在经典力学中，测量对物理系统本身没有任何影响，可以无限精确地进行；在量子力学中，测量过程本身对系统造成影响；对于两个不同的物理量A和B（如坐标和动量，时间和能量等），不可能同时具有确定的测量值，这是由于测量过程对微观粒子行为的“干扰”，致使测量顺序具有不可交换性。
• 第三个理论：量子纠缠，对于由多个粒子组成的系统，其每个粒子的状态往往无法被分离出来，因此，单个粒子的状态被称为是纠缠的；纠缠的粒子有惊人的特性，例如：对一个粒子的测量，可以导致整个系统的波包立刻塌缩，因此也影响到另一个、遥远的、与被测量的粒子纠缠的粒子。
• 第四个理论：量子退相干，当两个粒子互相纠缠时，即使距离遥远，一个粒子的状态变化将会影响另一个粒子的状态变化；量子纠缠是量子技术的重要资源，是量子计算机、量子模拟等重大应用的物理基础；量子纠缠尽管奇妙无比，用途广泛，但它却有天然的致命伤——量子纠缠十分脆弱，环境会破坏其量子特性而使“纠缠”消失掉，即两个纠缠的量子客体最终会演化为不纠缠的状态，非局域关联或完全断开；环境不仅包括经典噪声，诸如热运动、吸收、散射等，还包括量子噪声，即真空起伏。这种环境引起的量子性消失，被称为量子退相干。

基于量子力学的理论基础，后面介绍一下量子通讯、量子计算与量子计算机。

• 量子通信是指利用量子纠缠效应或海森堡测不准原理进行信息传递的一种通讯方式。
• 量子计算是一种遵循量子力学规律调控量子信息单元进行计算的新型计算模式。

量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置，该装置处理和计算的是量子信息、运行的是量子算法。

量子计算机使用的是量子比特，量子计算机能秒杀传统计算机得益于两个独特的量子效应：量子叠加和量子纠缠。

• 量子叠加能够让一个量子比特同时具备0和1的两种状态，
• 量子纠缠能让一个量子比特与空间上独立的其他量子比特共享自身状态，创造出一种超级叠加，实现量子并行计算，其计算能力可随着量子比特位数的增加呈指数增长。

二、量子密码与后量子密码

第二阶段，大家简单分享一下量子密码和后量子密码知识。

Shannon证明，若密钥为长度不小于待加密的明文长度的随机序列，且任何一密钥仅使用一次，该加密体制（C=PK）是无条件安全的（Perfect Secrecy）。

为何“一次一密”密码迄今未被广泛使用呢？主要原因是，“一次一密”要大量消耗“密钥”，需要通信双方不断地更新密码本，而“密码本”的传送（称为“密钥分配”）是关键问题所在。

• 量子密码体系采用量子态作为信息载体，经由量子通道在合法的用户之间传送密钥；
• 量子密码的本质是用于解决密钥分配问题 ，从该意义上说，量子密码即为量子密钥分配，为“一次一密”加密体制在公开信道进行安全、高效的密钥分配提供很好的解决方案。

量子密码的安全性由量子力学原理所保证，具体来说，其安全性依赖于：

• 1)量子不可克隆性：窃听者无法克隆出正确的量子比特序列；
• 2)海森堡测不准原理：基于单光子量子信道的量子密码
• 3)量子纠缠：基于量子相关信道的量子密码。

量子密码在理想状态下可以确保密钥的安全性，但实际上量子密码系统绝对达不到理想状态，例如单粒子探测效率不是百分百的，它会产生传输损耗，各种器件不完善等等问题，这些非理想漏洞就可能被窃听者用来窃取密钥，但却不会被合法用户发现。同时，量子密码体系必须确保安全密钥的生成率足够高，以达到信息“一次一密”加密的需求。

目前，在百公里范围的城域网，量子密码体系可以做到密钥分配在现有的各种攻击下是安全的，安全密钥生成率在25公里内可确保高清视频“一次一密”。

量子攻击方法可分为非相干攻击和相干攻击。

• 非相干攻击：攻击者独立地给每一个截获到的量子态设置一个探测器，然后测量探测器中的粒子，从而获取信息；
• 相干攻击：攻击者通过某种方法使多个粒子比特关联，从而可相干地测量或处理这些粒子比特，进而获取信息。

由于量子信息的奇妙特性，使得量子计算具有天然的并行性，且其计算能力可随着量子比特位数的增加呈指数增长；量子计算机的这种超强计算能力，使得基于某些数学难题的传统公钥密码的安全受到挑战；然而，量子计算机并不能解决电子计算机难于求解的所有数学问题。基于量子计算机不擅长计算的那些数学问题构造密码，就可以抵抗量子计算的攻击，我们称能够抵抗量子计算机攻击的密码为抗量子计算密码，或后量子密码。

出于对抗量子计算密码需求的紧迫性，国际上从2006年开始举办"抗量子计算密码学术会议（Post-QuantumCryptography）"，每两年举行一次，至今已举办了4届，已经产生了一批重要的研究成果，让人们看到了抗量子计算密码的新曙光。

• 2015 年 8 月，美国国家安全局公开宣布由于面临量子计算的威胁，其计划将联邦政府各部门目前使用的ECC/RSA 算法体系向后量子算法进行迁移。
• 而负责标准制定的美国国家标准与技术局也在2016 年 2 月正式面向全球公开了后量子密码标准化的路线图，并在同年秋正式公布征集密码系统建议的计划，其中包括公钥密码、数字签名以及密钥交换算法，建议征集的截止日期定于2017年12月；此后，国家标准与技术局会利用3-5年时间分析这些建议并发布相关分析报告，最终的标准拟制工作也将耗时1-2年。
• 换言之，国家标准与技术局后量子密码算法标准最终将在2021-2023年出台；而考虑到其具备较好的安全性能以及国际互联网工程任务组已经着手展开了标准化工作，基于哈希算法的签名标准可能会更快地推出。
• 除此之外，欧洲量子密码学术和工业界研究者联合组织“后量子密码”项目（PQCrypto）也在2015年发布了一份初始报告，在对称加密、对称授权、公钥加密以及公钥签名系统领域都提出了相关标准化建议。
• 针对受到量子计算技术严重威胁的RSA/ECC密码系统，该报告认为麦克利斯密码系统具有发展成为新的公钥加密标准的潜力。

在后面和大家分享一下四种主流的后量子密码算法及其优缺点。

第一种是基于哈希算法签名（Hash-based signatures），安全依赖于底层的哈希函数的抗碰撞性；
优点：安全要求是最小的；
缺点：只能用于量子签名方案（签名/验签）。

第二种是基于多元二次方程式密码（Multivariate-quadratic-equations-cryptography），多变量密码体制（MPKC）被认为是能够抵御基于量子计算机攻击的新型公钥密码体制之一，利用减扰动方法构造出了一种基于MPKC的新型签名方案，其计算效率，主要指中心映射求逆的效率高于两个著名的多变量签名体制Sflash和Quartz；
优点：与基于hash的签名方案相比，签名较短；
缺点：与传统的RSA、ECC等系统相比，密钥非常大；还有在MPKCs的可证明安全性没有实质性的结果。

第三种是基于编码密码（Code-basedcryptography），算法原语（底层单向函数）使用纠错码，第一个基于编码密码（公钥加密方案）是由Robert J. McEliece在1978年提出的；
优点：加解密速度快；
缺点：大型公钥大小（100KBS-几MBS），签名/验签成本大，

“基于编码密码体系没有实际应用是知道”；二元Goppa码是安全的（似乎是），而其他基于编码密码体系适用应仔细考虑，有些方案看上去并不是很牢靠的。

第四种是基于格密码（Lattice-basedcryptography），安全性是基于最坏情况下格问题的困难，Ajtai在1996年提出“Collision-ResistantHash Function”，Goldreichet al.在1997年提出“PKE and signature schemes”，Ajtai和Dwork在1997年提出“PKE scheme”；
优点：可证明安全：基于最坏情况硬度的强安全性证明；相对高效的实现；非常简单；多用途，许多先进的密码体制的提出，例如：IBE、ABE、FHE；
缺点：暂无。

现在密码学术界，对于后量子密码的方案基本上是基于哈希函数签名和基于格密码两者结合的，基于哈希函数签名用于抗量子密码体系的签名/验签，基于格密码用于抗量子密码体系的加密/解密。

三、区块链世界里的密码攻击以及量子密码破译算法

第三阶段，和大家分享一下在区块链世界里的密码攻击以及量子密码破译算法。针对现有区块链技术，攻击主要集中在四个方面：

• 第一，针对区块链基础设施的攻击；
• 第二，针对智能合约的攻击；
• 第三，针对热钱包的攻击；
• 第四，针对冷钱包的攻击，代表性的攻击事件如图所示。

目前，可用于密码破译的量子计算算法主要有Grover算法和Shor算法。

对于密码破译来说，

• Grover算法的作用相当于把密码的****密钥长度减少一半；
• Shor算法适用于解决大整数分解、离散对数求逆等困难数学问题，对目前广泛使用的RSA、EIGamal、ECC公钥密码和DH密钥协商协议可以进行有效攻击。

因此，在量子计算环境下，RSA、EIGamal、ECC公钥密码和DH密钥协商协议将不再安全。

我们设计新区块链底层的时候，着重考虑数据隔离、数据安全防护以及隐私保护方面。今天准备并不是非常充分，简单大家分享到此，非常感谢！