点击蓝字关注我们
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合数的经典算法。
这里我们试图辩解计算意义的安全性在很多现实场景下已经足够了。以下分析和估计既不严谨也不准确，只是为了大致上解释计算安全性的现实意义。以RSA加密为例，假设全球的比特币算力都用来攻击某个RSA加密，假设约为每秒270次运算，而受保护的信息的敏感期是50年，那么这段时间内大约能进行2100次运算。如果当前最高效的分解𝑛比特RSA的算法需要22𝑛13(log𝑛)23的代价，取𝑛=2048，该值已经达到了2125，不仅足够应付假设的攻击，而且还留有足够的安全边际用于应对后续可能出现的算法优化、摩尔定律等一些变数。目前，这些公钥密码算法广泛应用于网络通信的保密性和完整性保护、身份的认证和保障各类交易的不可抵赖性等应用场景，是互联网和区块链等信息基础设施的安全基础。
现代密码学的必要条件是单向函数（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]：
有意思的是，第一类的困难问题的量子困难性已经被Shor算法否定了,而第二类的基于格的密码不仅能实现传统公钥密码的几乎所有功能，也是后量子密码主流的技术路线。
格密码（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，目前主要用于构造数字签名。像我这样的理论计算机背景的人可能会（带有偏见地）认为多变量密码没有建立在一个自然简洁的（平均情况的）计算困难问题上，其安全性更有待专家和时间的检验。
美国国家标准与技术研究院（NIST)在2017年展开了后量子密码标准的方案征集，下表列出进入NIST第三轮的决赛方案（finalist）和备选方案（alternate candidate），包括数字签名与公钥加密。我们看到，格密码是后量子密码的最主流的技术路线，决赛方案中除了 “经典McEliece”（编码密码）和 “Rainbow”（多变量密码），其它5个算法都是格密码算法。最近Rainbow被发现存在现实的攻击 [29]。NIST认为长公钥、短密文的经典McEliece更适合用作特定场景的加密算法标准。通用的加密/签名的候选算法则都是由格密码组成，具体来说：Kyber、SABER和NTRU三选一作为通用加密标准，Falcon和Dilithium二选一作为数字签名标准，将在2022年3月8日召开的公钥密码年会上由NIST工作人员宣布 [30]。作为备胎，备选方案组的更加体现了 “鸡蛋不要放在一个篮子” 的指导思想，算法更加多样化，包含2个格密码算法、2个编码密码算法、2个基于哈希的签名、1个多变量签名和1个同源密码算法。总的来说，这些密码算法都是建立在底层问题的假想量子困难性（conjectured quantum hardness）之上，不能说哪个一定比另外某个更困难，只是那些相对较新的问题的安全性更有待公众和时间的检验。即使是比较主流的格密码算法，很多为了提升算法的效率和竞争力，引入了特殊的结构。同时带来的争议是这些结构是否同时也带来了额外攻击的可能性 [5]。
我国的研究人员在后量子密码也取得了较好的进展，其中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多年同态加密取得了较大的发展，逐步从理论走向应用，目前几乎所有的全同态加密都是基于格困难问题，因此全同态加密被认为天然具有抗量子计算机的安全性。
如果说全同态密码这个曾被称为 “密码学的圣杯” 已经基本到手了，那么还没完全落地的是被誉为 “密码学皇冠上的明珠” 的不可区分混淆技术 [21]。混淆可理解为将某段代码转换成为同样功能的等价代码的转换，敌手无法从代码中抽取出关于原算法有任何效信息，只能将混淆后的代码当作一个 “虚拟黑盒” 进行调用。混淆技术早已经广泛应用于软件保护，但工业界目前用的混淆技术没有计算困难性的数学理论基础，被逆向通常只是时间问题。目前我们知道能实现 “虚拟黑盒” 的通用混淆器是不存在的 [27]，混淆后能达到的安全性是因目标算法而异。不可区分混淆(Indistinguishability Obfuscation，简称为iO）是目前最主流的混淆技术，可简单理解为：如果某算法𝑓最多可以被混淆到什么安全程度，那么用iO混淆后得到的𝑓′就能达到对应程度的安全性。不可区分混淆的出现重塑了人们对密码学边界的认识，它与单向函数的组合被认为是密码完备，是理论密码的终极目标。谈到混淆绕不开的一位华人密码学家就是华盛顿大学的林蕙佳（Rachel Lin）教授，林教授10多年以来在混淆方面做出了一系列重要成果，最新的成果包括证明不可区分混淆可以基于多个标准假设 [22,23] 来构造。虽然构造出来的混淆方案还不实用，但人们开始相信不可区分混淆在经典计算模型下是存在的。由于上述构造混淆的假设并不都是抗量子的，目前还有一些基于非标准的格假设构造的不可区分方案的候选方案，其安全性有待时间的检验。此外，目前相对比较高效的抗量子不可区分混淆的候选算法还包括基于仿射行列式的混淆方案 [24]，在我们最新的研究中发现了其设计的一些漏洞并作了安全性修补的建议 [25]。
经过四十多年的发展，现代密码学已经从对数据进行加密和签名等基本密码算法的阶段逐步过渡到对区块链、数据交易和计算进行隐私保护的后量子时代。Shor算法等量子算法对密码学的冲击总体来说是有惊无险，甚至为密码的转型和发展带来了契机，以LWE为代表的格密码等后量子密码的出现顺应也进一步推动了现代密码学的发展。未来，我们期待更多的高等密码算法和协议可以逐步切换到更为高效的后量子版本，例如基于LPN等编码问题可以设计非常高效的后量子安全的多方计算协议，以及基于格或者其它后量子假设设计的不可区分混淆技术。同时，我们也看到在一些特定的场景中后量子密码已经与量子密码技术的结合应用 [15]。
作者简介
郁昱，上海交通大学计算机科学与工程系教授，目前担任亚洲密码年会指导委员会(ASIACRYPT Steering Committee)成员、国际密码学会理事会(IACR board)的观察员以及三大密码会CRYPTO 2021、EUROCRYPT (2020,2021)、ASIACRYPT (2018, 2020, 2021)，以及TCC(2017,2019), PKC(2019,2022), CCS等重要会议的程序委员会委员。
编辑：陈十九
审核：商密君
征文启事
点击购买《2020-2021中国商用密码产业发展报告》
来源：商密在线
注：内容均来源于互联网，版权归作者所有，如有侵权，请联系告知，我们将尽快处理。
原文始发于微信公众号（商密君）：郁昱：后量子时代，密码何去何从？
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论