查看原文
其他

美国NIST公布首批后量子密码标准算法

The following article is from 信息安全与通信保密杂志社 Author Cismag





导读

随着量子计算技术的发展,相关运算操作在理论上实现从指数级向多项式级别的转变,量子计算机有望攻破现有的公钥密码体制。为应对出现的新型威胁,后量子密码(PQC)应运而生,旨在研究密码算法在量子环境下的安全性。


美国为维护国家安全,进一步抢占量子领域全球领导地位,早先于2017年开始推动PQC算法标准化研究。2022年7月5日,美国国家标准与技术研究院(NIST)宣布CRYSTALS-KYBER、FALCON、CRYSTALS-Dilithium等4个项目提前入选其PQC项目标准化算法结果,并宣布BIKE、Classic McEliece等4个候选算法进入下一轮算法筛选。这一里程碑事件标志着NIST PQC标准化工作经过6年的发展即将进入最后阶段。



01背景


(一)量子计算给现有密码体制带来的威胁与日俱增

近年来量子计算取得多项重大突破,IBM、谷歌、微软公司等多家科技巨头公布量子计算发展路线图,密集推出革命性量子硬件、软件,种种迹象表明量子计算正逐步迈入规模化应用阶段。在百万比特级加密量子计算机的冲击下,现有公钥密码体制(如RSA、ECC及DH密钥交换技术)都将被完全破解,对称密码算法(如AES、SHA1、SHA2等)的安全性将被显著降低。网络攻击者可利用量子计算机轻松打破世界上任一数字防御系统、破解公钥密码系统,进而对国家安全造成严重威胁。

(二)美国政府积极引导传统密码体制向后量子密码过渡

为应对量子计算发展给国家安全带来的威胁,美国政府密集出台一系列应对量子技术风险相关政策法案(如表1),进一步加快PQC技术布局,推动PQC技术遴选和标准化工作。相关法案指出联邦政府现有的信息系统需要向PQC技术迁移,政府和产业界需要优先开发可以容易升级到PQC的应用、硬件和软件。

表1.美国PQC迁移相关政策

为此,美国国家网络安全卓越中心(NCCoE)于2021年8月正式启动PQC迁移项目,邀请各部门、企业撰写PQC迁移意向书,描述产品和技术性内容,从而为PQC迁移项目提供安全平台支持和演示;7月5日当天,美国网络安全和基础设施安全局(CISA)宣布建立PQC计划,将向后量子加密过渡确定为网络安全愿景的优先事项。

(三)借力学术、产业界开展后量子密码研发及应用测试

美国《国家战略计算倡议战略计划》强调通过“整体型政府与工业界、学术界共同建立高性能计算系统的跨机构战略远景和投资”。美国政府积极联合学术界、产业界开展PQC技术和产品研发,积极进行多场景抗量子密码应用测试,推出相关商业服务和升级产品等。例如,2022年7月,后量子安全公司QuSecure宣布产品QuProtectTM基于Kyber标准算法建立量子安全通道,实现100%正常运行时间保护美国政府空域的加密通信和数据;2022年4月,韩国移动运营商LG Uplus推出了世界上首个后量子密码专线服务,可以实现对量子计算网络攻击的有效防御;2021年8月,德国慕尼黑工业大学研究人员设计生产了一种基于RISC-V技术的PQC芯片,旨在展示其阻止黑客使用量子计算机解密通信的能力。



02美国后量子密码标准进展


2016年12月,NIST正式面向全球征集具备抗击量子计算机攻击能力的新一代PQC算法,以期逐渐取代以经典RSA为代表的不可抗量子计算机攻击的公钥加密算法,并最终成为标准化加密算法。PQC算法评估工作分为三轮进行,每轮18个月左右,预计2024年前完成。

PQC标准化算法筛选只选择了无状态数字签名、非对称加密和密钥封装机制(KEMs)两种密码体制,并将算法安全性、效率和性能、其他因素(如知识产权要求、实施难度)作为评估标准因素。

(一)PQC标准化项目进程

1.第一轮筛选结果

2017年12月,NIST公布PQC标准协议的第一轮预选结果,期间共收到82个基础方案,筛选收录63个完整方案,其中包括44个非对称加密和KEMs方案及19个数字签名方案。

表2.NIST第一轮标准方案情况表

2.第二轮筛选结果

2019年1月,NIST公布PQC标准协议的第二轮预选结果,共计26个算法进入下一轮进程,其中包括17个非对称加密和KEMs方案(BIKE、Classic McEliece、CRYSTALS-KYBER、FrodoKEM、HQC、LAC、LEDAcrypt、NewHope、NTRU、NTRU Prime、NTS-KEM、ROLLO、Round5、RQC、SABER、SIKE、Three Bears)及9个数字签名方案(CRYSTALS-DILITHIUM、FALCON、GeMSS、LUOV、MQDSS、Picnic、qTESLA、Rainbow、SPHINCS+)。

表3.NIST第二轮标准方案情况表

3.第三轮筛选结果

2021年1月,NIST公布的第三轮审查共有7个算法入围,其中包括4种非对称加密和KEMs(Classic McEliece、CRYSTALS-KYBER、NTRU、SABER)及3种数字签名算法(CRYSTALS-DILITHIUM、FALCON、Rainbow)。此外,NIST还保留了8个备选算法,包括5种备选公钥加密和密钥生成算法(BIKE、FrodoKEM、HQC、NTRU Prime、SIKE)和3种数字签名算法(GeMSS、Picnic、SPHINCS+)。

表4.NIST第三轮标准方案情况表

4.标准化算法结果

2022年7月5日,NIST公布提前选中并将进行标准化的算法,其中包括用于非对称加密和KEMs的CRYSTALS-KYBER、用于数字签名的CRYSTALS-Dilithium、FALCON及SPHINCS+。其中,NIST推荐CRYSTALS-Kyber算法用于保护通过公共网络交换信息的通用加密,推荐其余三种算法用于身份认证。以上四种算法均在2024年之前支持NIST未来的加密标准。

此外,NIST推荐将BIKE、Classic McEliece、HQC、SIKE算法进入第四轮筛选进程。

(二)标准化算法情况

1.非对称加密和密钥封装机制(KEMs)

CRYSTALS-Kyber是基于格理论的PQC算法,其安全性基于假定的硬件模块的容错性学习 (MLWE) 问题。在保障安全性的同时兼具加密密钥相对较小、交换数据量小、运行速度快的特点。同时,Kyber的硬件、软件及混合设置、抗侧信道攻击等性能在同类型算法中位于前列,专利障碍问题较少,在未来具有较大的使用前景。

2.数字签名

Crystals-Dilithium是基于格理论的数字签名方案,其安全性依赖于MLWE和模块短整数的强度解决问题 (MSIS) 并遵循Fiat-Shamir与中止技术。该算法在密钥和签名大小方面具有强大而平衡的性能,并且密钥生成、签名和验证算法的效率在实际验证中表现良好。

Falcon是一种利用“散列和符号”范式的基于格的签名方案,其安全性依赖于短整数解(SIS)问题在NTRU格算法上的难度,以及随机预言机模型 (ROM) 和QROM 中的安全证明递减。该算法提供了最小的带宽,提供非常好的整体性能。

Sphincs+是一种基于散列的无状态签名方案,其安全性依赖于关于底层散列函数安全性的假设。该算法提供了可靠的安全保证,但会导致性能上的巨大成本。NIST 将该算法视为极其保守的选择,同时也是标准化算法中的唯一哈希算法,成为其余格密码受威胁背景下的备选方案。

表5.NIST标准化算法数字签名方案比较表



03影 响


一)格密码将成为后量子密码中的主流路线

PQC算法中,格密码算法可在安全性、公私钥大小、计算速度方面达到较好的平衡。同时在相同安全强度下,格密码的公私钥大小比其他三种(编程密码、多变量密码、哈希密码)方案更小,计算速度更快且更适用于多应用场景。在NIST公布的4种标准化算法中就包含3个格密码,足见其巨大潜力。美国家安全局网络安全局(NSA CSD)指出,基于格的加密方案进行参数化可保证安全,该密码方案是当前最高效的后量子算法。该机构预计,基于NIST筛选的格密码算法将被批准用于国家安全系统(NSS)。

(二)短期内将开发和使用混合密钥协议

目前,NIST选定的PQC标准化算法只包括了公钥加密和数字签名两种常用的密码算法,但这些算法已趋于成熟,优化改进余地较小。短期内,PQC算法要与传统安全密码技术结合形成一种“混搭”模式以适用当前的安全需求。亚马逊AWS公司首席安全官指出,混合密钥交换方案在实际应用中具有广泛的前景,其中ECDHE+Kyber混合方案的性能最佳。

(三)标准化后量子算法已开启商用化应用

新型密码体系的成熟离不开企业界的长期测试研究与商业应用。西方多家科技巨头既是PQC算法的设计者,又是应用落地的催化者。当前,PQC标准算法已然开启商业化应用,部分企业将PQC标准算法集成至公司产品中,进一步提升其安全性能。例如Cloudflare公司将CRYSTALS-Kyber与其他PQ算法集成到其加密数据库CIRCL;Crypto Quantique公司推出CRYSTALS-Kyber算法的后量子物联网安全平台。



END往期推荐:




隐私计算头条周刊(7.17-7.23)


一文带你走进量子计算


《隐私计算应用研究报告(2022年)》:2025年隐私计算市场规模将达到145.1亿元


招标 | 近期隐私计算项目招标15(多方安全计算、数据运营、Saas服务)


开放隐私计算社区征稿啦!

热门文章:




姚期智院士:数据、算法、算力为何是数字经济核心技术?


后量子时代,密码何去何从?


清华大学张超:实现数据确权与保护,数据密态渐成行业共识


如何在保障数据安全的前提下,充分发挥电力数据的经济价值?


未来十年,将会有95%的企业采用隐私计算技术


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存