密码体制如何应对“量子霸权”？

量子计算（Quantum Computing）以量子比特为基本单元，通过量子态的受控演化实现数据的存储计算，具有经典计算无法比拟的信息携带能力和并行处理能力。量子计算机的原理架构示意图如图1所示。

由于量子叠加态的存在，与经典比特相比，量子比特可携带更多的信息。

量子叠加：在无外界观测干扰时，一个量子系统可以处在不同量子态的叠加态上，即著名的“薛定谔的猫”。

量子比特（Qubit）：一个量子比特可以表示0、1或0和1的叠加，因此其搭载的信息量远超只能表示0或1的经典比特。

一个n经典比特存储器只能存储2^n种可能的n比特数中的一个，而一个n量子比特存储器可以同时存储2^n个数，且其存储信息的能力随n的增加而指数上升。

由于量子叠加效应，量子计算过程中的幺正变换可以对处于叠加态的所有分量同时进行操作。因此，量子计算机可以同时进行多路并行运算，这也是量子计算机超强信息处理能力的源泉。

在经典计算中，所谓并行性只是对一个确定的状态进行分时处理。在量子计算中，由于量子比特的叠加态特性，可对所有可能状态进行同时处理。

量子计算自概念诞生起发展至今经历了理论探索、算法研究、技术验证等阶段，具体如图2所示。

2019年，谷歌宣布实现所谓的“量子霸权（Quantum Supremacy）”，即量子计算机拥有一项超越经典计算机的计算能力，其使用更稳定的53量子比特可编程超导处理器仅用200秒就完成了随机量子线路采样任务，而超级计算机通常需要上万年的时间才能完成。但是，由于计算功能局限性等因素，谷歌是否真正实现了“量子霸权”受到了包括IBM在内的业界质疑。

需要注意的是，以上所述量子比特数量指的都是物理比特。由于噪声的存在以及物理比特的不稳定性，需要约800个物理比特的冗余纠错才能实现1位逻辑比特，而目前没有任何一家机构能实现1位逻辑比特的编码。

1）Grover算法

量子计算中的Grover随机数据库搜索算法能够以“指数减半”的效果提升空间搜索效率。对称密码的安全性如果以穷举搜索密钥的攻击复杂度进行衡量，将导致对称密码的安全性减半，即在经典计算环境下2^128安全的对称密码算法，在量子计算环境下只有2^64安全。

影响：量子计算可使DES、AES、SM4等分组密码算法和流密码算法的安全性降低为原来的1/2。但由于Grover算法需要指数级内存，其对于对称密码算法的实际影响不大。

2）应对策略

增加密钥长度：为了达到2^128的量子计算安全，需将对称密码的有效密码尺寸设计为至少256比特。需要注意的是，密钥长度增加对加解密运算速度有影响，但影响可控，从密钥长度128bit的约450MB/s降低至密钥长度256bit的约320MB/s。

1）量子随机行走算法

量子随机行走算法可提高经典搜索算法的时间效率，进而增加一定时间内随机找到两个碰撞原像的概率，实现对抗碰撞性的暴力破解，降低哈希摘要算法的安全性。

影响：量子计算可使MD5、SHA、SM3等哈希摘要算法的安全性降低为原来的2/3。

2）应对策略

增加摘要长度：量子计算对哈希摘要算法的影响不大，只需采用摘要长度较大的算法即可。

1）Shor算法

Shor量子算法可以在多项式时间内破解大整数分解问题和离散对数问题。破解2048比特强度的RSA密钥可能需要经典计算机耗费10亿年以上的时间，而谷歌称2000万量子比特的量子计算机只需8小时就可破解2048比特RSA算法。

影响：量子计算可破解RSA等基于大整数分解的公钥密码算法和ECDSA、SM2等基于离散对数的ECC椭圆曲线公钥密码算法。

2）应对策略

更换新的算法：大整数分解和离散对数困难问题在量子并行计算环境下可被轻易破解，因此可考虑选取无法高效并行计算的数学困难问题构造抗量子公钥密码算法。

各类密码算法在经典计算环境和量子计算环境的安全级别对比如表1所示。

1）美国

2015年8月，美国国家安全局（NSA）宣布将美国政府使用的密码套件进行安全性升级，用于2015年至抗量子密码算法标准正式发布前的过渡期，如表2所示。

2016年4月，美国国家标准与技术研究院（NIST）公布了抗量子密码标准化计划:

截至目前，NIST抗量子密码算法征集的实际进展如图3所示。

NIST共收到82个算法，首轮公布前即淘汰了13个算法。在剩下的69个候选算法中，2019年初第二轮仅剩26个有效候选算法，其中17个为公钥加密与密钥协商算法，9个为数字签名算法。

与RSA等传统非对称密码算法同时支持加密与签名等功能不同，抗量子密码体制对公钥加密/密钥协商算法和数字签名算法进行分别构造。

2）欧洲

2015年3月，欧洲电信标准协会ETSI成立“量子密码安全工业标准工作组”，主要负责抗量子密码算法的征集、评估和标准制定。同年，欧盟相继启动抗量子密码算法项目PQCRYPTO和SAFECRYPTO。

欧洲在抗量子密码算法方面的策略是全力配合美国NIST的算法征集，并基于NIST的算法推动抗量子密码迁移工作。

3）亚洲

中国、日本、韩国等国家于2016年开始组织“亚洲抗量子密码论坛”，分别在中日韩三国举办。

在国内，中国密码学会于2019年开展了全国密码算法设计竞赛，在征集到的算法中不乏抗量子密码算法。据报道，中国或将于2022年左右开展抗量子密码算法标准化工作，于2025年左右实现应用落地。

由于现有非公钥密码算法存在可抵抗量子计算攻击的版本，因此抗量子密码主要讨论的是公钥密码体制在量子计算下的替代方案。

1）抗量子密码定义

抗量子密码体制也称为后量子密码体制（Post-Quantum Cryptography），是指既能抵抗现有经典计算攻击又能抵抗未来量子计算攻击的密码体制，至少应满足以下要求：

一些困难问题无法利用量子离散傅里叶变换解决，如格上的最短向量问题（SVP）/最近向量问题（CVP）、非线性方程组求解问题、背包问题等，可考虑基于此类问题构造量子密码算法。

2）抗量子密码分类

抗量子密码算法包含基于格的密码、多变量密码、基于Hash的密码、基于编码的密码等类型，具体如表3所示。

在NIST抗量子密码算法征集的第二轮26个算法中，有12个基于格的密码、7个基于编码的密码、4个多变量密码、2个基于Hash的密码、1个超奇异同源密码。其中，基于格的LAC算法由国内的中科院信工所研究团队提交。

3）基于格的密码

基于格的密码（Lattice-Based Cryptography）是目前抗量子公钥密码算法中最具代表性的一类。格是一种与群、环、域并列的代数结构，LWE（带错误的学习）是格上的困难问题。2005年，Regev提出LWE问题并通过量子算法将LWE归约到格上的最短向量困难问题（SVP），并给出了基于LWE的公钥密码方案。与之前出现的格上困难问题比较，LWE在构建密码系统时更方便。

Ring-LWE（环上带错误的学习）是LWE的变体。在基于Ring-LWE的密码中，密钥由若干个多项式表示，而不是LWE中的矩阵，因而减小了密钥大小，同时提高了加解密速度。

4）各类抗量子密码特点

基于格的密码、多变量密码、基于Hash的密码、基于编码的密码等各类抗量子密码算法的特点如表4所示。

表4：各类抗量子密码特点

虽然“量子霸权”还未真正意义上实现，但为了未来能够快速向后量子密码体制迁移，业界在布局长期应用时需要考虑后量子密码算法的兼容性。