格上基于身份的代理签名方案.pdf
《格上基于身份的代理签名方案.pdf》由会员分享,可在线阅读,更多相关《格上基于身份的代理签名方案.pdf(7页珍藏版)》请在文库网上搜索。
1、格上基于身份的代理签名方案姬蔚萍,范士喜,李子臣(北京印刷学院信息工程学院,北京102600)通信作者:李子臣,E-mail:摘要:为抵抗量子计算攻击,降低代理签名中用户私钥泄露的风险,构造了一个格上基于身份的代理签名方案.方案的设计基于安全高效的 GPV 签名框架,结合用户身份信息生成验证公钥,使用格基委派技术生成用户签名私钥,并使用盆景树代理委托算法提升签名效率.方案的安全性可规约至格上最小整数解问题,满足基于身份代理签名的安全属性,且在随机谕言和量子随机谕言下均具有存在性不可伪造性.关键词:基于身份的代理签名;GPV 签名框架;后量子密码;格上最小整数解问题;格基委派算法引用格式:姬蔚萍
2、,范士喜,李子臣.格上基于身份的代理签名方案.计算机系统应用,2023,32(10):301307.http:/www.c-s- Proxy Signature on LatticesJIWei-Ping,FANShi-Xi,LIZi-Chen(SchoolofInformationEngineering,BeijingInstituteofGraphicCommunication,Beijing102600,China)Abstract:Toresistquantumcomputingattacksandreducetheriskofprivatekeyleakageofusersinpro
3、xysignatures,thisstudyproposesanidentity-basedproxysignatureschemeonlattices.ThisschemeisdesignedbasedonthesecureandefficientGPVsignatureframework.Theverificationpublickeyisgeneratedbycombiningtheuseridentityinformation.Thelatticebasisdelegationtechnologyisusedtogeneratetheprivatekeyfortheusersignat
4、ure,andthebonsaitreedelegationalgorithmisadoptedtoimprovesigningefficiency.Thesecurityoftheschemeisbasedontheshortestintegersolution(SIS)assumption.Itsatisfiesthesecuritypropertiesofidentity-basedproxysignaturesandhasexistentialunforgeabilityunderrandomoraclesandquantumrandomoracles.Key words:identi
5、ty-basedproxysignature;GPVsignatureframework;post-quantumcryptography;shortestintegersolution(SIS)assumption;basisdelegationalgorithm数字签名是指只有信息发送者才能生成且其他任何人无法伪造的一段字符串,这段字符串同时也是对信息的发送者所发送的信息是否真实有效的证明.一个完备的数字签名通常需要定义两个互补运算,一个用于签名,另一个用于验证.代理签名的特点在于可以在原始签名者无法签名的情况下进行签名权力的委托,并完成安全的数字签名过程.比如,某单位负责人由于某些原因无
6、法返回公司,将公司相关事务委托给他的助理,为赋予事务的办理权力,负责人需要给予助理自己的公章,让其能够代表公司在文件上盖章,以上所述即为“代理”的过程.因此可以看出,代理签名具有不可替代的研究意义和应用前景.1996 年,代理签名的概念被 Mambo 等人1提出,该方案具有两个角色:原始签名者 O(originalsigner)计算机系统应用ISSN1003-3254,CODENCSAOBNE-mail:ComputerSystems&Applications,2023,32(10):301307doi:10.15888/ki.csa.009243http:/www.c-s-中国科学院软件研究
7、所版权所有.Tel:+86-10-62661041基金项目:国家自然科学基金(61370188);北京市教委科研计划(KM202010015009,KM202310015002);北京市教委科研计划(KM202110015004);北京市高等教育学会 2022 年立项面上攻关课题(MS2022093);北京印刷学院博士启动金(27170120003/020,27170122006);北京印刷学院科研创新团队项目(Eb202101);北京印刷学院校内学科建设项目(21090121021);北京印刷学院重点教改项目(22150121033/009);北京印刷学院科研基础研究一般项目(Ec20220
8、1)收稿时间:2023-02-22;修改时间:2023-04-07;采用时间:2023-04-23;csa 在线出版时间:2023-07-21CNKI 网络首发时间:2023-07-21ResearchandDevelopment研究开发301和代理签名者 P(proxysigner).签名者 O 赋予代理签名者 P 签名的权力,P 在获得签名权力之后,可以代替原始签名者 O 进行有效签名,产生合法签名信息.在此概念提出之后,代理签名方案的研究如火如荼地进行,基于离散对数的代理签名方案、基于大整数分解的代理签名以及基于双线性对映射上的代理签名方案等不断被提出25.1984 年,Shamir6首
9、次提出了基于身份的签名方案,身份的特殊属性可以使密钥管理过程更加简洁高效,用户的身份信息即为用户公钥,用户私钥通过主密钥以及用户身份 id 构造.2005 年,Xu 等人4基于椭圆曲线上的双线性对困难问题构建了第 1 个基于身份的代理签名方案,但该方案缺少对于自适应选择身份攻击和选择消息攻击的安全性证明.2006 年,Shim7指出基于身份的代理签名所需的安全属性应包含不可伪造性、可验证性、强的身份可识别性、阻止误用性以及不可抵赖性.2007 年,Wu 等人8优化了基于身份地代理签名的安全概念,并基于双线性对构造了一个高效的签名方案.该方案可抵抗自适应选择明文攻击和选择身份伪造攻击.2015
10、年,Gu 等人9提出了一个标准模型下的签名框架,并基于 CDH(computationalDiffie-Hellmanproblem)问题提出了一个可证安全的基于身份的代理签名方案.随着后量子时代的到来,传统公钥密码系统岌岌可危10,11,量子安全代理签名方案的研究已经成为当务之急.2008 年,Gentry 等人12创造性地提出了以困难格陷门为基础的 hash-and-sign 签名范式,该签名范式是第 1 个公认安全高效的格上陷门方案,此框架提出后,格上数字签名得到快速发展.Cash 等人13利用原像抽样函数构造了著名的格基委派算法,并提出了第1 个标准模型下可证安全的格签名方案.文献 1
11、4 利用 Gentry 所提出的陷门构造方法提出了一种标准模型下基于格的代理签名方案.之后,文献 15 结合身份信息构造了一个基于身份的格代理签名方案,但此方案只满足存在不可伪造性,并未分析其他安全属性.文献 16基于格上短整数解和非均匀小整数解难题提出了第1 种标准模型下基于身份的代理盲签名方案,并分析了其不可伪造性.文献 17 基于最小整数解问题在理想格上构造了一个基于身份的代理签名方案,并证明了方案在选择身份和固定选择消息攻击下仍具有强不可伪造性,但方案签名复杂度较高.文献 18 构造了一种 NTRU 格上基于身份的代理签名方案,由于 NTRU 的特性,该方案在公钥和签名尺寸较短.文献
12、19 提出了一种前向安全的格基代理签名,但方案是以牺牲效率为代价来提升安全性.本文基于 GPV 签名框架构建了一个基于身份的代理签名方案,使用盆景树生长算法13合成原始签名者 O 和代理签名者 P 各自的公钥矩阵,利用格基委派算法提取身份 id 对应的用户私钥,利用原像取样算法完成签名及验证过程.经分析,该方案安全性依赖于格上 SIS 困难问题,且满足随机谕言机模型下选择身份和选择消息的存在不可伪造性、强的身份可识别性以及不可抵赖性.1相关知识 1.1 格上定义q,m,n 0A ZnmqeAe=0(mod q)|e|定义 1.最小整数解困难问题(shortestintegersolution,
13、SIS).给定正整数,实数,选取随机均匀矩阵,寻找一个非零向量,使其满足,且是困难的.A ZnmqT Zmmqu Znq|eTA|(logn)SamplePre(A,T,u,)Av=u(mod q)v定义 2.原像取样函数(preimagesampleablefunction,PSF).即给定一个函数值,求解其对应的原像.算法输入矩阵,及其格基,向量,参数,运行原像取样函数,在多项式时间内输出满足的采样点.m 2nlogqq 2 m,nSampleBasis(A,Ti)i k=1,2,k A=A1|Ak ZnkmqTiAiq(A)T Zkmkmq定义 3.格基委派算法(latticebasis
14、delegation).给定整数,素数,均为整数,存在一个概率多项式时间算法,其中,为联合矩阵,是的优质基.运行算法输出为格的随机优质基.1.2 GPV 签名框架2008 年,Gentry 等人12设计了一个安全的基于格的数字签名框架.该框架的安全性可归约于最小整数解问题,在 SIS 困难问题的假设下,GPV 框架已被证明在 ROM(randomoraclemodel)和 QROM(quantumrandomoraclemodel)下均有着的 EUF-CMA 安全性,即适应性选择消息攻击下的存在不可伪造性.GPV 签名框架是格基签名方案的认证性理论基础,具有安全简洁的特性,其主要内容如下.n(
15、t0,q,m)参数生成过程:给定安全参数,整数,常计 算 机 系 统 应 用http:/www.c-s-2023年第32卷第10期302研究开发ResearchandDevelopment1(0,1)m1+1(logm)H:0,1 ZnqTrapGen(n,q,m)A ZnmqT Zmmq(pk,sk)AT=0(mod q)|eT|m1+1数,高斯参数.假设为抗碰撞哈希函数.方案使用陷门生成算法获得矩阵以及陷门,并将他们作为公私钥,这里,且.Mr 0,1t0s SamplePre(A,T,H(M|r),)(r,s)Mr 0,1t0As=H(M|r)s m签名和验证过程:对于消息,选取随机字符串
16、,计算,输出即为消息的签名.验证时,若有和等式同时成立,且满足,则认为此签名合法;否则,拒绝签名.2格上基于身份的代理签名方案本文在 GPV 签名框架基础上,使用格基委派技术来产生代理签名密钥,构建了一个基于身份的格上代理签名方案.该方案共分为 5 个阶段,分别为系统建立、密钥提取、代理授权委托、代理签名生成和签名验证.方案流程图如图 1 所示,方案使用符号及符号说明如表 1.2.1 系统建立Setup(1n)m 5nlogq=poly(n)q (logn)l 0SamplePres1,s2SampleBasiss3L:输入整数,实数,整数,两个原像取样函数的高斯参数和两个格基派生函数的安全高
17、斯参数和;3 个安全的哈希函数,分别记作:h1:0,10,1l Znqh2:0,1 Znqh3:0,1 Zn2mq(1)h1l0,1Zqh20,1Zqh30,1Zqn2m其中,表示任意长度的随机字符串和长度为 的字符串可转换为上的多项式;表示任意长度的字符串可转换为上的多项式;表示任意长度的字符串可转换为上一个大小的矩阵.(1)产生相关系统参数以及哈希函数(2)密钥生成中心生成矩阵对,主公钥为A,主私钥为TSetup(1n)123,h h hqqn mm mAZTZ,(1)利用主公钥 A、原始签名者 O、代理签名者 P 的身份信息 idO与 idP,计算矩阵(2)利用主私钥 T,运行算法名者与
18、代理签名者的私钥.(,)iiidKeyExtraction params mk idskiO P=原始签名者 O:(1)根据需求生成授权证书(2)计算(3)生成授权信息(4)授权信息,其中代理签名者 P:12(,)=验证授权:若成立则继续,否则重新授权(,)PProxySignature m sk111(mod),|2idAuqsm=代理密钥生成:(1)计算矩阵(2)合成矩阵(3)运行(,)ooidDelegationGeneration idsk2(|)nOPOPOOPPq h ididZ=u1SamplePre(u,skido,Aid)skido,skidpSampleBasis(Aid,
19、A,T,L),生成原始签12(,)=2=23()nmqBhZ=4(|)nmididqAAABZ=+3(,)idTSampleBasis A sks对消息 M 进行代理签名:(1)任意选取计算(2)运行(3)即为消息 M 的代理签名0,1l,11(,)vh M=12SamplePre(,)A v Ts(,)(1)验证者 V 计算:(2)判断等式:若两者均成立,则接受代理签名;否则,拒绝此代理签名(,)/OPProxyVerify ididMTrue False 13(,),()vh MBh=v2(|)(mod),|s4ididAABqm+=201201|OPlnmidiiqilnmidiiqiA
20、A Aa AZAA AbBZ=+=+安全信道发送图 1签名算法流程图2023年第32卷第10期http:/www.c-s-计 算 机 系 统 应 用ResearchandDevelopment研究开发303 2.2 密钥提取KeyExtraction(params,mk,id)密钥提取阶段输入公共参数,主私钥以及用户身份 id,生成原始签名者与代理签名者的用户私钥,具体如下.TrapGenA Znmqq(A)T ZmmqAT(1)密钥生成中心运行算法生成矩阵以及格的一个陷门基,其中主公钥为,主私钥为.A0,A1,Al ZnmqB0,B1,Bl ZnmqidOidP(2)随机为 O 和 P 选取
21、矩阵,和,结合主公钥 A 和 O 与 P 的身份信息与,计算矩阵:AidO=A|A0+li=1aiAi Zn2mqAidP=A|A0+li=1biBi Zn2mq(2)idO=(a1,a2,al),idP=(b1,b2,bl)0,1l其中,.TSampleBasis(Aid,A,T,L)|eT|T|L|eT|2m(log2m)q(AidO)q(AidP)RidO Z2m2mRidP Z2m2mOskidO=RidOPskidP=RidP|eRidi|L,i=O,P(3)利用主私钥,运行格基委派算法,其中与正交,.输出格和格的一组短基和,产生 的私钥和的私钥,且.2.3 代理委托Delegati
22、onGeneration代理委托算法用于确认代理签名者身份,利用委托证书、原始签名者身份信息及其私钥,生成授权信息,具体如下.OOP(1)原始签名者 根据需求生成授权证书,授权证书中包含 和 的身份信息、代理授权期限以及代理授权范围等内容.Ou=h2(idO|idP|)Znq1 SamplePre(u,skidO,AidO)u12=(2)原始签名者 计算,运行算法,对 进行签名,生成授权信息,同时,令.O=(1,2)(3)原始签名者 将发送给代理签名者.2.4 代理签名生成ProxySignatureM代理签名算法输入消息、代理签名者私钥以及授权信息,产生对应代理签名,具体过程如下.PAidO
23、1=u(mod q)|1|s12m(1)代理签名者 收到 后,首先验证等式和是否成立.若成立,则接受授权,否则需重新授权.B=h3()Zn2mqOPAidOAidPPRidP(2)根据授权信息计算矩阵,再结合 和 的公钥和以及 的私钥,计算矩阵:A=(AidO|AidP+B)Zn4mq(3)T SampleBasis(A,RidP,s3)Ts3s3|RidP|4mlog4m运行生成代理签名密钥,高斯参数 需满足.M(3)对消息进行代理签名,过程如下.0,1lv1=h1(M,)1)随机选取,计算.SamplePre(A,v1,T,s2)2)运行生成.(,)M3)即为消息的代理签名.2.5 签名验
24、证ProxyVerify签名验证函数输入对应的验证信息,输出签名信息的正确性,具体如下.V(idO,idP)v=h1(M,)B=h3()(1)验证者在已知公钥的情况下,计算和.(AidO|AidP+B)=v(mod q)|s24m(2)判断两条件和是否成立.若两者均成立,则代理签名合法;否则,此代理签名为非法签名.3安全性分析 3.1 不可伪造性在分析代理签名的存在性伪造攻击时,一般分为两类伪造者攻击.第 1 类攻击中,代理签名者并未被授权,即此类伪造者已知代理签名者的公私钥和原始签名者的公钥.第 2 类为原始签名者攻击,是指恶意的原始签名者伪装成合法的代理签名者,此类伪造者已经掌握原始签名者
25、的公私钥和代理签名者的公钥.定理 1.如果本文提出的基于身份的代理签名方案被选择身份和固定选择消息攻击成功的概率 不可忽略,那么将存在一个算法 在多项式时间内可解决 SIS 问题.因此在 SIS 问题难解的情况下,该代理签名强不可被伪造.q1h1q2h2q3h3q4q5q6证明:假设存在敌手,通过次询问,次询问,次询问,以及次授权过程询问,次签名询问,次密钥提取询问,能够成功地伪造出代理签名,表 1符号及符号说明符号符号说明O原始签名者P代理签名者授权证书V验证者n系统安全参数Poly(n)n的多项式函数idO原始签名者的身份标识idP代理签名者的身份标识计 算 机 系 统 应 用http:/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 身份 代理 签名 方案