- 路献辉副研究员
随着量子计算技术的不断进步，基于经典计算复杂性理论的现有密码算法安全性受到了严重威胁，制订下一代抗量子计算的密码算法标准已经成为保障未来量子计算环境下网络空间安全的重要任务。为支撑我国后量子密码算法标准的研制，DCS中心（全称为“中国科学院数据与通信保护研究教育中心”）密切跟踪并参与了相关国际进展，主要包括NIST的后量子密码算法标准征集活动（提交了候选算法LAC，已进入第二轮评估）、欧洲ETSI的量子安全会议（应邀作大会报告介绍中国后量子密码技术进展）、ISO\IEC的后量子密码算法研究项目（作为章节编辑参与SD8项目）等。
后量子密码算法设计与分析理论是否已经成熟？
目前量子计算对密码算法最大的威胁是Shor算法对基于因子分解和离散对数困难问题的公钥密码算法的破解。因此，目前国际上对后量子密码算法的研究主要集中在公钥密码领域。在公钥密码领域除了工业界熟悉的RSA和ElGamal两个类型的密码算法之外，还有许多其他的类型，其中有五种类型的公钥密码算法尚未发现有效的量子计算攻击，它们被统一称为后量子密码算法，包括：格密码、基于编码的密码、多变量密码、基于散列的数字签名、同源密码。这些密码算法中基于编码的密码和基于散列的数字签名已经有40年的研究历史，多变量密码已经发展了30多年，格密码和同源密码已经发展了20多年。这些密码算法的设计与分析理论已经取得了许多成果，在量子计算复杂性分析方面尚未完全成熟，经典安全性和效率已经接近实用化需求。在国际标准化需求的大力推动下有望在未来3-5年内取得较大发展，最终形成实用化的密码算法标准。
可以攻破RSA的量子计算机什么时候可以制造出来？
按照最原始的Shor算法估计，破解1024比特的RSA算法需要1024*3个量子比特的通用量子计算机。根据公开的数据，目前技术进展最顺利的超导量子计算机还停留在20-70个量子比特之间，而且尚未完成纠错和全纠缠等运行Shor算法需要的功能。提升量子比特的数目、量子纠错、量子比特的全纠缠都带来巨大的技术挑战。因此，目前尚无法精确预测量子计算机什么时候能够真正破解RSA。然而，密码算法的生命周期非常长，例如根据欧盟的标准数据需要50年的保密期，再考虑到制订和推广密码算法标准需要5-10年时间，因此我们需要考虑的是量子计算机60年之后是否可以破解RSA。如果我们回忆一下60年前的状态，你会发现60年可以发生太多变化。这就是欧美等国家决定启动后量子密码算法标准征集的原因。
NIST的后量子密码算法标准征集
美国NIST于2009年发布了后量子密码算法的综述，2012年正式启动后量子密码算法标准项目，2016年发布后量子密码算法征集公告，评估工作分为3轮进行，每轮18个月左右，预计2024年之前完成。鉴于后量子密码算法包含多种类型且尚未完全成熟，为了更好的促进后量子密码算法设计理论的发展，本次征集不会像之前一样推出一个胜选算法，可能会推出两个算法集合，一个集合满足工业化应用需求，另一个集合继续研究。单纯从技术角度而言，这种用十多年时间精心打造密码算法标准的模式值得我们借鉴。截止到2017年11月30日，NIST共收到来自全球的82份提案，经过审查有69个算法符合要求进入第一轮评估，2019年初发布了进入第二轮评估的26个算法。第二轮的26个候选算法中包括12个格密码，7个基于编码的密码，4个多变量密码，2个基于散列（分组码）的密码，1个同源密码。欧洲是NIST后量子密码候选算法的最大来源，其中整合了欧洲多个高校和公司力量的PQCRYPTO项目主导和参与了26个密码算法中的15个，整个欧洲主导和参与的则达到了20多个，其中有很多算法是欧洲和美国之间合作设计。除欧洲、美国、加拿大之外，其他进入第二轮的只有DCS中心设计的LAC算法。
ETSI的量子安全计划
欧洲在后量子密码算法方面的策略是全力配合美国NIST的算法征集，并基于NIST的算法推动技术、标准、服务、市场的全链条后量子密码迁移工作。2013年欧洲电信标准化协会(ETSI)启动了量子安全会议来推动后量子密码算法迁移工作。需要指出的是，ETSI的量子安全技术包含了后量子密码（PQC）和量子密钥交换（QKD）,其目标是融合PQC和QKD共同打造未来的量子安全技术体系。欧洲整合了多个高校和公司的研究力量积极参与NIST的后量子密码算法征集工作，2015年启动了全球后量子密码算法旗舰项目PQCRYPTO和后量子密码算法应用项目SAFCRYPT，2018年启动了后续的PROMETHEUS项目。
ISO/IEC的后量子密码算法研究项目
美国NIST除了自己征集后量子密码算法标准之外还在国际标准化组织ISO/IEC的密码工作组JCT1/SC27/WG2主导启动了后量子密码算法研究项目SD8。目前该项目的主要工作是撰写后量子密码算法研究报告，共分为6个部分，其中第一章为整体介绍，第二章为基于散列的数字签名技术，第三章为格密码，第四章为基于编码的密码，第五章为多变量密码，第六章为椭圆曲线超奇异同源密码。DCS中心派出专家负责第三章格密码研究报告的撰写。除了SD8,DCS中心还派出了多名专家参与SM4,ZUC等我国商用密码算法的国际标准化推进工作。从时间上推算，美国NIST是在自己征集算法标准的同时在ISO/IEC开展同步推广工作，这一模式非常值得我们借鉴。
IETF的后量子密码算法草案
在所有5个类型的候选算法中，基于散列的数字签名算法是安全性分析最成熟的算法，也是工业标准化进展最快的算法，XMSS算法已经在2018年成为RFC8391。从技术角度看，虽然数字签名属于非对称算法，但是与公钥加密和密钥交换不同的是其可以基于单向函数构造，即数字签名可以直接基于对称密码算法或散列函数构造。其基本设计思想是基于单向函数构造一次性数字签名算法，然后基于Merkle提出的哈希树技术将一次性数字签名转换为标准的数字签名算法。如果使用哈希函数作为底层的单向函数，上述框架可以基于哈希函数设计数字签名算法。基于该框架的数字签名算法结构清晰，且不需要数学困难问题，不存在被量子计算攻破的风险，是目前安全性最好的后量子密码算法。
我国的后量子密码算法技术发展
当前，我国已在积极推进现有商用密码算法标准SM2,SM3,SM4,SM9,ZUC等成为国际标准，为一带一路计划提供国际化安全标准支撑。后量子密码算法标准的制订工作是我们迎头赶上国际先进水平的机会，为了充分调动国内研究力量投入下一代密码算法标准设计工作，我国已经面向全国启动了密码算法设计竞赛活动。DCS中心已经积极动员起来，共提交了5个密码算法参与国内的密码算法设计竞赛。
声明：本文来自中科院DCS中心，版权归作者所有。文章内容仅代表作者独立观点，不代表安全内参立场，转载目的在于传递更多信息。如有侵权，请联系 anquanneican@163.com。
