后量子密码学研究思考与实践
中国电信翼付后量子加密研究思考与实践
2022年10月，法国物理学家阿兰·阿斯佩克特、美国理论与实验物理学家约翰·克劳瑟和奥地利科学家安东·蔡林格共同荣获诺贝尔物理学奖，以表彰三位通过实验证实了“幽灵般的超距作用”的物理学家。爱因斯坦描述的纠缠粒子”。随着量子计算、量子通信、量子密码等技术的不断发展，量子技术近年来进入公众视野并受到广泛关注。量子研究正在稳步向前发展，成熟。
作为量子领域最关键的应用之一，量子计算机具有运行速度快、解决特定问题能力强的特点。因此引起了国内外众多学者和技术研究机构的关注，发展尤为迅速。自20世纪80年代初，美国物理学家保罗·贝尼奥夫首次提出量子计算概念，并用经典类比设计出可执行的量子图灵机以来，包括中国、美国、英国、日本在内的许多国家都相继宣布，在量子计算机理论和工程领域取得了巨大进展。
图www.sychzs.cn量子处理器发展路线
量子计算机的出现和发展虽然极大提升了计算性能，但也对个人和企业的数据隐私带来了现实的安全威胁。根本原因在于，当前大多数密码算法，如Diffie-Hellman（DH）、RSA、ECC等，其安全性都是基于传统数论问题，如离散对数和大整数分解整数分解问题。到了量子计算时代，这些问题都不再“困难”。事实上，
同时，由于目前互联网广泛使用的安全协议和密码系统大多是基于DH、RSA、ECC等经典算法设计和构建的，当这些底层算法在网络中不再安全时，面对量子计算机，这些协议和系统所保护的敏感数据面临被破坏的风险。
图 2. 后量子密码学迁移时间表
应对量子计算机对数据安全带来的挑战的有效途径是完成算法和协议的后量子（抵抗量子计算机攻击）密码学迁移（Post-Quantum Cryptography-PQC Migration），即，将目前使用的所有基于密码学的传统数论问题的公钥密码算法转换为抗量子计算攻击的后量子密码算法版本，使其能够高效运行在传统计算机在有效时间内抵抗量子计算机攻击。 。目前，学术界和工业界对后量子密码算法的研究已经持续多年。主流的后量子密码算法类别包括：
1）基于哈希的密码系统，其中Merkle设计的Hash-Tree公钥签名方案是此类密码的典型方案；
2）基于编码的密码系统，例如McEliece设计的“Hidden-Goppa-Code”公钥加密方案，以及我国王新梅教授的新梅方案[4]；
3）基于格的密码，基于格谜题的密码算法目前吸引了越来越多的关注。早期格密码的典型代表是著名的NTRU方案；
4）基于多元的公钥密码学，如Matsumoto于1988年设计的多元加密和签名方案；
5）基于超奇异同源的算法，提供了一种基于特殊椭圆曲线代数结构的后量子密钥交换算法；
6）其他密码算法，如基于零知识证明的ZKP、分组密码算法AES256等
量子计算机的威胁不是一个迫在眉睫的问题，而是一个持久的问题。攻击者可以通过公开通道提前获取并存储大量经经典加密系统加密的密文，等待足够强大的量子计算机出现。破解，即“现有方案”（Store Now and Decrypt Later-SNDL）攻击。 2022 年 5 月发表在《后量子密码迁移指南》杂志上的《后量子密码迁移指南》[3]》中，对 SNDL 攻击和后量子密码学迁移时间线（图 2）进行了解释。可以说，后量子密码学的迁移是一项长期工作，需要尽早规划、尽早完成，确保个人、企业乃至国家核心数据的安全。量子时代。
目前对传统基于数论的密码系统构成威胁的攻击算法主要有两种：Shor算法和Grover算法。前者可以解决
Shor算法：由Peter W. Shor提出，它利用量子叠加位来高效计算离散傅立叶变换（DFT），使得量子计算机下降到\(O(log ^2 N) \)。利用这一特性，Shor算法可以有效地解决有限交换群的隐子群问题（HSP），进而解决大整数分解和离散对数问题以及解决现有的公钥如RSA、DH、和ECC。加密系统构成严重威胁。
Grover算法：又称量子搜索算法，由Lov K. Grover于1996年提出。该算法基于量子叠加态和量子相位干涉原理。与传统搜索算法相比，可以以快平方倍的速度在无序序列中搜索特定数字。 Grover的算法主要针对传统密码学中的对称加密算法或哈希函数。目前已知的针对对称加密算法AES和安全哈希函数的攻击方法的复杂度为\(O(N)\)。使用 Grover 算法，在量子计算机上进行相同的攻击需要 \(O(N^{1/2} )\) 的复杂度。因此，只需增加加密算法的安全参数即可。后量子安全，比如使用AES512代替AES256，或者将Sha-3的输出长度加倍等
综上所述，后量子密码迁移的关键是替换易受Shor算法影响的公钥密码算法，例如RSA和ECC。目前比较常见的解决方案是使用格密码算法或者基于哈希的后量子数字签名系统。
此类密码系统的安全性可以简化为向量空间上的计算难题。比如最短向量、最近邻搜索等。格密码的优势主要是在性能方面，可以与经典的公钥加密系统相媲美，因此可以用来实现更复杂的密码协议，比如同态加密以及安全的多方计算协议。然而，点阵密码需要仔细选择安全参数以确保安全。
定义：
格是维欧几里得空间的线性独立向量组 \(b1,b2,…,bn\)（称为格基）的所有整数系数的线性组合。相同的网格可以用不同的网格基来表示。 m称为晶格的维数，n称为晶格的秩。当m=n时，二维晶格及晶格基如图2所示。
图 3. 二维晶格示例
如图3所示，(V1，V2)，(V1'，V2')是二维晶格的两组晶格基。 (V1',V2')趋于正交，称为优质底座(V1,V2)之间有小角度，称为劣质底座。
网格上的难题：
？ ？该向量确定的向量V'=Σi Ci bi 最接近目标向量V。在足够复杂的空间中，CVP问题是一个NP-hard问题。格密码算法所基于的难题通常是Learning With Error-LWE。 LWE问题的输入是矩阵A和向量v，v=As+e。很难从中恢复。 LWE问题可以简化为上述SIVP问题。
基于Ring-LWE问题的简单密码方案：
a) 密钥生成：公钥记为(a,b=as+e)，私钥记为s。 a、b、s、e都是多项式，s、e的系数比较小。
b) 加密：将待加密的消息记录为{0,1}系数多项式m，随机选择系数较小的三个多项式r、e1、e2，计算密文(c,d )，其中 c=ar+e1，d=br+e2+m(q-1)/2。
c) 解密：通过d-cs恢复m。如果d-cs的第i个系数更接近0，则令m的第i位为0；如果d-cs的第i个系数更接近(q-1)/2，则设m的第i位为1。【通过判断每一位得到整个消息】
正确性验证：
\(d-cs=br+e2+m(q-1)/2-(ar+e1)s=er+e2-e1s+m(q-1)/2\)
如果m的第i位为0，那么d-cs的第i位就是er+e2-e1s的第i个系数，且r、e1、e2都是多项式系数相对较小，所以结果接近 0；如果m的第i位为1，那么d-cs的第i位就是多项式er+e2-e1s加上(q-1)/2的第i个系数，结果为更接近 (q-1)/2。
以上是一个简单的格公钥密码方案。除了前面提到的需要精心选择安全参数来保证格上数学问题的难度外，还需要选择合适的参数来保证算法的正确性。
数字签名与公钥加密不同，过程中可能存在信息丢失。在传统计算机中，数字签名的存在相当于单向函数的存在。由于可以将哈希函数视为任意布尔电路，进而将其安全性降低为NP完全问题，因此理论上可以通过哈希函数构造出足够安全的数字签名算法。
Lamport一次性签名解决方案
？ ,x_1^1),(x_0^2,x_1^2),...,(x_0^t,x_1^t)←{0,1}*\).对于所有\(a∈{0,1},i∈[t]\)，计算公钥\(y_a^i=h(x_a^i)\) 。输出密钥对\((sk,pk)←({x_a^i},{y_a^i}),a∈{0,1},i\in [t]\)。b) 签名：定义\(m_i\)是消息\(m\)的 \(i\)
c) 验证：验证\(y_{m_i}^i=h(x_{m_i}^i))\)。
以上签名方案只能签名一次。这是因为： 如果得到两个相差超过 1 位的消息签名，则可以构造第三个合法签名，从而破坏了签名方案的不可伪造性。 。但结合 Merkle 树，可以将一次性签名方案扩展为多重签名方案，并且可以预设允许签名的数量，如图 3 所示。
图 4. Merkle 签名图
如图4所示，假设要对消息\(m_{19}\)进行签名，采用某种一次性签名方案对\(m_ {19}\) 在之后，从节点19到根节点1的路径上所有相邻节点的私钥可以一起输出为完整的签名，即\(K_{18},K_8 ,K_5,K_3\)。在签名验证过程中，联合计算并验证两个子节点对应的签名是否与父节点对应的签名匹配，直至验证根节点\(K_1\)。
此外，后量子安全密码算法还包括多变量加密系统、基于椭圆曲线同源的系统、基于编码的加密系统等。 然而，这些加密系统有的性能较差且不实用，有的无法简化为经典的计算难题，因此并未成为主流的后量子密码选择。
上述算法一定是抗量子的吗？现在看来是的，但将来不一定。就像RSA提出后不久就出现了很多攻击方法一样，RSA算法本身也在不断改进。经过行业学者的大量研究和评估，很可能发现某些算法不安全。例如，基于超奇异同源性的密钥封装SIKE算法就被发现是不安全的。那么为什么我们需要进行后量子迁移呢？通过更早布局后量子密码学的迁移，数据可以更早实现后量子安全。就像RSA算法一样，即使目前使用的方法不是那么完美，但随着不断改进，最终也会成熟。一般来说，一个基本的密码算法从被提出到在业界得到广泛应用，需要大约20年的验证和改进。然而，随着量子计算时代的加速，后量子密码学迫切需要尽快成熟。并替换现有的密码系统。目前，通过上述方法（如格子、哈希等）构建的算法极有可能成为量子时代的标准密码算法。
美国国家标准与技术研究院（NIST）于2009年发布后量子密码算法综述，2012年正式启动后量子密码算法标准项目，并于2017年发布后量子密码算法征集公告2016年，相关评估工作分为三轮进行，每轮耗时约18个月，预计2024年之前完成。初步征集共收到文件82份。经过同行间长时间的评估和算法攻击，发现很多算法是不安全的。 2022年7月，NIST公布了四项将冲破重围并进行标准化的算法提案，包括密钥封装算法CRYSTAL-Kyber，以及三种数字签名算法CRYSTAL-Dilithium、Falcon和SPHINC+。同时公布了四种第四轮候选密钥封装算法：BIKE、McEliece、HQC和SIKE算法（图5）。然而，比利时鲁汶大学团队最近发表的一篇论文提出，SIKE算法的SIDH安全假设在某些情况下是可以被破解的。
图5. NIST 2022年公布的标准算法和候选算法
2022年2月，美国宣布《关键和新兴技术清单》，将后量子密码学作为量子信息技术纳入国家安全考量范围。 2022年5月，《》杂志发表的《后量子密码迁移的指导综述》指出，由于SNDL攻击的存在，向落后量子密码学的迁移是现在就必须开始的事情。美国互联网工程任务组（IETF）也在开发改进的传输层（TLS）协议，以适应后量子密码算法。知名咨询公司 Gartner 预测，20% 的组织将在 2023 年开始为后量子密码学迁移做准备。
国家信息基础设施安全是国家安全的核心关键环节。从近期西北工业大学遭遇美国国家安全局袭击事件来看，美国正在对我国关键设施进行全面的网络渗透和信息窃取，极有可能存储了大量数据使用传统数论密码学（RSA、ECC）进行加密。该数据可用于解决现有的SNDL攻击，这势必对我国信息安全造成重大安全风险。加快我国后量子密码的标准化和迁移已成为保障我国国家信息安全的关键。
中国密码动物学会于2019年发起密码算法大赛，征集一系列后量子密码算法。其中，LAC算法成功获奖，进入NIST第二轮后量子密码候选算法名单。清华大学丁锦泰教授提出的Rainbow算法成功加入NIST第三轮最终算法。但在激烈的同行评审中，两者都被发现容易受到攻击。此外，中国密码动物学会还举办了量子密码学年度学术会议。除了学术界对后量子密码技术的研究和探索外，中国企业对后量子密码标准化研究和早期工程化工作的重视还不够。 。整体来看，目前业界对后量子安全的研究维度并不高。只有少数公司开始推动后量子密码迁移，包括在软件协议层面的小规模尝试，以及从硬件芯片层面加速后量子密码的运行效率。从安全性角度评估现有的后量子算法。此外，一些区块链公司也开始关注后量子区块链技术，以保证量子计算时代链上数据的安全，比如如何实现多量子计算等技术的抗量子能力和能力。 -签名、环签名、门限签名和零知识证明。链的整合和算法的替换。
易支付作为中国电信互联网金融和科技战略的重要板块之一，积极推进后量子密码迁移的理论研究和工程实践。如图6所示。
图6.中国电信在后量子安全领域的探索工作
标杆NIST后量子标准化进程已进入最后阶段，但从SIKE算法被攻破的案例来看，尚不清楚仍在标准化进程中的算法是否足够安全。鉴于当前算法安全性的不确定性，电信团队并未直接开展核心算法的后量子密码迁移项目。而是采用了基于“国密SM系列算法+PQC后量子候选算法”融合的方法进行探索，遵循的思路是只要国密算法或者PQC算法之一没有被破解，攻击者无法破解融合密码算法。同时系统预留了标准化接口，为后续转换为国内后量子标准算法留下了可扩展、可插拔的灵活空间。
易付宝综合考虑后量子安全和迁移对量子计算机时代数据安全融合的影响和意义，将后量子安全和迁移工作从特定的密码算子拓展到包括隐私计算和区块链。的多个领域。综上所述，后量子安全领域的布局可分为硬件层、传输层、基础算法层、高级算法层和应用层（图6）五个维度：
1）在硬件层面，积极探索软硬件结合的方式，例如后量子+隐私计算一体机，提升后量子密码的效率和安全性算法；
2）在传输层，采用后量子+国密融合方案替代传统的Diffie-Hellman协议，逐步重构TLS/SSL作为底层数据加密通信协议；
3）在基础算法层，提供四个基础密码模块，为上层高级算法和应用层提供基础能力，包括密钥协商、公钥加密、数字签名和国密+邮政。量子混合密钥策略。这些基础算法的设计遵循标准化和可插拔性的思想。一旦最新研究发现某个算法的安全性比较弱或者已经被攻破，可以快速更换新的安全算法；
4）在高级算法层面，推广使用后量子密码算法，改进隐私计算中的各种上层算法，让参与者在不暴露自己数据的情况下实现后量子安全数据集成。 。例如，重构并实现后量子安全Oblivious Transfer-OT协议，并基于其构造后量子安全隐私查询方案（OT-》PIR）；替代VOLE算法和ECDH算法为了抵抗量子密码算法，实现后量子安全的私有集交集（PSI）协议；另一方面，设计了基于格公钥密码学的多方自定义计算方案；而在联邦学习中，格-基于同态加密算法替代了传统的Paillier算法，此外还部分设计并实现了抗量子环签名、群签名算法和抗量子零知识证明协议，以提高区块链在量子计算中的安全性时代；
5）在应用层，通过底层的后量子密码能力，为上层数据集成和应用提供抗量子密码分析和攻击的能力，包括但不限于数据流通、数据存储、和金融对策。诈骗、暗推理、电子支付等
量子计算技术的研发和后量子密码学的标准化是长期任务。由于基于上述工作的后量子算法仍处于标准化进程中，仍有大量的研究和验证工作需要学术界和工业界共同完成。因此，中国电信推动的后量子技术研究和工程化工作主要以积累实践经验和储备技术人才为主。相关技术成果并未直接应用于现有生产业务系统。 相关研发工作与国家、集团级重大科研项目和产业应用紧密结合，为后量子迁移工作提供了丰富的实践场景验证环境。
随着数据隐私保护监管政策和法律法规的逐步收紧，数据安全已成为国家安全、社会安全、经济安全、金融安全的重要支柱。为了保证数据隐私合规，实现跨域融合，最大化释放数据价值，隐私计算、区块链、可信执行环境等技术系统的深入研究和开发具有重要意义。密码学作为核心技术基础，安全性极高。对于数据安全来说更为重要。
量子计算机技术的快速发展，推动了现代密码学从简单的数据加密、签名等基础算法向通过数据元素融合实现全流程隐私保护的后量子时代转变。虽然基于数论问题的传统密码算法受到了量子计算机的极大挑战，但以格密码为代表的后量子密码算法进一步推动了现代密码学的发展。如何将目前广泛使用的密码算法迁移到更安全的后量子版本，如何将后量子安全算法与隐私计算、区块链、大数据AI、网络和数据安全等新一代信息技术相结合，并基于它们进行构建更加安全高效的安全协议是后量子时代密码学工作者和研究机构需要关注的核心问题之一。确保我国关键基础设施长期安全也是一项重大任务。
[1] IBM 推出 400 Qubit-Plus 量子处理器和下一代 IBM 量子系统二号 (2022)。网址：https://www.sychzs.cn/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two
[2] 严鲍，等。 “在超导量子处理器上使用亚线性资源分解整数”。 arxiv(2022), 2022.12372.
[3] 约瑟夫，大卫，等人。 “将组织过渡到后量子密码学。”自然 605.7909 (2022): 237-243.
[4]王新梅. “基于纠错码的数字签名方案。”电子通讯 26.13 (1990): 898-899.
[5]卡斯特里克、沃特和托马斯·德克鲁。 “针对 SIDH 的高效密钥恢复攻击（初步版本）。”密码学 ePrint 档案 (2022)。
