1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):2045密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618NIST 抗量子密码标准候选算法中基于格的公钥加密与密钥封装机制介绍*向斌武1,2,3,张 江1,邓 燚2,31.密码科学技术全国重点实验室,北京 1008782.中国科学院 信息工程研究所 信息安全国家重点实验室,北京 1000933.中国科学院大学 网络空间安全学院,北京 100049通信作者:向斌武,E-mail:摘要:基于格的后量子密码
2、方案在安全性、密钥尺寸和运算速度等方面相较于其他方案都有一定优势,被认为是最有潜力的后量子密码方案.本文综述了美国国家标准技术研究所发起的后量子密码竞赛中所有基于格的公钥加密方案与密钥封装机制,从方法论以及困难性假设的角度进行分类,详细介绍了各自的设计思路与细节.针对重点算法 KYBER、SABER、FrodoKEM、LAC、NewHope 以及基于 NTRU 的算法,从底层设计、参数选择、性能对比等方面进行全面比较.总结了竞赛最新进展并分析了目前设计方案需要注意的问题,介绍了未来后量子密码方案设计潜在的发展方向.关键词:格;公钥加密;密钥封装机制中图分类号:TP309.7文献标识码:ADOI
3、:10.13868/ki.jcr.000577中文引用格式:向斌武,张江,邓燚.NIST 抗量子密码标准候选算法中基于格的公钥加密与密钥封装机制介绍J.密码学报,2023,10(1):2045.DOI:10.13868/ki.jcr.000577英文引用格式:XIANG B W,ZAHNG J,DENG Y.An overview on lattice-based public key encryption andkey encapsulation mechanism in candidate schemes for post quantum cryptography standard of
4、NISTJ.Journal of Cryptologic Research,2023,10(1):2045.DOI:10.13868/ki.jcr.000577An Overview on Lattice-based Public Key Encryption and KeyEncapsulation Mechanism in Candidate Schemes for Post QuantumCryptography Standard of NISTXIANG Bin-Wu1,2,3,ZHANG Jiang1,DENG Yi2,31.State Key Laboratory of Crypt
5、ology,Beijing 100878,China2.State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy ofSciences,Beijing 100093,China3.School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,ChinaCorresponding author:XIANG Bin-Wu,E-mail:Abstract:The
6、lattice-based scheme is considered the most potential Post-Quantum Cryptography(PQC)scheme due to its advantages in security,key size,and operation speed compared to other*基金项目:国家自然科学基金(62022018,61932019);北京自然科学基金(M22003);国家重点研发计划(2018YFB0804105)Foundation:National Natural Science Foundation of Chin
7、a(62022018,61932019);Natural Science Foundation ofBeijing Municipality(M22003);National Key Research and Development Program of China(2018YFB0804105)收稿日期:2022-02-14定稿日期:2022-11-13向斌武 等:NIST 抗量子密码标准候选算法中基于格的公钥加密与密钥封装机制介绍21PQC schemes.This paper summarizes all lattice-based Public Key Encryption(PKE)s
8、chemes andKey Encapsulation Methods(KEM)in the National Institute of Standards and Technology(NIST)PQC competition,classifies them from the perspective of methodology and hard problem assumptions,introduces their design ideas and design details.A comprehensive comparison of the key algorithmsKYBER,S
9、ABER,FrodoKEM,LAC,NewHope,and NTRU-based algorithms is conducted in terms ofunderlying design,parameter selection,and performance comparison.In addition,the latest progressin the NIST PQC competition is summarized and the issues that need to be taken into account incurrent design schemes are analyze
10、d,while potential development directions for future PQC schemedesigns are introduced.Key words:lattice;public key encryption;key encapsulation mechanism1引言目前公钥加密、数字签名和密钥交换方案主要使用 RSA(Rivest-Shamir-Adleman)、Diffie-Hellman密钥交换和椭圆曲线来实现,安全性依赖于数论上的困难问题,如大整数分解和离散对数问题.1997 年,Shor1提出了一种在量子计算机上运行的算法,可以在多项式时间内
11、解决大整数分解问题.此外,该算法还可用于在多项式时间内解决离散对数问题,使得目前使用的大多数公钥密码方案都不安全.尽管还不清楚是否存在高效的量子计算机,本着未雨绸缪的思想,后量子密码成为了一种趋势,构造能够抵抗经典计算机和量子计算机攻击的可以在经典计算机上运行的密码方案是十分必要的.2016 年美国国家标准技术研究所(NIST)发布了一份后量子报告2,并开始在全球范围内开展后量子密码算法标准的征集工作.NIST 的后量子密码报告中提到的后量子密码算法主要有基于格的密码(lattice-based cryptography)、基于编码的密码系统(code-based cryptosystems)
12、、多变量密码(multivariate cryptography)以及基于哈希算法的签名(hash-based signatures)等四种.在这些后量子算法中,基于格的密码算法已经被选中并将进行标准化.格是 Rm中一类具有周期性结构离散点的集合.1996 年,Ajtai3开创性地给出了格中困难问题的worst-case 到 average-case 的归约证明.那么,除非格问题的所有实例都容易解决,否则我们便能基于格问题构造安全的密码方案.基于 Ajtai 的归约,1997 年 Ajtai 和 Dwork4构造了第一个基于格的密码体制,具有最坏复杂性假设下安全性证明.同年,Goldreich
13、、Goldwasser 和 Halevi5提出了更实用的格上公钥加密和签名方案(GGH 密码体制),但并没有最坏情况下的安全性保证.1996 年 Hoffstein 等人6利用多项式环提出了 NTRU 加密体制,加解密速度更快,密钥尺寸更紧凑但缺乏形式化的安全性证明.2005 年 Regev7提出错误学习问题(learning with error,LWE)并给出了相关的格中问题 worst-case 到 average-case 的归约证明.2010 年,Lyubashevsky 等人8提出了环上错误学习问题(ring-LWE,RLWE),其困难性可归约到理想格上的困难问题 SVP 的最困难
14、情形下;2012 年 Banerjee 等人9提出舍入学习问题(learning with rounding,LWR)以及环上 LWR 问题(ring-LWR,RLWR),并在一定参数条件下给出了从 LWE 问题到 LWR 问题的归约,以及从 RLWE 问题到 RLWR 问题的归约;2015 年,Langlois 等人10研究了模上的错误学习问题(module-LWE,MLWE),并将 MLWE 问题归约到模格上的困难问题.NIST 中所有基于格的公钥加密方案与密钥封装机制大都基于这些困难问题.NIST 后量子密码竞赛公布的第一轮的 69 个候选算法中有 26 个是基于格设计的.在第二轮评选挑
15、选出的 26 个算法中,基于格的有 12 个,NIST 从第二轮候选中选出 15 个算法(包括 7 个决赛算法、8 个候选算法),进入第三轮标准化过程.在第三轮标准化进程的决赛算法中有 3 个公钥加密/密钥封装算法以及 2 个数字签名算法都是基于格设计的.此外,在候选算法中还有 2 种基于格的公钥加密算法.本文将介绍在 NIST 征集工作中基于格的公钥加密/密钥封装机制,介绍各自的算法流程以及设计摘要,并挑选第二轮中的几种重点算法给出更为详细的分析与比较,阐述 NIST 后量子密码竞赛的最新进展.本文后面部分安排如下.第2节介绍基于格的方案设计中必需的基础知识;第3节介绍 Regev 方案以及
16、 NIST 候选方案中的类 Regev 方案;第4节第介绍 LP 方案以及 NIST 候选方案中的类 LP 方案;第5节介绍 NTRU 公钥加密方案与类 NTRU 方案并对其结构进行详细的比较与分析;第6节简要介绍其22Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023他的几个方案;第7节是总结与展望.2背景知识2.1符号如非特殊说明,本文中用 R 表示多项式环,Rq=R/qR,加粗的小写字母(如 a)表示向量或多项式环元素,加粗的大写字母(如 A)表示矩阵.向量 a,b 之间的内积用 a,b 表示,用,分别表示向下取整、向上取整和舍入运算.对于分布,x 表示抽取分布 中的值 x,x$表示从分布 中随机抽取值 x.2.2标准格格是 Rm中一类具有周期性结构离散点的集合.严格地说,格是 m 维欧式空间 Rm的 n(m n)个线性无关向量组 b1,b2,bn的所有整系数线性组合,即L(B)=Bx|x Zn=y=ni=1xibi|xi Z,向量组 b1,b2,bn称为格的一组基.同一个格可以用不同的格基表示.m 称为格的维数,n
