【区块链百家讲谈】韦云川：抗量子密码技术进展综述

查看原文

其他

【区块链百家讲谈】韦云川：抗量子密码技术进展综述

Original: 韦云川链世纪财经 2019-05-16

主办方：BTRAC智库区块链百家讲谈

联合主办方：链世纪财经

信息发布方：链世纪财经

主讲嘉宾：北京理工大学韦云川博士

主持人：BTRAC智库创始人，区块链百家讲谈创始人宇鸣初

文稿编辑：链世纪财经杨小伍

区块链百家讲谈

面对量子计算机的必然到来，区块链行业已经在布局和谋划对策，越来越多的公链项目开始提出抗量子攻击的方案。比如一个低调的、名为Necto的公链项目，就提出了非常全面、具体的抗量子解决方案，并得到美国NIST密码专家的高度肯定。我们有理由相信，以Necto项目为代表的一批公链项目将会引领区块链行业迈上安全新台阶。

——韦云川

专家介绍

韦云川

北京理工大学博士、加州大学戴维斯分校访问学者，曾任职于中国航天科技集团、成都卫士通信息产业股份有限公司，曾创立北京金泰众和科技有限责任公司。在区块链技术、无线通信安全、抗量子攻击技术等领域有广泛研究和积累。

曾荣获国家留学基金委公派留学奖学金、北京理工大学人民奖学金、中国航天科技集团一院技术改进奖一等奖。学术论文曾被顶级国际会议 IEEE INFOCOM 录用并作专题报告，获得10余项发明专利授权

以下为分享主题文字内容

作者：韦云川编辑：杨小伍

前言

BitAsset Labs介绍

BitAsset Labs是由加密数字货币交易中心BitAsset发起，联合国际顶尖区块链专家、学者、技术研究人员和投资机构等共同组建的数字加密资产研究中心和孵化器。BitAseset Labs的联盟合作伙伴有Harvard University、MIT、Standford University、UC Berkeley、ConsenSys、Cryptic Labs、LemniScap等，邀请图灵奖获得者Whitfield Diffie、Silvio Micali以及诺贝尔经济学奖获得者Eric Maskin等顶级科学家组成BitAseset Labs的专家智库，旨在建立产业界、学术机构和投资机构的一体化创新平台，为全球顶尖项目提供人才、社区、资金、战略等系统支持，帮助优秀区块链项目的孵化和落地，加速区块链的生态系统建设。

本次交流的目的

区块链技术(BlockchainTechnology)的学术名称：

DistributedLedgerTechnology(DLT)。

DLT的本质是账本，特点是分布式，核心是共识，基础是密码。

本次交流从密码讲起。以下是提纲：

密码技术发展历史

1.1古典密码

从古代到19世纪末的手工密码阶段。这个时期由于生产力水平低下，密码形式还处于比较低级的阶段，比如象形文字就可以看作是一种原始的密写术。我们称这个时期的密码体制为“古典密码体制(classical cryptography)”。古典密码体制主要有两大类，移位密码(transposition cipher)和替换密码(substitution cipher)。它们都可以利用“手工作业”进行加解密处理，与此对应的密码分析也基本上是“手工作业”。

举例：比如A部落给B部落传递一个信息M，为了不让敌方部落获悉信息。A部落先用一块布缠绕在一根特定尺寸的木头上，然后写上打算传递的信息。写完解开布，送去给B部落，并让可靠的信使告诉B部落木头的尺寸。B部落用相应尺寸的木头，把写了秘密的布缠绕上去，即可解读正确的信息。敌方部落截获了这块布，因为不知道用什么尺寸的木头进行缠绕，就难以破译信息。

从现代密码的视角：部落间传递的信息M为明文，木头尺寸为密钥，写上信息的布为密文。

古典密码编码方法归根结底主要有两种，即置换和代换。把明文中的字母重新排列，字母本身不变，但其位置改变了，这样编成的密码称为置换密码。最简单的置换密码是把明文中的字母顺序倒过来，然后截成固定长度的字母组作为密文。代换密码则是将明文中的字符替代成其他字符。

一些经典的古典密码，例如凯撒密码被用于高卢战争，采用将英文字母向前推移K位，以此字母替代明文。

在欧洲的法国外交官维吉尼亚，对贝拉索密码采用自身密钥体制，即以一个共同约定的字母作为起始密钥，以之对第一个密文脱密，得到第一个明文，以第一个明文为密钥对第二个密文脱密，此类类推，不会重复使用密钥，被后世称为维吉尼亚密码。

1.2（近代密码）机械密码

从20世纪初到20世纪50年代末的机械密码阶段，这个时期的密码技术使用的是“机械计算部件”。在这半个世纪里，由于莫尔斯(Samuel F. B. Morse)发明了电报，利用电磁波进行通信己成为一个必然的趋势。为了适应电报通信，密码设计者设计出了一些采用复杂的机械和电动设备来进行信息加解密处理的方法。我们称这个时期的密码体制为“近代密码体制”。近代密码体制己被证明是不安全的，但是要想破译它们往往需要很大的计算量。

Enigma转轮机代表了机械密码发展的一个顶峰，但是在第二次世界大战中服役的Enigma却被完全破译。

典型代表：Enigm轮转机

1.3（现代密码）电子密码

从1949年开始的电子密码阶段。自从1949年香农(Claude E. Shannon)发表了划时代论文《保密体制的通信理论》之后，随着电子技术的发展，电子密码走上了历史舞台，催生了“现代密码体制”。特别是20世纪70年代中期，美国联邦数据加密标准密码算法(Data Encryption Standard, DES)的公开，以及公共密钥(public key)思想的提出，极大地促进了现代密码学的蓬勃发展。但是，广泛使用的“电子密码”的安全性大多没有得到完备性证明。

里程碑：

1949年香农(Claude Shannon)《保密系统的通信理论》，为近代密码学建立了理论基础。
1976年Diffie和Hellman发表的文章“密码学的新动向”一文掀起了密码学上的一场革命。
1978年，R. L. Rivest，A. Shamir和L. Adleman实现了RSA公钥密码体制。
1969年，哥伦比亚大学的Stephen Wiesner首次提出“共轭编码”(Conjugate coding)的概念。
1984年，H. Bennett和G. Brassard在次思想启发下，提出量子理论BB84协议，从此量子密码理论宣告诞生。其安全性在于：1、可以发现窃听行为；2、可以抗击无限能力计算行为。
1985年，Miller和Koblitz首次将有限域上的椭圆曲线用到了公钥密码系统中,其安全性是基于椭圆曲线上的离散对数问题。
1989年R. Mathews, D. Wheeler, L. M. Pecora和Carroll等人首次把混沌理论使用到序列密码及保密通信理论，为序列密码研究开辟了新途径。
2000年，欧盟启动了新欧洲数据加密、数字签名、数据完整性计划NESSIE，究适应于21世纪信息安全发展全面需求的序列密码、分组密码、公开密钥密码、hash函数以及随机噪声发生器等技术。

量子计算机的威胁

2.1现代密码学基石

现有的几乎所有的密码都是建立在一种类似单向函数的假设上的，也就是说我们需要寻找一个函数，它的计算复杂度是多项式时间可计算的，而他的反函数的计算复杂度不是多项式时间可计算的，例如RSA算法所基于的大数分解问题，ECC基于的离散对数问题，这些问题的解决难度都是要用“非确定性图灵机”在多项式时间内计算的问题，属于NP问题。而这两个公钥算法利用的则是基于这两个困难问题的单向陷门函数来实现的。而在量子计算条件下，部分NP问题有多项式时间的算法，也就是说这种一边儿是P问题，一边是NP问题的函数不再是单向函数了，即这些密码算法就无法使用了。

2.2对公钥密码体制的影响

在1994年，Peter Shor开发了一种用于整数分解的量子算法（Shor算法），该算法在多项式时间内运行，因此能够破坏任何RSA或离散的基于对象的密码系统（包括那些使用椭圆曲线的密码系统）。

对于量子计算机而言，所有广泛使用的公钥密码都是不安全的。

有人说：把RSA的长度从1024加到2048比特甚至更长，不就安全了吗？答案是：对于现有的经典计算机和算法，这样是可以的。但对于量子计算机和算法，这是徒劳的（除非RSA的长度增大到1GB或更长。但这样的话，算法还能用吗？）

2.3对对称密钥体制的影响

第二个是Grover的算法，它能够在O（√n）时间内反转函数。该算法会通过根因子降低对称密钥加密的安全性，因此AES-256只能提供128位的安全性。类似地，找到256位散列函数的前映像只需要2128次。由于将哈希函数或AES的安全性提高两倍并不是非常繁琐，因此，Grover的算法不会对对称加密造成严重威胁，但是会降低安全性。

后量子时代的来临

3.1后量子密码是什么

在2015年，美国国家标准技术研究院(NIST)发布了一份后量子密码报告，对公钥密码算法的换代工作以及后量子子密码算法研究工作产生了极大的推动作用。NIST的后量子密码报告强化了量子计算机出现的预期，同时NIST也开始在全球范围内开展后量子密码算法标准的征集工作。2019年1月30日，NIST启动了第二轮征集工作。

后量子密码，是能够抵抗量子计算机对现有密码算法攻击的]新一代密码算法。所谓“后”，是因为量子计算机的出现，现有的绝大多数公钥密码算法（RSA、Diffie-Hellman、椭圆曲线等）能被足够大和稳定的量子计算机攻破，所以可以抵抗这种攻击的密码算法可以在量子计算和其之后时代存活下来，所以被称为“后”量子密码。也有人称之为“抗量子密码”，说的都是一个意思。

3.2后量子密码算法基本要求

安全

运行速度快

通信开销合理

更广应用场景

3.3主流后量子密码算法

基于编码的密码

基于编码的公钥密码体制利用纠错码对信息进行编码，并添加足够的随机错误信息，使得信息无法被攻击者破译，而接收方通过私钥进行纠错，最终恢复出原始信息。

基于格的密码

格密码主要用于构造加密、数字签名、密钥交换，以及众多高级密码学应用，如：属性加密(Attribute-based encryption)、陷门函数(Trapdoor functions)、伪随机函(Pseudorandom functions)、同态加密(Homomorphic Encryption)等，尽管格子密码系统的优化和安全性证明都需要极其复杂的数学，但基本思想只需要基本的线性代数，后量子性基于格上的一些困难性问题，如最短向量问题(shortest vector problem，SVP)、最近向量问题(closest vector problem，CVP)、SIS(small integer solutions)问题、LWE(learning with errors)问题，能抗量子计算机攻击。目前以1996年提出的NTRU(Number Theory Research Unit)公钥密码体制最具影响力。

以下是格的定义：

MQ密码体制。它的安全性基于有限域上非线性方程求解的困难性，代表方法/算法：HFE (Hidden Field Equations)、Rainbow(Unbalanced Oiland Vinegar(UOV)方法)、HFEv-等。

基于哈希算法的签名

哈希签名使用哈希函数的输入作为密钥并输出作为公钥。这些密钥仅适用于一个签名，因为签名本身会显示密钥的一部分。基于散列的签名的极端低效导致区块链使用Merkle树来减少空间消耗（是的，比特币中使用的相同Merkle树）。

不幸的是，用哈希构造KEM或公钥加密方案是不可能的。因此，基于散列的签名不是完整的后量子密码学的解决方案。而且，它们不是空间有效的;一种更有前途的签名方案SPHINCS产生41kb的签名和1kb的公钥/私钥。另一方面，基于散列的方案非常快，因为它们只需要计算散列函数。它们还具有极强的安全性证据，完全基于存在具有抗冲突和抗图像抗性的散列函数的假设。

由于没有任何迹象表明当前广泛使用的哈希函数（如SHA3或BLAKE2）容易受到这些攻击，因此基于哈希的签名是安全的。

基于超奇异椭圆曲线上的同源问题的密码

在椭圆曲线加密中，我们使用Diffie-Hellman类型协议来获取共享秘密，但是我们不是将组元素提升到某个幂，而是遍历椭圆曲线上的点。在基于同源的密码学中，我们再次使用Diffie-Hellman类型协议，但我们不是通过椭圆曲线上的点遍历，而是通过一系列椭圆曲线本身。

与其他后量子方案相比，基于同源的密码学具有极小的密钥大小，仅使用330个字节用于公钥。不幸的是，在这篇文章中讨论的所有技术中，它们是最慢的，对于密钥生成和共享秘密计算都需要11-13毫秒。然而，他们确实支持完美的前向保密，这不是其他后量子密码系统所拥有的。

基于辫群(braidgroups)的密码

辫群引起密码学学者兴趣的一个主要原因是其上有许多“难解”的数学问题，这些问题有的可用于构造新的密码体制，现在主要介绍涉及到的3类：(1)扭结共轭搜索问题(2)根搜索问题(3)子群成员判断问题

格密码体制与近期研究进展

4.1基于格的零知识证明

零知识证明是证明者向验证者证明某个命题的真伪，但不泄露其他的任何信息.它可以用到密码学的很多领域，是格密码近期研究的热点问题。

基于格的零知识证明在加密、可验证加密和群签名等密码方案的应用方面，明文知识证明得到越来越多的关注。

目前的技术手段一般有2种思路:

1）在格困难问题中采用Stern的方法来构造，然而，利用该方法构造的方案效率较低.这是由于每轮协议有2/3的错误概率，因此要达到128比特的安全性，需要重复执行192次。

2）结合Rejection Sampling引理，利用Fait-Shamir技术。一般情况下，该方法下的协议每轮有1/2的错误概率，但由于该方法比Stern有更多的代数结构。因此，近几年的主要进展都是基于该方法之上的。

目前基于格的零知识证明发展较快，基于LWE或ring-LWE构造高效的，且最好没有异常终止的零知识证明将会是今后研究的重点内容。

4.2基于格的加密

主要有2条技术路线。一类是对NTRU加密系统的改造。2011年，Stehle和Steinfeld首次对NTRU进行了成功改进，将方案的语义安全规约到了ring-LWE问题的困难性假设。在PKC2017会议上，有学者讨论了在素分圆环上的NTRU加密方案，得到一个标准模型下IND-CPA安全方案，其安全性可规约到理想格上的最坏情况的困难问题；这个方案比2011年Stehle的环更容易控制而且能抵御子域攻击。另外，基于素分圆环构造加密方案更接近原始的NTRU加密系统。

2018年底，一个名为Necto的区块链公链项目基于NTRU加密系统进行了改进，也得到一个标准模型下IND-CPA安全方案。

另一类是应用LWE和ring-LWE问题构建某些特殊加密方案，如谓词加密(Predicate Encryption)、基于属性加密(Attribute Based Encryption, ABE)、可验证加密等。2014年亚洲密码年会Benhamouda等提出的零知识证明能够改进基于ring-LWE的加密方案；2017年欧洲密码年会Lyubashebsky等人提出利用明文知识证明构造了一个可验证加密方案。总之，利用格构造各种特殊的加密方案是格加密的重要发展趋势。

4.3基于格的数字签名

近2年格上数字签名的研究成果，基本是利用Fiat-Shamir变换这种思路构造高效安全的签名方案这种思路的构造一般要经历如下过程:困难问题→抗碰撞Hash函数→一次签名→身份认证协议→数字签名。

目前主要的有效的解决途径主要有2种方法:第一是采用Aborting技术，主要思想是签名者可以有选择性的输出签名，以保证签名不包含私钥的任何信息，第二是Rejection Sampling引理。

近几年来，格上数字签名主要以上述2种方法为基础来构造高效安全的签名方案。在CT-RSA2014上，Bai和Galbraith在生成签名的过程中，先用rounding算子对承诺值v的比特取高位，也就是扔掉一些最不重要的比特位，然后再取它与签名消息μ的Hash值c，然后根据上述方法即可得到一个基于LWE的短签名方案。

构造高效的格签名的思路比较单一，如何丰富格签名的构造将会是一个有趣的方向。另外，相比较于传统的签名方案，格签名的签名长度还有待于缩短，这也是格签名进一步研究的方向。

4.4基于格的密钥交换

对于基于格的密钥交换协议的构造，近几年出现许多优秀成果。一种思路是根据Diffie-Hellman密钥交换协议的想，直接由LWE问题直接构造，关键问题在于密钥共识。一种思路是Robust Extractor；另一个较为常用的思想是Peikert在2014年提出的Reconciliation技术。

总结与思考

本次交流简述了密码技术的发展史，分析了量子技术对密码学存在的威胁以及这种威胁出现的技术依据，综述了基于不同的底层数学问题的多项式时间的难解性提出了不同的后量子密码学思路，重点分析了基于格的密码体制在零知识证明，加密，签名，密钥交换等方面的应用以及主要问题。

最后，感谢大家宝贵的时间。