谈量子计算和后量子密码学

作者：余宇（上海交通大学特约研究员，博士生导师），张江（信息安全博士）

近日，有新闻媒体报道称，量子信息/量子计算将对传统密码学（又称现代密码学或经典密码学）提出严峻挑战，甚至将其彻底颠覆。 作为密码学研究者，我们想就“量子计算VS密码学”这个问题分享一下我们的看法，并简要介绍一下我们正在进行的后量子密码学研究工作。

一、人生的“密码”

随着信息技术的发展和互联网的普及，密码学被广泛应用于网络和信息系统安全的各个方面，保护信息的机密性、完整性、不可抵赖性等信息安全的重要属性，也是一种网络空间安全的重要方面。 学科的重要组成部分[1]。 由于翻译和使用习惯，大多数人理解的密码仅限于登录各种应用账户（如邮箱、支付宝、微信等）需要输入的数字和字母组合，所以-称为密码（英文为password/passphrase））。 一般来说，密码只是用来实现服务器对用户的身份认证，但密码学的含义要广泛得多。 公交卡、二代身份证等协议需要不同密码技术的支持。

二、量子密码学对传统密码学的“威胁”

与现代密码技术相比，目前量子密码学的应用还比较少，主要包括量子密钥分发和量子比特承诺等。其中，量子密钥分发可以用来实现信息的安全传输，是目前应用最多的有关量子密码学的应用。 接下来，我们简要介绍围绕安全信息传输的传统密码系统。 经典密码系统主要由两部分组成，密钥和密码算法。 密码算法通常是公开的，密码系统的安全性仅取决于密钥的保密性。 如下图所示，在一个加密系统中，加密算法Enc和解密算法Dec都是公开的，而加密者Alice和解密者Bob分别拥有加密密钥k1和解密密钥k2，Eve是密钥传输通道上。 攻击者。 当Alice要向Bob发送数据m时，Alice使用加密密钥k1和数据m作为加密算法Enc的输入，计算出密文c=Enc(k1,m)发送给解密者Bob。 Bob收到密文c后，将解密密钥k2和密文c作为解密算法Dec的输入量子计算比特币，计算出明文m=Dec(k2,c)。

图 1. 现代加密系统工作原理示意图（黄晨阁绘制）。

根据使用密钥的不同方式，加密系统分为对称加密系统和公钥加密系统。 在对称加密系统中，加密和解密使用相同的密钥，即k1=k2，密钥是保密的。 对称加密系统主要有流密码和分组密码，其中分组密码应用较为普遍量子计算比特币，如美国著名的分组加密标准DES和AES，我国商用的分组加密标准SM1和SM4。 这类算法通常是密码学家根据现有的一些设计原理和分析方法设计的，而不是基于已知的数学和计算复杂性理论中的难题。 据我们所知，在量子计算模型下，目前对称密码系统中最高效的Grover算法只是将密钥的有效长度减少了一半。 也就是说，即使真正意义上的量子计算机能够实现，破解AES-256仍然需要2^128（即2128）的计算成本。

使用对称加密有一个前提条件，即加密者和解密者必须事先共享一个短的（例如128位）密钥，这在某些应用场景中是不现实的。 公钥加密系统的出现解决了这个问题。 最具突破性的Diffie-Hellman密钥交换协议可以保证通信双方在不共享任何机密信息的情况下建立共享密钥。 之后出现了RSA和ElGamal公钥加密，我国也有相应的公钥加密。 标准 SM2。 由于公钥类型的加密效率相对较低，在实际应用中，双方建立共享密钥后，一般会采用效率更高的对称加密算法对大量数据进行加密。 公钥加密的特点是其安全性是基于一些众所周知的计算难题，如RSA大数分解、离散对数等。目前，研究人员尚未找到解决图灵下大整数的有效方法机器型号。 分解和离散对数问题的经典算法，但在1995年，美国科学家Peter Shor给出了一种量子算法，可以在多项式时间内高效解决大整数分解和离散对数问题。 即借助量子计算机，攻击者可以高效破解RSA、Diffie-Hellman等基于大整数分解和离散对数问题的公钥密码方案。 尽管目前的量子计算机还局限于几个量子比特的原型阶段，在其上运行 Shor 算法也只能分解两位数的合数，但科学家们正在为“后量子时代”做准备。 量子信息技术对上述问题给出的解决方案是通过量子密钥分发技术在传输双方之间建立共享密钥，然后通过香农一次性一密或类似的方法对其进行对称加密，实现无条件安全。 然而，目前的量子密钥分发速率仍然是实现高速信息传输的瓶颈。 而且，与传统密码学一样，理论上可论证的安全性并不等于实际系统的安全性，密码学系统在实现时硬件和系统的非理想性也可能成为攻击者可以利用的漏洞。

3. 后量子密码学

量子算法对传统密码体制的冲击是由于量子算法在某些问题上相比经典算法具有一定的加速性（可以简单理解为量子算法具有高度的并行计算能力）。 例如，在传统计算机上需要次指数计算时间的大整数分解问题可以在量子计算机上以多项式时间解决。 然而，量子算法相对于传统算法的“指数级”加速并不适用于所有数学问题。 事实上，对于一些问题（如NP完全问题、基于格的、基于代码的、基于多元方程的数学问题），量子算法与传统算法相比并没有明显的优势。 随着秀尔算法的出现，国内外密码学家对基于格、基于编码和基于多元方程的密码方案进行了大量研究，试图设计出能够抵抗量子计算机的经典密码算法，这些研究统称为后量子密码学。 下面我们就后量子密码学中的一两个基本难题做一个简单的介绍。 这里攻击者的目标是求解如下n元线性方程组，其中系数a11,...,aqn，未知数x1,...,xn都是在GF(2)上随机选择的（即随机0 or 1), e1 ,...,eq 的位都独立服从参数 0i 等于 1，概率为 u，否则 ei 等于 0)。

本题要求在已知给定系数a11,...,aqn和结果y1,...,yq的情况下求解未知数x1,...,xn（若求解x1,...,xn , e1,...,eq 也立即可用）。 上面的问题就是著名的 Learning Parity with Noise (LPN) 问题。 当 q 远大于 n，且 u 为小于 1/2 的常数时，未知数 x1,...,xn 几乎可以唯一确定。 这个问题已经被证明在最坏的情况下是NP完全的。 即使在一般情况下，人们也没有找到解决这个问题的有效算法。 目前，渐近意义上最好的 BKW 算法需要亚指数时间复杂度，更重要的是，不幸的是，量子算法在解决这个问题上也没有任何优势。 我国学者在利用LPN[2]设计后量子对称密码算法和在特定参数设置下对LPN进行密码分析[3,4]方面取得了比较领先的成果。 我们还有一项基于 LPN 问题的标准难度设计公钥加密算法和遗忘传输协议的工作正在进行中。 OdedRegev将上述LPN问题进一步扩展到更大的素数域，即上述方程中所有的系数和未知数都是GF(p)上的元素，相关的加法和乘法都是对GF(p)的运算，其中p 是一个大素数，e1,...,eq 都独立服从 GF(p) 上的离散高斯分布。 上述推广后的问题就是著名的 Learning with Errors (LWE) 问题。 目前已知LWE在一定参数设置下可以化简为GapSVP、SIVP等格上难题（即求解LWE问题并不比求解格上难题容易），因此也是后量子安全的。 虽然 LWE 的效率比 LPN 稍低，但它具有更广泛的密码学应用。 LWE除了公钥加密外，还可以用来设计防碰撞哈希函数、全同态加密等，我国学者在这方面也有一些工作，如后量子安全高效密钥交换协议由张江等人设计。 基于可用于 TLS 协议 [5] 的 Ring-LWE。

综上所述，现代密码学并不等同于基于RSA、离散对数等少数数论难题的密码系统。 量子计算机的到来并不是现代密码学的终结。 安全的信息传输只是传统密码学的众多应用之一。 因此，量子密码不可能完全取代传统密码。 经过近20年的发展，后量子密码学的研究取得了丰硕的成果。 同时，为抵御量子计算机攻击保留了大量的密码学技术。 一些标准制定组织甚至即将开展后量子密码算法的标准化工作。 我们相信在不久的将来，量子安全（但仍然运行在传统计算机上）的密码系统可以部署到我们的日常系统和网络中，以更好地保护我们的信息安全。

关于作者：

余宇，上海交通大学特约研究员、博士生导师。 主要从事密码学基础理论研究。 2010年回国后，分别在华东师范大学和清华大学任教。 多项研究成果在三大密码学会议（CRYPTO/EUROCRYPT/ASIACRYPT）及CCS、TCC、CHES、CT-RSA、ESORICS等密码学与信息安全代表性会议上发表。 目前担任国际密码学会理事会（IACRboard）观察员，负责学会官方网站的日常管理工作。 2015年获得中国密码学会杰出青年奖。

张江，博士在信息安全方面，主要侧重于可证明安全性、公钥加密和密码协议的研究。 现任密码科学与技术国家重点实验室助理研究员。 发表了多项研究成果。 个人主页：jiangzhang.net。

参考

[1] 张焕国，韩文宝，赖雪佳，林东岱，马建峰，李建华． 《网络空间安全述评》，中国科学，第46卷，第2期：125-164，2016。

[2] 余元和约翰·斯坦伯格． “PseudorandomFunctionsinAlmostConstantDepthfromLow-NoiseLPN”，在 AdvancesinCryptology-EUROCRYPT2016 中。

[3] QianGuo, Thomas Johansson, Carl L?ndah., “Solving LPNUsing Covering Codes”。 在密码学进展-ASIACRYPT2014。

[4] 张斌, 焦林, 王明生． “求解 LPN 的更快算法”。 在密码学进展中——EUROCRYPT2016。

[5] 张江、张振峰、丁金泰、Michael Snook、Özgür Dagdelen。 “来自理想格的经过验证的密钥交换”，密码学进展 – EUROCRYPT2015。

全文下载链接：Quantum Computing VS Cryptography-v324-Duan