公钥密码安全强度刻画概述.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(5):879896密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]公钥密码安全强度刻画概述*林 申1,陈 洁1,王陆平2,31.华东师范大学 软件工程学院 上海高可信计算重点实验室,上海 2000622.苏州科技大学 电子与信息工程学院,苏州 2150093.江苏省电梯智能安全重点建设实验室,常熟 215500通信作者:陈洁,E-mail:S080001e.ntu.edu.sg摘要:安全强度是对密码方案安全性的量化指标,代表了攻破某密码方案所需的计算开销.公钥密码方案的安全强度与构建该方案所依赖的困难问题和具体的参数有关.随着后量子密码学的发展,原先单一的安全强度评估标准产生了变化和扩充.因此,系统性总结数论体系下的经典公钥密码和抗量子攻击的后量子公钥密码的安全强度具有重要意义.本文首先介绍了经典公钥密码和后量子公钥密码的安全强度定义.然后给出了一些经典公钥密码方案的安全强度和后量子公钥密码方案的安全强度级别.接着从常见密码方案的现实应用出发,介绍若干在商用安全服务中使用的公钥密码方案及其安全强度分析.最后,给出本文的总结,并根据目前公钥密码安全性研究和应用的不足,对未来的研究和应用提出了展望.关键词:安全强度;经典公钥密码;后量子公钥密码;商用密码中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000643中文引用格式:林申,陈洁,王陆平.公钥密码安全强度刻画概述J.密码学报,2023,10(5):879896.DOI:10.13868/ki.jcr.000643英文引用格式:LIN S,CHEN J,WANG L P.Survey on public key cryptography security strengthJ.Journalof Cryptologic Research,2023,10(5):879896.DOI:10.13868/ki.jcr.000643Survey on Public Key Cryptography Security StrengthLIN Shen1,CHEN Jie1,WANG Lu-Ping2,31.Shanghai Key Laboratory of Trustworthy Computing,School of Software Engineering,East China NormalUniversity,Shanghai 200062,China2.School of Electronic and Information Engineering,Suzhou University of Science and Technology,Suzhou215009,China3.Jiangsu Key Laboratory for Elevator Intelligent Safety,Changshu 215500,ChinaCorresponding author:CHEN Jie,E-mail:S080001e.ntu.edu.sg*基金项目:国家重点研发计划(2018YFA0704701);国家自然科学基金(61972156);NSFC-ISF 联合科学研究计划(61961146004);上海市教育委员会科研创新项目(2021-01-07-00-08-E00101);江苏省高等学校基础科学(自然科学)研究面上项目(22KJB520035);“江苏省电梯智能安全重点建设实验室”开放课题(JSKLESS202104);江苏省计算机学会教学类专项(JSCS2022049)Foundation:National Key Research and Development Program of China(2018YFA0704701);National Natural Sci-ence Foundation of China(61972156);NSFC-ISF Joint Scientific Research Program(61961146004);Innovation Programof Shanghai Municipal Education Commission(2021-01-07-00-08-E00101);Natural Science Research Project of Uni-versities in Jiangsu Province(22KJB520035);Open Project of Jiangsu Key Laboratory for Elevator Intelligent Safety(JSKLESS202104);Special Teaching Project of Jiangsu Computer Society(JSCS2022049)收稿日期:2022-09-19定稿日期:2023-04-17880Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023Abstract:Security strength is a quantitative indicator of a cryptography schemes security,rep-resenting the computational cost required to break the scheme.The security strength of a publickey cryptography scheme corresponds to the hard problem that it is based on and the selection ofscheme parameters.With the development and enrichment of the post-quantum cryptography,theoriginal security strength evaluation standard has been changed and expanded.In order to summa-rize the security strength of classical public key cryptography based on number theory problems andpost-quantum public key cryptography based on mathematical hard problems which are difficult tosolve even for quantum computers,this paper first introduces the definition of security strength ofclassical and post-quantum public key cryptography,then introduces the security strength of sometypical classical and post-quantum public key schemes.After that,the security strength analysis ofthe public key schemes implemented in commercial security services is proposed.Finally,accordingto the shortcomings of the current research and application of public key cryptography,some futureresearch directions are put forward,and the conclusion of this paper is given.Key words:security strength;classical public key cryptography;post-quantum public key cryptog-raphy;commercial cryptography1引言现代公钥密码方案的安全性是建立在困难性问题假设上的,具有可证明安全性(provable security),即:若求解该问题假设是困难的,则称该公钥密码方案是安全的.这也是公钥密码学与对称密码学在本质上的一大不同.公钥密码方案的安全性与困难问题假设的种类紧密相关,按困难问题对公钥密码方案进行分类也是一类常见的分类标准.如图1所示,现存的公钥密码方案可大致分为两类:基于经典数论问题的方案和基于抗量子攻击困难问题的方案.经典数论体系下公开的公钥密码方案以 1976 年提出的 Diffie-Hellman 密钥交换算法1为开端,可根据嵌入困难问题的不同分为三类:即基于大整数分解问题、基于离散对数问题和基于椭圆曲线问题的方案.然而,随着量子计算机的出现,经典公钥密码体制的安全性受到了极大的挑战.Shor 算法的提出,使得破解 RSA、DSA、ECDSA 算法成为了可能2.因此,抗量子攻击的新密码方案在近些年应运而生,被称为后量子密码.相似地,根据困难问题的不同,可将常见的后量子密码分为五类:基于格问题、基于编码问题、基于哈希函数问题、基于超奇异椭圆曲线同源问题和基于多变量二次方程组问题的方案.由于方案安全性的内核和攻击者的能力都有本质不同,经典公钥方案和后量子公钥方案的安全性评估标准和结果都有明显的区别.图 1 根据困难问题分类的公钥密码方案Figure 1 Public key cryptography schemes classified according to difficult problems安全强度在密码方案的实例化中具有非常重要的意义,具象的安全标准对方案参数的设置有很强的导向作用.譬如,在基于配对的密码方案的实例化中,Costello 等人提出,BLS24 椭圆曲线(嵌入度/安全乘数 k=24 的 Barreto-Lynn-Scott 曲线3)非常适合构造 192,224,256,288 和 320 位的安全强度较高林申 等:公钥密码安全强度刻画概述881的配对方案4.此外,同族中 k=12 的 BLS12 椭圆曲线非常适合构造 192 位安全的配对.在后量子密码方案的实例化中也是如此.2022 年郝世迪等人提出了一种基于模格 MLWR 密钥封装的参数优化,针对NIST 后量子标准化选定的 Saber 方案的三种变体都提出了一组新参数,使其在安全强度、错误率和带宽方面获得了更好的平衡,特别是针对参数更为轻量级的变体 LightSaber 方案的新参数,使其在保持相当于 128 位 AES 安全强度的前提下,密码分析所需的量子门电路规模由 2107提升至了 2111(量子门电路规模的评价标准详见2.2节),并使得各参数的规模都有所缩小5.安全强度的提升往往被看作证明方案可用性的一大因素.目前,国内学界在经典密码方案、后量子密码方案和密码应用方案的安全性上都有相应的研究和总结.在经典密码体系的安全强度介绍上,2016 年,孙权总结并对比了国内外主流的对称加密、非对称加密、杂凑等主要加密算法的安全强度要求,并针对不同类型的软件应用场景,结合计算机算力的发展趋势,提出当前主流加密算法的密钥强度建议6,但该文对公钥加密安全强度的总结较为片面,仅以加密方案为单位介绍了 ECC 算法和 RSA 算法的密钥长度和安全强度的关系(如 1024 位密钥的 RSA 算法对应 80 位的安全强度),缺乏从困难问题出发的安全强度梳理,并且在近三年内,缺乏更新的综述跟进公钥加密方案安全性的发展.在后量子密码体系方面,目前综述性总结较少,且集中在对称密码方面.2021 年,梁敏等人对后量子对称密码的安全强度进行了概述,分类介绍了后量子对称密码的研究进展状态,归纳总结了各项成果之间的关联及其机理7,仍缺乏对后量子公钥密码研究及其安全性的系统性总结.此外,对使用经典公钥加密和后量子公钥加密方案的商用密码方案,目前国内的研究还处在对国家标准的总结与对比层面8,少有落地于具体密码产品安全强度评估的研究总结,在场景应用安全性上也缺乏相应的安全建议.综上,国内学界研究仍缺乏对经典公钥密码方案和后量子公钥密码方案安全性定量评估的系统介绍,且缺乏结合密码学实际应用的公钥密码方案的安全性评估介绍.为弥补这些缺失,本文将以公钥密码方案嵌入的困难问题为分类标准,定量刻画现有的主流公钥密码方案的安全性,并结合目前商用的公钥密码方案应用,分析现有的公钥密码方案的安全性的总体现状和存在的隐患,并对未来的安全性提升的研究和密码算法的安全应用进行了展望.希望能为公钥密码方案的安全性优化研究提供一些参考和帮助.本文的第2节将介绍安全强度的概念,并阐述在数论困难问题下的密码(下文统称经典公钥密码)和在抗量子攻击困难问题下的密码(统称后量子公钥密码)安全强度的具体定义.第3节将介绍常见经典公钥密码方案的安全强度.第4节将介绍常见后量子密码方案的安全强度级别.第5节将从第34节中提到的密码方案的现实应用出发,介绍若干中外企业在商用安全服务中使用的公钥密码方案及其安全强度分析.第6节将对目前学界公钥密码方案的安全性现状进行总结和展望.2公钥密码方案的安全强度定义密码方案定量的安全性被称为安全强度或安全等级(以下统称安全强度),通常指在当前最佳有效攻击方式下,在密码方案取某参数时,解决困难问题的计算开销.本文使用的安全强度定义是根据美国国家标准与技术研究所(National Institute of Standards andTechnology,NIST)在 SP800-57 第 5 版密钥管理建议中给出的定义9作适应性修改得到的.定义 1(密码方案的可比安全强度)若给定密码方案 A 和方案 B 的参数集,确定 A 和 B 的密钥所需的计算开销大致相同,则称密码方案 A 和方案 B 对于该参数集具有可比安全强度.由定义可知,安全强度是基于参照的密码方案产生的,而非绝对的.在目前常见的公钥密码安全强度刻画的标准中,对称密码方案往往是强度比较的媒介,常用的又以 AES 为多10.本文在2.1和2.2节将会根据经典公钥和后量子公钥的不同特性,给出具体的安全强度定义.需要指出的是,关于安全强度,学界一直存在着不同的定义,不同的标准化机构之间有不同的定义方式.譬如,ENISA11和 IETF12等机构给出的安全强度建议都与 NIST 不同,但目前多数密码方案评估都以NIST 为准,因此,本文采取了 NIST 的标准化规定.2.1经典公钥密码方案的安全强度定义本文在经典公钥体系下衡量安全强度的方法如下:882Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023定义 2(经典公钥密码方案的安全强度)若某公钥密码方案确定密钥所需的时间与某对称密码确定密钥所需的时间近似,则该公钥密码方案的安全强度等于该对称密码的密钥长度.从具体例子而言,若一个对称密码算法的密钥为 X 位,对明文进行加密,并比较所得密文和目标密文是否一致所需的时间为 T,则完成穷举密钥平均需要 2X1T 的时间.如一个公钥密码算法被攻破的平均时间(即解决困难问题的时间)与 2X1T 相近,则称该密码算法具有 X 位的安全性10.经典公钥密码的安全强度通常有 80,112,128,192,256 几种,分别对应不同对称密码基准的密钥长度,如表1所示.其中 112 位的 2DTEA(有 2 个独立密钥的 DES 算法)在选择明文攻击或已知明文攻击下需 280次操作可确定密钥13;168 位的 3DTEA14(有 3 个独立密钥的 DES 算法)在中途相遇攻击下(meet-in-the-middle attack)需 2112次操作可确定密钥15;目前对 AES(advanced encryptionstandard)最有效的密码分析算法没有对其安全性产生太大影响16,其安全强度等于密钥长度.表 1 经典公钥密码方案的常见安全强度Table 1Typical security strengths of classical public key cryptography schemes安全强度(位)等价对称密码密钥长度(位)802DTEA1121123DTEA168128AES128192AES192256AES256在实际应用中,随着密码分析方法的不断更新,公钥密码的实际强度会更弱,本文阐述的是密码方案在理论实验中的安全强度.Bernstein 在 2013 年提出,一些公钥密码系统(如 RSA 和 ECC)遭到更强的攻击时,其在实际应用中的安全强度与标准机构提出的安全强度相比,会产生 1.11.5 倍的差距17.大型量子计算机的产生也会削弱经典公钥密码的安全强度,但考虑到量子计算的落地普及还需一定时间,本文暂不把这一因素纳入到经典公钥安全强度的讨论范畴内.2.2后量子公钥密码方案的安全强度定义本文提出的后量子公钥密码方案的安全强度概念参照的是 NIST 在后量子密码学标准化方案征集中给出的评估标准18,同样采取与对称密码等价的思想,但用安全强度等级的概念代替了具体的安全位数.采用该方法的原因是目前学界对量子计算机的性能认知有限,研究者需要根据量子计算机的性能发展,细化后量子公钥密码方案的安全强度.定义 3(后量子公钥密码方案的安全强度等级)若攻破某后量子公钥密码方案所需的经典门电路/量子门电路数量,与攻破某密钥长度的 AES 密码所需的经典门电路/量子门电路数量近似,则该后量子公钥密码方案的安全强度等级等于该 AES 密码的安全强度等级.现有研究已给出了使用 Grover 算法对 AES-128/192/256 攻击所需的门电路规模的估计19,在这基础上可以得到三种不同的安全强度等级,如表2所示20.其中 MaxDepth 是指一定时间内可串行的门电路数量,可将量子攻击限制在固定运行时间内,其范围大致在 240,264 个逻辑门之间(等价为 1 到 10 年内目前理想的量子架构能执行的逻辑门数量),最高不会超过 296(等价为光速原子级量子位在一千年内可以执行的逻辑门数量)21.引入该常量可以限制攻击算法的计算时间,并将攻击者的能力控制在合理的范围内.在后量子密码方案的安全性衡量上,使用经典门电路规模和量子门电路规模等价安全强度等级的方法是同时存在的.比如,NTRU 方案的说明文档中,衡量安全强度使用的就是 RAM 模型下混合攻击的 core-SVP 成本22;另有一些研究,如文献 5,23,则同时用到了经典电路和量子电路混合攻击的 core-SVP 成本来衡量安全性.林申 等:公钥密码安全强度刻画概述883表 2 后量子公钥密码方案的常见安全强度Table 2Typical security strengths of post-quantum public key cryptography schemes安全强度等级等价对称密码经典门规模量子门规模Category 1AES-12821432170/MaxDepthCategory 3AES-19222072233/MaxDepthCategory 5AES-25622722298/MaxDepth3经典公钥密码方案的安全强度3.1经典公钥的困难问题经典公钥密码方案的安全强度论述将分为三类展开:基于大整数分解困难问题的方案(integer fac-torization problem,IFP)、基于有限域离散对数困难问题的方案(discrete logarithm problem on finitefield,DLP-FF)和基于椭圆曲线离散对数困难问题的方案(discrete logarithm problem on elliptic curve,DLP-EC).三类困难问题的数学表述如表3所示.表 3 经典公钥困难问题的数学表述Table 3Mathematical expression of classical public key hard problems困难问题输入输出典型方案IFP合数 Nf (1,N),其中 f|NRSA,RabinDLP-FF有限域 Fp,两个元素 g,y Fpx Fp,其中 gx y mod pElGamal,DH 密钥交换DLP-EC有限域 Fp上的椭圆曲线方程 E,P(x1,y1),Q(x2,y2)Ek Z,其中 kP=QECDH,SM2以上三种问题使用经典计算机都难以破解,即使出现了若干比朴素计算更快的密码分析算法,譬如针对整数分解问题的普通数域筛选算法(N 位整数分解的复杂度为 exp(649)13(logN)13(loglogN)23(1+o(1)24)等,可以将时间复杂度控制在多项式级和指数级之间,但目前没有经典计算机可应用的多项式算法破解这三类问题.常见的基于大整数分解问题的密码方案有 RSA 方案25、Rabin 方案26;常见的基于有限域离散对数问题的密码方案有 DSA 方案27、DH 密钥交换方案1,28、ElGamal 方案29;常见的基于椭圆曲线离散对数问题的密码方案有椭圆曲线 DH 密钥交换方案(EC-DH)30、椭圆曲线 DSA方案(EC-DSA)31、椭圆曲线 ElGamal 方案(EC-ElGamal)32、国密 SM2 方案33.3.2三类经典公钥的安全强度三类困难问题的安全强度如表4所示10,以公私钥的长度为主要变量(其中 k 为模数 n 的长度,L为公钥长度,N 为私钥长度,f 为椭圆曲线基点 G 的阶,k 和 f 也常被简称为密钥长度).表 4 经典公钥密码的安全强度Table 4Security strength of classical public key cryptography安全强度IFPDLP-FFDLP-EC 80k=1024L=1024f 160,223112k=2048L=2048,N=224f 224,255128k=3072L=3072,N=256f 256,383192k=7680L=7680,N=384f 384,511256k=15360L=15360,N=512f 512884Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023关于在表4中未给出的大整数分解和有限域离散对数密码方案实例化参数,可以通过 NIST 给出的公式进行安全强度的计算.对于密钥长度为 L 的大整数分解密码方案而言,对应的对称密码位数 x(可大致等同于安全强度)可用公式(1)计算34:x=1.923 3L ln2 3(ln(L ln2)2 4.69ln2.(1)对于公钥长度为 L、私钥长度为 N 的有限域离散对数密码而言,其安全强度 y 可用公式(2)计算(其中 x 为将 L 代入公式(1)中的计算结果).y=min(x,N/2).(2)到 2030 年,112 位的安全强度的密码方案不允许被用于加密和签名的数据保护,仅可被用于解密和验证签名.2031 年以后,若要在数据保护和验证处理上都保有足够的安全性,那么一个密码算法至少需要有 128 位及以上的安全性10.4后量子公钥密码方案的安全强度后量子公钥密码方案的阐述将分为以下几部分展开:基于格问题的密码方案、基于编码问题的密码方案和基于其他抗量子攻击困难问题的密码方案.本节中的安全强度阐述将在困难问题下,以具体密码方案为单位展开,因为同一类后量子困难问题下的方案参数选取差异化较大,且后量子公钥密码发展还不成熟,目前仍未有一个完整的标准化体系.4.1基于格问题的密码方案格可被看作一组 n 维空间上的线性网格点,其定义如下:定义 4(格)R 为实数域,Z 为整数域,给定 n 个线性无关的向量 b1,b2,bn Rm,那么格是这n 个向量的任意线性组合的集合,即:L(B)=L(b1,b2,bn)=xibi|xi Z=Bx|x Zn,b1,b2,bn 为格的基向量,也可写成基矩阵 B 的形式.格上的若干数学困难问题,常用的包括最短向量问题(shortest vector problem,SVP)、最近向量问题(closest vector problem,CVP)、小整数解问题(small integer solution problem,SIS)、带错学习问题(learning with error,LWE)等,即使对于量子计算机而言,也是难解的.这四类问题的定义如表5所示.表 5 常见格困难问题的定义Table 5Definition of typical lattice hard problems困难问题输入输出SVP格基 B非零向量 v L(B),对任意非零向量u L(B),v uCVP格基 B 和向量 t L(B)向量 v L(B),对任意非零向量 u L(B),v t u tSIS(A,),其中 AR Zmnq,Z非零整数向量 z Zm0,有 Az=0,且 z LWE(A,As+e),其中 AR Zmnq,sR Zq,e ZnqR XB,XB为向量范式最大为 B 的随机分布向量 s,有 As(As+b)B本文将以下安全高效的格密码方案纳入调研的范围,分别为:NTRU 方案(融合了 NTRUEncrypt 和NTRU HRSS-KEM 两个方案)、CRYSTAL-KYBER 方案和 CRYSTAL-DILITHIUM 签名方案.林申 等:公钥密码安全强度刻画概述8854.1.1NTRUNTRU 方案是 1998 年基于格上 SVP 问题构造的首个格基公钥加密方案35.本文采用的 NTRU 方案是 NIST 后量子标准化第三轮入围的版本,包括了 NTRU 的加密和密钥封装算法,其中加密算法沿用的是 NTRU-HPS 算法3,密钥封装沿用的是 NTRU-HRSS 算法36.NTRU 在本地模型(local model,计算模型中的信号以有限的速度传播,如单带图灵机和超大规模集成电路 VLSI)和非本地模型(non-localmodel,计算模型允许在任意距离进行单位成本通信,如随机存取机器、布尔电路和 Clifford+T 量子电路)下的安全性有明显区别37.前者只允许模型信号以有限速度传播,整体安全性较高;后者允许任意距离内的单位成本通信,整体安全性较低.表6为 NTRU 方案的安全强度等级列举(Category 1,3,5 的定义见表2),其中参数中的 N 可确定多项式环的最高次数 N 1,q 为大模数,参数名设置往往是“NTRU-HPS+N+q”或“NTRU-HRSS+N”的格式.NTRU 方案安全强度等级的选取是大致根据原始攻击(结合了维度约简算法38和正交投影约简算法39)和 Howgrave-Graham 混合攻击40的 core-SVP 块约简的位操作成本决定的,其中会有一些数据略小于表2中的门电路规模标准(如(local)NTRU-HPS2048677 和(non-local)NTRU-HPS4096821),但设计者也指出,在分析中未考虑的额外成本如内存访问成本等,弥补了规模上的差距.同时值得指出的是,目前给出的 NTRU 参数集仍存在一定的隐患,若 Ducas 关于本地模型复杂度的安全性估计41是正确的,那么表格中的本地模型安全强度等级需要向下修正.表 6 NTRU 方案的安全强度等级Table 6Security strength levels of NTRU方案变体计算模型参数集主要参数设置Core-SVP等级位操作成本安全强度NTRU-HPS本地模型(Local)NTRU-HPS2048509N=509,q=20482151Category 1(Local)NTRU-HPS2048677N=677,q=20482205Category 3(Local)NTRU-HPS4096821N=821,q=40962253Category 5非本地模型(Non-local)NTRU-HPS2048677N=677,q=20482145Category 1(Non-local)NTRU-HPS4096821N=821,q=40962179Category 3NTRU-HRSS非本地模型(Non-local)NTRU-HRSS701N=701,q=81922136Category 1本地模型(Local)NTRU-HRSS701N=701,q=81922195Category 34.1.2KYBER 和 DILITHIUMCRYSTAL-KYBER23和 CRYSTAL-DILITHIUM42同属于代数格密码套件43(cryptographicsuite for algebraic lattices,CRYSTAL)的原语族,基于模带错学习问题(module learning with errors,MLWE)问题构建.KYBER 和 DILITHIUM 各有三组不同的参数集,KYBER 可实现 Category 1/3/5的安全等级,DILITHIUM 可实现 Category 2/3/5 的等级(本文仅讨论了 3/5 两种等级).KYBER 和DILITHIUM 共享一个框架,其安全等级的改变可以简单地通过改变算法中使用的块矩阵的顺序来实现.KYBER 和 DILITHIUM 密钥的大小都很小,对于实际的应用较为友好,特别是 KYBER,已经在一些互联网的安全服务中有了多处应用.经过 4 轮的选拔后,两个方案都已进入了 NIST 后量子标准化的最终候选算法(selected algorithm 2022)44.和 NTRU 的提出者直接使用 core-SVP 成本对标安全强度等级不同的是,KYBER 和 DILITHIUM的 NIST 说明文档中提到了基于 core-SVP 成本虽然可以得出较为保守的安全性,但较为粗略.在 KYBER886Journal of Cryptologic Research 密码学报 Vol.10,No.5,Oct.2023和 DILITHIUM 方案中,设计者使用了更贴合现实的攻击算法41,45,46对经典门电路的规模数据进行了修正,其数据会略高于格原始攻击的 core-SVP 成本,但更接近现实情况.表7为 KYBER 方案和 DILITHIUM 方案的安全强度等级列举,在 KYBER 方案中,n 和 q 分别决定多项式模环 Rq=Zq/(Xn+1)的系数模和最高次数,k 为矩阵的维数,改变 k 可调节方案的安全性.在DILITHIUM 方案中,定义多项式环的 n=256,q=8380417,表中 为签名中间变量 c 中 1 的数量,(k,l)为随机矩阵 A 的维数,为私钥每位的取值范围(si S),为签名 hint 中 1 的最大出现次数.表 7 KYBER 和 DILITHIUM 方案的安全强度等级Table 7Security strength levels of KYBER and DILITHIUM方案参数集主要参数设置经典门量子 core安全强度等级电路规模-SVP 成本KYBERKYBER512n=256,k=2,q=332921512107Category 1KYBER768n=256,k=3,q=332922152165Category 3KYBER1024n=256,k=4,q=332922872232Category 5DILITHIUMDILITHIUM3=49,=4,=55,(k,l)=(6,5)22172165Category 3DILITHIUM5=60,=2,=75,(k,l)=(8,7)22852229Category 54.1.3本节小结本节总结了三个基于格的密码方案,分别为NTRU、CRYSTAL-KYBER和CRYSTAL-DILITHIUM,这些方案都有较为完善的若干参数集,可以适应不同场景的安全性,在效率优先的情况下,往往 Category 1 的安全等级即可满足需求,如果要求更高的安全等级,上述方案也都可以满足需求.虽然在安全强度等级上二者都可以符合标准化的需求,但 KYBER 和 DILITHIUM 相较于 NTRU 给出的安全强度评估的出发点更加细致,也是 CRYSTAL 密码套件的优势所在.基于格问题的密码方案也是入选 NIST 后量子标准化最终确定方案名单中最多的,包括 KYBER、DILITHIUM 和 FALCON47,是目前最有前景且总体最稳定的抗量子密码方案类别,兼具安全性和高效性,因此,对于后量子公钥的应用可以多侧重于格密码,以保障敏感信息的安全性和信息传输的高效性.4.2基于编码问题的密码方案基于编码的密码方案依赖的困难问题往往是纠错码上的伴随式译码问题(syndrome decoding,SD)48及其衍生的困难问题,与寻找码字问题(codeword finding,CF)及其衍生问题,分别定义如下.定义 5(计算型伴随式译码问题)对于一个码长为 n,信息位数为 k 的线性码,给定一个二元(n k)n 矩阵 H、一个码字 y 0,1nk和一个整数 w 0,找出一个具有汉明重量小于等于 w 的码字x,使得 Hx=y.定义 6(判定型伴随式译码问题)对于一个码长为 n,信息位数为 k 的线性码,给定一个二元(n k)n 矩阵 H、一个码字 y 0,1nk,判断 y 是由伴随式(x)=Hx生成的,还是随机生成的.定义 7(寻找码字问题)给定一个二元(n k)n 矩阵 H 和一个整数 w 0,找出一个汉明重量小于等于 w 的码字 x,使得 Hx=0.本文调研的基于编码问题的方案有 2 个:Classic McEliece 和 BIKE.其中 Classic McEliece 是进入NIST 后量子标准化选拔第三轮正式候选的编码方案,BIKE 为第三轮的备用方案.4.2.1Classic McElieceClassic McEliece 方案是 NIST 第三轮方案提交中历史最为悠久的方案,是由 OW-CPA(one-wayCPA)的 McEliece PKE 方案转化得到的 CCA2 密钥封装机制(key encapsulation mechanism,KEM),与传统的公钥加密机制不同的是,密钥封装加密的目标更为明确,是为了保护通信中的对称密钥,被用于通信的混合加密中.McEliece PKE 由 McEliece 于 1978 年提出49,至今仍有足够强的安全性.McEliece的安全性基于计算型伴随式译码问题的变体,使用的码为 Goppa 码.林申 等:公钥密码安全强度刻画概述887目前的 Classic McEliece 方案融合了第一轮的 Classic McEliece 方案和 NTS-KEM 方案.ClassicMcEliece 也是三个方案中提供的参数集最多的,Category 1/3/5 每个分类中至少都有两种不同的参数集50.McEliece 的优势在于长期稳定的安全性保障,以及较小的密文大小,但其公钥大小过大也成为了一大劣势.针对基于编码的密码方案最有效的攻击方法是信息集攻击(information-set decoding,ISD)51,较为有效的算法包括 Stern 算法52、BJMM 算法53等.在 Classic McEliece 的官方文档中使用的是 Stern算法变体54的经典门电路规模(位操作次数)等价的参数集安全强度等级,因此,本文也采用相同的数据55.除了官方文档中使用的主流数据,近年也有新的研究对高效密码分析算法的操作复杂度数据进行了修正,例如文献 56,但截至目前,相关研究并未对 Classic McEliec