导 读
2022年2月8日,美国白宫总统行政办公室发布了最新修订的《关键和新兴技术(CET)清单》,后量子密码作为量子信息技术的一种也被列入了这个对美国国家安全战略具有潜在影响的清单。虽然看不懂这波操作,但像我这样人畜无害的理论工作者也大受震撼(颇有些蹭到热度的鼓舞)。
量子计算机是近年来一个时髦的话题,其计算能力较经典计算机有多大优势也是当前热门的研究方向。抛开量子计算机何时能够实用的争议,本文主要谈一下量子算法对现代密码学产生的影响以及后量子密码可能的发展方向。文中大多是常识性的内容,其它主观的观点受个人研究方向和知识储备的限制,难免有失偏颇甚至存在谬误,旨在抛砖引玉,供大家参考,同时也希望借此机会激励对理论计算机科学和密码学有兴趣的同学投身相关的研究。
撰文 | 郁昱(上海交通大学计算机科学与工程系教授)
古典密码学
密码学(cryptography)是研究如何保护信息在传输、存储和计算等过程中保密性(confidentiality)、完整性(integrity)、不可抵赖性(non-repudiation)、真实性(authenticity)等安全属性的一门学问。以发信为例,保证信件内容在传输过程中没有被他人偷窥是确保信息的保密性;确保内容没有被篡改则属于完整性保护;如果发送者在信中做了某些承诺,不可抵赖性确保其有履行承诺的义务;信件的真实性保证了收信人可确信信件的确是发信人写的(没有被冒名顶替)。自古以来在较长的一段时间内密码主要用于军事用途和信息的保密性保护,该时期的密码称为古典密码(classical cryptography),如罗马时期的凯撒密码(Caesar Cipher)和二战期间德军的恩尼格玛密码机(Enigma machine)。古典密码大多数属于对称密码范畴,如图1所示,双方都必须提前在安全的环境下共享一个密钥(secret key)用于此后在非安全的环境下的信息保护。信息论的创始人香农证明了如果对称加密要达到无条件的安全性,那么被加密的消息长度不能超过密钥长度。密钥安全分发的前提假设大大限制了对称密码的应用场景,而古典密码尝试用短密钥加密长消息的挑战因为安全性问题绝大多数以失败告终。
现代密码学
1976年 Whitfield Diffie 和 Martin Hellman 提出了密钥交换协议,1977年 Ron Rivest、Adi Shamir 和 Leonard Adleman 提出了RSA公钥加密,开创了现代密码学的新时代,他们也因这两项成就分别获得了2015年和2002年的图灵奖。密钥交换协议和RSA加密都属于公钥密码,它们不再要求发送方和接收方提前安全地共享密钥:双方可通过密钥交换协议从无到有建立一个共享密钥用于对称加密,或者如图2所示直接利用接收方公钥给他发加密的消息。然而,公钥密码不再具有信息论意义上的无条件安全性,而只是计算意义上安全。计算安全是指密码算法的安全性基于某个计算困难问题,比如 Diffie-Hellman 密钥交换协议的安全性可以近似(实际上不等价)理解为是基于 “离散对数” 问题的困难性:随机选取????∈????????,给定????(????)=????????mod????无法高效地算出????,其中????是某个????阶的乘法循环群的生成元;而RSA问题也可近似理解成随机选取两个等长的质数????和????,从????(????,????)=????⋅????分解出????和????是非常耗时的。这里引入安全参数????来描述问题的规模和困难性,例如RSA问题中????是要分解的合数????⋅????的长度,显然它的安全性最多也就是指数级的2????(????),而实际上还存在亚指数时间分解RSA合数的经典算法。
现代密码学的必要条件是单向函数(one-way function)的存在性。????为单向函数包含两层含义:计算????是容易的,而求逆计算????−1是在平均情况下是困难的(average-casehardness)。单向函数是否存在目前没有定论,它的存在蕴含了P≠NP,因为计算????−1也是NP问题。为了保住饭碗我们通常假设单向函数是存在的,上述的RSA问题和离散对数问题都可以抽象为单向函数的候选。单向函数要求平均情况的困难性,通俗的说,即99.999…%的(随机选取的????和????)问题实例中计算????−1都是困难的,这与最坏情况的困难性(worst-case hardness)有本质区别。换句话说,密码学很难直接建立在NP困难问题之类的假设上,因为即使P≠NP,NP完全问题也只保证了最坏情况下的困难性(如只有1%的问题实例是困难的,剩下都是容易的)。实际上,RSA公钥加密也可抽象为另一类特殊的单向函数,叫做陷门单向置换(trapdoor one-way permuation)。这里的加密算法????????:M→C和解密算法????−1????:C→M作用在同一个空间上(M=C),因此构成了两个互为逆的置换。掌握公钥(可简单理解为????=????⋅????)的可以得到加密算法????????,但没有办法有效逆推出私钥(可认为是????和????),而只有对于掌握陷门(私钥)的人来说解密操作????−1????才是可行的。
量子算法的密码优势
上述RSA等经典密码算法的计算意义安全性是建立在图灵机或与其等价的经典计算机模型基础上的。到了上世纪90年代,Peter Shor 提出了的量子算法(被称为Shor算法)可在多项式时间内解决有限交换群的隐藏子群问题(Hidden Subgroup Problem,简称HSP),该问题涵盖了RSA公钥加密、Diffie-Hellman密钥交换和椭圆曲线密码等常见公钥密码的底层问题。换句话说,如果一定规模的量子计算机成为现实,那么当前互联网和区块链广泛使用的公钥密码体系都不再安全。除Shor算法外对密码学有影响的量子算法还包括:
1 Grover量子算法该算法解决的无结构搜索问题可以抽象如下:点函数????:{0,…,????−1}→{0,1}只在某个点????取值为1,其余取值均为0。经典算法需要????(????)次询问????才能找出????,而Grover算法只需要????(????‾‾√)次操作便可以常数概率给出问题的解。该问题涵盖了密码中的密钥恢复、函数求逆等主要的攻击方式,较经典的暴力搜索实现了二次加速。此外,基于Grover算法还能在????(????1/3)代价内查找到密码哈希函数ℎ:{0,1}∗→{0,…,????−1}的碰撞[6],相较于经典的生日攻击算法????(√N)实现了1.5次加速。
2 Simon算法与Shor算法的原理类似(实际上后者是受前者启发)可用于寻找一些函数中的隐藏周期。最近的工作将Simon算法用于攻击对称分组密码的某些操作模式 [2]。
总的来说,Grover算法与Simon算法主要针对对称密码,其对对称密码的影响在可控范围内。为应对Grover算法,我们可将密码算法的安全参数(如密钥长度)加倍,达到与经典模型下同等的安全等级;对于Simon算法,我们可规避受到其影响的操作模式,使用量子模型下安全的操作模式。因此,量子算法对对称密码的影响较小,而Shor算法对现有的一些公钥算法的影响是致命的。目前,量子计算机还没有发展到可以分解比如RSA-1024合数的规模和量级,但密码学界已经未雨绸缪,开始准备应对后量子时代的密码危机。我们所说的后量子密码或者抗量子密码主要是指设计仍然能够运行在经典计算机上且具备抵抗量子计算机攻击安全性的密码算法和协议。
量子算法是否将终结现代密码?
就计算能力而言,量子计算机可高效解决的问题类是经典计算机对应类的超集,记为????⊆????????????(任何经典计算机可以高效解决的问题,量子计算机同样可以轻松解决)。然而,量子计算机较经典计算机的加速优势究竟有多少,目前还没有一个全面完整的答案。一方面,以上列出的是目前针对密码有加速优势的几乎所有量子算法;另一方面,理论计算机主流(但尚未证明)的观点认为量子计算机不能在多项式时间内解决NP完全问题(????????????≠????????)或者求逆任意的单向函数,Shor算法对于非交换群(non-Abelian group)上的HSP问题就不管用了,更不用说一般的NP问题。因此量子计算机没有从根本上否定现代密码学的根基。
哈佛的Boaz Barak教授将公钥密码的底层问题分成了两大类 [3]:
1. 代数:RSA和离散对数等
2. 几何:格和编码问题,如图4中的(近似)最短向量问题、(近似)最近向量问题等

格密码(lattice-based cryptography)基于格问题的困难性,如近似最短向量问题(GapSVP)等。格相关的数学问题历史悠久,最初格被用作某些密码问题(如分解RSA合数)的分析工具 [9],直到Miklós Ajtai [10] 发现格问题也可以用来构造密码算法。格密码是密码学历史上一个比较重要的发现,在此之前,人们认为最坏情况的困难性(如NP困难问题、GapSVP问题等)不足以支撑设计密码算法所需的平均情况的安全性。为此,MiklósAjtai引入了平均情况困难的小整数解(ShortInteger Solution,简称SIS)问题,并证明了格上某些问题的最坏情况困难性蕴含了SIS问题平均情况的困难性,而SIS问题可用于构造密码哈希函数、身份认证和数字签名等密码方案。另一个与SIS问题对偶的重要工作是Oded Regev [12]提出的容错学习(Learning with Errors,简称LWE)问题,LWE不仅具有格问题的最坏情况到平均情况的(量子)归约,而且可以用来构造后量子加密算法,以及诸如全同态加密 [7] 和不可区分混淆 [8] 等高等密码算法,Oded Regev因此项工作获得了2018年的哥德尔奖(G?del prize)。最后,另一类比较有代表性的格密码算法是由Hoffstein、Pipher和Silverman于1996年提出的NTRU公钥密码体制 [13],但其困难性没有建立在标准的格问题之上,而算法设计者在当时选择非常超前的商业化路线,各种开公司、申请专利、开发周边产品的运作,其前景一度不被学界看好。但多年以后再回顾,基于NTRU格的公钥加密算法的安全性的确经历了时间的考验。
编码密码(code-based cryptography)基于编码译码的困难性。信息论中信道编码的目标是设计高效的冗余编码,以对传输过程中信道引入的错误进行纠错,实现正确的译码。在研究过程中人们发现一些编码的译码是(最坏甚至平均情况下的)计算困难问题。然而,这样的 “失败的编码” 在密码学中找到了用武之地,其译码的困难性可用来构造安全的密码算法。编码问题是与格问题非常相关的一类问题。例如格上的最短向量等问题在编码里都有对应的问题,LWE问题也是受到了随机线性译码问题的启发,编码问题与格问题有类似的表现形式(如矩阵向量相乘),目前量子算法在解决这两类问题上相较经典算法并不具有太多加速优势。
其它后量子密码还包括基于哈希的签名(hash-based signature)、同源密码(isogeny-based cryptography)以及多变量密码(multivariate cryptography)等。同源密码包括超奇异同源Diffie-Hellman(SIDH)和CSIDH等公钥密码算法,可用于当前广泛使用的常规椭圆曲线密钥交换(ECDH)的后量子替代;多变量密码是关于有限域上多元多项式的密码学,因通常使用二次多项式(multivariate quadratic)很多时候也缩写为MQ,目前主要用于构造数字签名。像我这样的理论计算机背景的人可能会(带有偏见地)认为多变量密码没有建立在一个自然简洁的(平均情况的)计算困难问题上,其安全性更有待专家和时间的检验。

我国的研究人员在后量子密码也取得了较好的进展,其中Rainbow算法 [28] 进入了NIST第三轮的决赛方案,LAC算法入选了NIST第二轮的候选算法 [14],并且LAC的公钥加密算法和密钥交换协议分别获得了全国密码算法设计竞赛的公钥密码算法组的一等奖和二等奖各一项,我参与设计的Aigis [16] 公钥加密和签名算法也获得了该设计竞赛的两项一等奖,其它获得竞赛二等奖的算法还包括SIAKE认证加密协议 [17]、SCloud [18]和ACKN [19]。值得一提的是,在全国密码算法设计竞赛公钥组一二等奖的获奖算法中,除了SIAKE是同源密码,其它都属于格密码算法,这与NIST后量子密码算法征集第三轮决赛算法中格密码占比绝大多数也是一致的。
后量子数字签名
数字签名可用于在数字世界中替代手写签名。在现实世界中,签名首先认证了签名者的身份,同时在文件上签名表达了签名者对于这份文件内容的认可(不可否认性)。为实现以上功能,要求签名者的签名能够被大家验证认可,而难以被他人伪造。数字签名是手写签名在数字世界的对应,如图5所示,签名者可用持有的私钥对消息签名,完成了签名者身份与所签名消息的绑定,其他人可用其公钥验证签名的合法性,但无法推断出私钥或伪造签名。数字签名是公钥加密之外后量子密码的另一类重要的密码原语,广泛应用于公钥密码体系、网上银行、电子支付、数字钱包和区块链交易等场景。
与数字签名紧密相关的一类密码原语是哈希函数(杂凑函数)。简单地说,哈希函数是将任意长度的消息映射到固定长度输出的映射?:{0,1}?→{0,1}??。关于?的碰撞是指一对不同的消息映射到同一个输出,即??≠??′:?(??)=?(??′)。哈希函数在密码原语中是一个独特的存在。它的算法是完全公开的,没有密钥或其它秘密信息。根据定义?的碰撞存在无穷多个,而哈希函数设计的主要安全目标是找到各类碰撞最有效的方法应该是(不依赖于哈希算法的)通用攻击,在经典计算机模型下通用的碰撞攻击为生日攻击,其时间代价是??(2??/2)。哈希函数的设计通常比较复杂,很难抽象为某个简洁的数学问题,目前针对哈希函数的通用量子攻击复杂度为??(2??/3) [6]。这意味着,如果??足够大,现实中包括设计者在内没人可以找到哈希函数的碰撞,而被王小云院士破解的MD5和SHA1就是反面的例子。哈希函数的一个用途是可以为任意长消息生成固定长度的简短摘要,由于寻找碰撞的计算困难性,可认为每个消息都有唯一的摘要。因此,数字签名通常会利用哈希函数先对消息取个摘要,然后对摘要签名。此外,很多的高效密码方案的设计需要用到随机预言机(random oracle)才能得到似是而非(plausible)的安全性证明,这里预言机是理想化的真随机函数,无法高效地实现,密码学家干脆直接采用哈希这样的完全确定性的函数作为随机预言机的实例替代,这个操作外行很难看懂,理论上存在重大瑕疵,但在实现中通常没有太大问题。此外,哈希函数还用于工作量证明类(如比特币)的区块链中。
数字签名从形式上看属于公钥密码范畴,但理论上只需要对称密码的最低假设单向函数就可构造数字签名,不需要RSA或者格问题等可以生成后门结构的困难问题。例如NIST第三轮备选方案中的Picnic算法只依赖于哈希函数和分组加密算法LowMC等对称密码算法,而SPHINCS+算法甚至只需依赖哈希函数。数字签名算法通常都要用到哈希函数将消息压缩为摘要,因此基于哈希的数字签名是用到密码原语最少和安全性最为保守的后量子签名。格和编码等的后量子密码通常为追求高效率会引入性能优化的新型结构或设计,与此同时带了一定的安全性不确定性和争议。而哈希函数的困难性可直接假设等同于理想的通用攻击的复杂度,其安全性并不随着设计的优化而减弱,因此基于哈希的数字签名的安全性评估相较其它签名来说更为容易。目前,SPHINCS+是基于哈希的(无状态)后量子签名最优化的代表算法,其效率的改进空间已经较少,我们最近用组合学理论进一步优化了SPHINCS+签名中的编码方案和其它组件,同等安全强度下优化后的签名大小最多可以减少10%左右 [20]。

后量子密码的发展趋势
目前NIST等机构正在标准化的后量子密码算法只包括了公钥加密和数字签名等常用的密码算法,这些算法目前趋于成熟,优化改进的余地也比较小了。实际上,基于格等困难问题还能构造全同态加密、不可区分混淆等高等密码算法。传统的加密算法,只能保护数据在存储和传输等过程中静态的安全性。数据在加密后,对密文能做的唯一有效操作就是解密。1978年 Ron Rivest 等人提出了同态加密(Homomorphic Encryption)的概念 [26]。如图6所示,同态加密允许在没有解密密钥的情况下对密文进行有意义的计算操作,最终输出加密的计算结果,整个计算过程不泄露原始数据和计算结果的任何有效信息。能支持任意计算操作的同态加密被称为全同态加密(Fully Homomorphic Encryption)。2009年 Craig Gentry 提出了第一个全同态加密算法方案 [7],最近10多年同态加密取得了较大的发展,逐步从理论走向应用,目前几乎所有的全同态加密都是基于格困难问题,因此全同态加密被认为天然具有抗量子计算机的安全性。

