1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(1):119密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618基于格的数字签名及其聚合类变体的综述*陈新坚1,黄建业3,黄 琼1,21.华南农业大学 数学与信息学院,广州 510642,中国2.广州市智慧农业重点实验室,广州 510642,中国3.伍伦贡大学 计算机与信息技术学院,伍伦贡 新南威尔士 2500,澳大利亚通信作者:黄琼,E-mail:摘要:数字签名作为一项重要的认证技术,使得人们能够在数字信息
2、时代进行便捷的数字办公,在信息安全、身份认证、数据完整性、不可否认性等方面应用广泛.多重签名和聚合签名将数字签名压缩技术和批处理技术进行整合,极大节省了存储空间和传输带宽的消耗,适用于区块链比特币交易、电子投票、证书链认证等实际业务.随着量子计算机的快速发展,许多传统密码体制的安全性受到严重威胁,而格中的困难问题被认为是能够抵抗量子计算攻击的数学问题,所以格密码成为目前备受关注的一类能够抵抗量子计算攻击的公钥密码体制.因此,研究基于格的数字签名方案是使数字签名能够抵抗量子计算攻击的有效举措.本文主要围绕基于格的数字签名,包括普通数字签名、多重签名和聚合签名,对近些年的主要研究成果进行介绍和分析
3、,对基于格的数字签名及其未来的研究方向进行了总结.关键词:格密码;数字签名;多重签名;聚合签名中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000576中文引用格式:陈新坚,黄建业,黄琼.基于格的数字签名及其聚合类变体的综述J.密码学报,2023,10(1):119.DOI:10.13868/ki.jcr.000576英文引用格式:CHEN X J,HUANG J Y,HUANG Q.An overview of lattice-based signature andits variants supporting aggregationJ.Journal of
4、 Cryptologic Research,2023,10(1):119.DOI:10.13868/ki.jcr.000576An Overview of Lattice-based Signature and Its Variants SupportingAggregationCHEN Xin-Jian1,HUANG Jian-Ye3,HUANG Qiong1,21.College of Mathematics and Informatics,South China Agricultural University,Guangzhou 510642,China2.Guangzhou Key L
5、ab of Intelligent Agriculture,Guangzhou 510642,China3.School of Computing and Information Technology,University of Wollongong,Wollongong,NSW 2500,AustraliaCorresponding author:HUANG Qiong,E-mail:*基金项目:广东省基础与应用基础研究重大项目(2019B030302008);国家自然科学基金(62272174,61872152);广州市科技计划(201902010081)Foundation:Major
6、Program of Guangdong Basic and Applied Research(2019B030302008),National NaturalScience Foundation of China(62272174,61872152),Science and Technology Program of Guangzhou Municipality(201902010081)收稿日期:2022-05-01定稿日期:2022-09-012Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2023Abstract:As an
7、important authentication technology,digital signature enables people to carryout convenient digital office in the digital information age.It is widely used in information security,identity authentication,data integrity,non-repudiation and so on.As the extensions of digital signa-ture,multi-signature
8、 and aggregate signature integrate digital signature compression technology andbatch processing technology,which greatly saves the consumption of storage space and transmissionbandwidth.And they are widely used in blockchain bitcoin transactions,electronic voting,certificatechains authentication and
9、 so on.With the rapid development of quantum computers,the security ofmany traditional cryptosystems has been seriously threatened.Fortunately,lattice-based cryptogra-phy is a type of public-key cryptosystem that can withstand quantum computing attacks,because thehard problem on lattice is considere
10、d to be resistant to the attacks of quantum computers.Therefore,research on lattice-based digital signature schemes is an effective measure to make digital signaturesresistant against quantum computing attacks.This paper mainly focuses on lattice-based digital sig-natures,including general digital s
11、ignature,multi-signature and aggregate signature,introduces andanalyzes the main research results in recent years.Finally,lattice-based signatures and their futureresearch directions are summarized.Key words:lattice-based cryptography;digital signature;multi-signature;aggregate signature1引言1976 年,Di
12、ffie 与 Hellman 在New Directions in Cryptography1一文中第一次提出了数字签名(digital signature)的概念,自此关于数字签名的研究层出不穷.数字签名是在网络环境里模拟现实世界物理签名的关键技术,只有消息发送方能够生成,其他人无法正确伪造,可有效解决身份冒充、伪造篡改以及抵赖等信息安全问题.数字签名作为一项重要的认证技术,在身份认证、消息完整性检验、鉴权等信息安全领域扮演着不可或缺的角色.随着应用领域的扩展,各种应用需求不断增加,数字签名产生了很多变体.比如,在实践中往往需要多个部门或单位在同一份文件上分别签字,才能使文件生效.在网络环境
13、中,多重签名(multi-signature,MS)技术就是模拟解决这类问题的关键所在.1983 年,Itakura 和 Nakamura2首先提出了多重签名的概念和模型:一组具有公钥序列 pk1,pk2,pkn 的签名者在同一消息 m 上共同构建一个多重签名.一般而言,多重签名的大小比使用 n 个单签名组成的平凡多重签名(trivial multi-signature)小得多,从而大大节省了存储空间和传输带宽的消耗.多重签名的应用非常广泛,包括区块链比特币交易、合同签署、专家咨询等.如果将多个签名者对同一消息进行签名的场景,扩展到多个签名者对各自不同的消息进行签名的情形,则得到了另一种数字签
14、名聚合签名(aggregate signature,AS).2003 年,Boneh 等人3首先提出了聚合签名的概念,通过将数字签名压缩技术和批处理技术进行整合,设计了聚合签名这一原语.在签名生成算法中,将每一个签名用户对各自不同的消息进行签名得到的签名集合压缩成一个单一的聚合签名,从而大大节省了存储空间和传输带宽的消耗.在验证算法中,如果最终的聚合签名验证有效,则相当于完成了对每一个用户的签名消息对的批量验证.聚合签名以其特有的优势被广泛应用于无线传感网、证书链认证、安全路由等领域当中.随着量子计算机的不断发展,Shor 和 Grover4,5发现有效的量子算法能够解决经典的困难问题,经典签
15、名方案正面临着极大的安全威胁.因此,如何设计能够抵抗量子计算攻击的签名方案,是后量子时代的密码安全研究领域中一个亟待解决的问题.1996 年,Ajtai6开创性地给出了一类随机格的构造方法,并在文献 7 中证明了格中最短向量问题(shortest vector problem,SVP)、最短线性独立向量问题(shortest linear independent vector problem,SIVP)等在最坏情况(worst-case)下的困难性,可以归约为解决随机格中小整数解(small integer solution,SIS)问题、容错学习(learning with errors,L
16、WE)问题的困难性,使得基于格的公钥密码体制具备了安全性证明的理论基础.目前,格中很多困难问题是 NP困难的(non-deterministic polynomial-time hard,NP-hard),即便借助量子计算机也很难将其攻破,所以陈新坚 等:基于格的数字签名及其聚合类变体的综述3基于格中困难问题的公钥密码体制被认为是能够抵抗量子计算攻击的有效密码体制.因此,为了使数字签名能够抵抗量子计算的攻击,研究基于格的数字签名方案已逐渐成为后量子时代的研究热点.本文主要介绍基于格的数字签名,包括普通数字签名、多重签名和聚合签名,并对近些年的一些主要研究成果进行分析和比较,最后进行总结.本文的内容安排如下:第1节主要介绍基于格的数字签名方案研究的发展由来;第2节介绍了格中基础理论的一些基本概念和困难问题,并介绍数字签名、多重签名、聚合签名的定义和安全性要求;第3节就基于格的普通数字签名方案及其主要研究成果展开论述;第4节讨论了基于格的多重签名方案及其重要成果;第5节针对基于格的聚合签名方案及其关键成果进行回顾分析;最后在第6节中对基于格的数字签名及其未来的研究方向进行了总结.2基础知识