无双线性对的部分盲代理重签名方案

牛淑芬,李文婷,王彩芬

(西北师范大学 计算机科学与工程学院,兰州 730070)

0 概述

自代理重签名的概念被提出以来[1],研究者相继设计了多种代理重签名方案[2-4]。代理重签名的特点主要体现为代理者可将用户(受托者)的签名转换成另一用户(委托者)的签名,在不获取两方用户私钥的同时实现签名转换。此特性使其在现有的网络环境下能够应用于数字版权管理系统、简化证书管理及跨域身份认证等方面[5-7]。由于基于身份的公钥密码体制[8]可减轻用户对证书的依赖,因此结合两者优势,基于身份的代理重签名既能解决繁琐的密钥管理问题,又能满足在签名转换过程中对私钥的保护。

SHAO等人于2007年首次提出基于身份的代理重签名方案[9]。2009年,HU等人在强q-SDH困难问题假设下提出基于身份的代理重签名方案[10]。2014年,冯婕等人利用目标抗碰撞哈希函数提出一种基于身份强不可伪造的代理重签名方案[11]。2015年,TIAN等人构造了格上基于身份的代理重签名方案,用于抵抗量子攻击。2018年,WANG等人利用二次剩余理论提出一种基于身份的代理重签名方案[13]。由于代理者能够获得所转换的消息,因此使用者需要在代理重签名中添加盲性。为保证代理者的权益不被滥用,YANG等人于2018年提出部分盲代理重签名体制[14],并构造了可证明安全的签名方案。

在以上研究中,同类代理重签名中基于身份的密码体制存在运算开销大不利于实际应用的问题,且缺少部分盲性,不能对签名者隐匿待签消息内容,从而造成消息泄露。本文在文献[13]方案的基础上,基于大整数分解困难问题,提出一个单向、单用基于身份的部分盲代理重签名方案,以解决使用双线性对运算开销较大这一问题,并通过部分盲性避免恶意签名滥用。

1 基础知识

大整数分解困难问题为:给定一个合数N满足N=pq,p和q是两个大素数,要求输出p或q。

大整数分解假设为:设l是一个安全参数,N为一个合数满足N=pq,p和q是两个l比特的大素数。如果不存在概率多项式时间的敌手tT以不可忽略的概率εR分解合数N,则称(tT,εR)大整数分解假设成立。

2 形式化定义及安全模型

定义1无双线性对的基于身份的部分盲代理重签名方案由以下9个算法组成:

1)Setup(1λ)→(par,msk):输入安全参数λ,运行系统参数生成算法输出公开参数par和系统主密钥msk。

2)Extract(par,msk,ID)→sk:输入par、msk和用户身份信息ID,PKG运行密钥提取算法输出公私钥对(pk,sk)。

3)Rekey(skA,skB)→rkA→B:输入Alice(受托者)和Bob(委托者)的私钥skA和skB,PKG运行重签名密钥产生算法输出重签名密钥rkA→B。

4)Agree(par)→c:输入par,受托者Alice与代理者Proxy运行协商消息算法生成一个公共消息c。

5)Sign(par,sk,m,c)→(h,σ):输入par、c、消息m和受托者私钥sk,由受托者产生原始签名σ。

6)Blind(h,c,σA,k,pkA)→(h′,σ′A):输入c、消息摘要h、原始签名σA、盲化因子k和受托者公钥pkA,受托者运行盲化算法输出盲化的消息摘要h′和盲化的原始签名σ′A,并发送给代理者。

7)ReSign(rkA→B,c,h′,σ′A,pkA)→σ′B:输入rkA→B、c、h′、σ′A和pkA,代理者首先验证σ′A的合法性,若不合法,输出⊥;否则,代理者运行重签名生成算法输出与委托者公钥pkB对应的部分盲代理重签名σ′B,并发送给受托者。

8)Unblind(σ′B,k,pkB)→σB:输入部分盲代理重签名σ′B、盲化因子k和委托者公钥pkB,受托者首先验证σ′B的合法性,若不合法,输出⊥;否则,受托者运行脱盲算法输出代理重签名σB。

9)Verify(m,c,pk,σ)→{0,1}:输入消息m、公共消息c、对应的公钥pk和签名σ,若关于消息m和公共消息c的签名σ对应于公钥pk合法,验证者接受签名,输出1;否则,输出0。

新方案的安全性分别由存在性不可伪造性和部分盲性构成。存在性不可伪造性在新方案中要求不存在一个外部敌手能够伪造一个新消息的代理重签名。下面先以敌手A与挑战者C的交互游戏来定义方案的存在性不可伪造性。

1)系统建立。挑战者C运行Setup算法获得系统参数par、系统主公钥mpk和系统主密钥msk,挑战者将mpk及系统参数发送给敌手,保密msk。

2)询问。敌手A能够自适应地向挑战者C进行以下询问:

(1)密钥提取询问。当敌手A提交身份ID的密钥提取询问时,挑战者C运行Extract算法输出skID并返回给敌手A。

(2)重签名密钥询问。当敌手A提交(IDA,IDB)的重签名密钥询问时,挑战者C首先对身份IDB进行密钥提取询问来获得skIDB,然后C运行Rekey算法输出重签名密钥rkA→B并返回给敌手A。

(3)签名询问。A与C运行Agree算法产生公共消息c,当敌手A提交(ID,m,c)的签名询问时,挑战者C首先对身份ID进行密钥提取询问来获得skID,然后C运行算法输出原始签名sig并返回给敌手A。

(4)重签名询问。当敌手A提交(sig′A,h′,c,IDA,IDB)的重签名询问时,挑战者C首先验证盲化的sig′A是否为对应于pkA关于盲化消息摘要h′和c的合法签名,若不合法,输出⊥;否则,C对(IDA,IDB)进行重签名密钥询问获得rkA→B,然后运行Resign算法输出部分盲代理重签名sig′B。假设攻击者A在Blind算法中选择k为盲化因子,A最后运行Unblind算法输出(h,c)的重签名。

3)伪造。敌手A输出伪造的签名(sig*,m*,c*,ID*),若满足以下条件,敌手A赢得这个游戏:(1)Verify(sig*,m*,c*,ID*)=1;(2)A没有进行过ID*的密钥提取询问;(3)A没有进行过(ID*,m*)的签名询问;(4)A没有进行过(sigi,h'*,ci,IDi,ID*)的重签名询问,IDi表示任一用户,sigi表示任何一个签名。

定义2若敌手A在以上游戏中攻击成功的概率是可忽略的,则称新的部分盲代理重签名方案在适应性选择消息攻击下是存在性不可伪造的。

部分盲性在新方案中是指代理者不能够将最终的代理重签名与部分盲代理重签名相对应。参考已有的部分盲签名方案的安全定义[16-17],下面将通过敌手B与挑战者D的游戏来定义新方案的部分盲性。

1)系统建立。挑战者D运行Setup算法、Extract算法和Rekey算法,产生系统参数par、受托者和委托者的密钥对(skA,pkA)和(skB,pkB)以及重签名密钥rkA→B,发送par和rkA→B给敌手B。

2)准备。敌手B选择两个长度相等可区分的消息m0和m1,以及公共消息c发送给挑战者D。

3)询问。挑战者D随机选取b∈{0,1},对消息(m0,c)和(m1,c)运行Blind算法,得到盲化的消息摘要与盲化的消息签名(h′b,c,σ′A,b)和(h′b-1,c,σ′A,b-1)发送给敌手B进行重签名。B收到(h′b,c,σ′A,b)和(h′b-1,c,σ′A,b-1)后运行ReSign算法得到部分盲代理重签名σ′B,b和σ′B,b-1并返回给挑战者D。D收到签名σ′B,b和σ′B,b-1后运行Unblind算法进行脱盲得到最终重签名σB,b和σB,b-1,并将(mb,c,σB,b)和(mb-1,c,σB,b-1)返回给敌手B。

4)应答。B输出对b的猜测b′,若b=b′,则B赢得了游戏。

B在上述游戏中获胜的优势定义为:

Adv(B)=|2Pr[b=b′]-1|

定义3若敌手B在以上游戏中攻击成功的概率是可忽略的,则称新的部分盲代理重签名方案具有部分盲性。

3 具体方案

本文基于WANG等人方案[13]设计了一个无双线性对的基于身份的部分盲代理重签名方案,具体算法如下[18]:

2)Extract算法。输入系统参数par、系统主密钥msk和用户身份信息ID,PKG运行密钥提取算法计算用户私钥sk=H(ID)dmodN和pk=H(ID)modN,得到公钥/私钥对(sk,pk)。

4)Agree算法。受托者Alice与代理者Proxy协商一个公共消息c。

7)ReSign算法。输入rkA→B、c、h′、sig′A和受托者的公钥pkA,代理者首先验证(σ′A)2=Rc·pkh′A是否成立,若不成立,输出⊥;否则,代理者计算σ′B=rkA→B·σ′A,最后输出部分盲代理重签名sig′B=(σ′B,R,IDB)发送给受托者。

9)Verify算法。输入消息m、公共消息c、对应的公钥pk和签名σ,验证者验证等式σ2=Rc·pkh是否成立,若成立,验证者接受签名,输出1;否则,输出0。

4 安全性证明与效率分析

4.1 正确性证明

本文方案的正确性证明如下:

Rc·H(IDA)d·2h·H(IDA)2k=

Rc·H(IDA)h·H(IDA)2k=

4.2 不可伪造性证明

证明假设存在一个敌手A能够以不可忽略的概率伪造签名,下面将构造一个算法C作为挑战者与敌手A进行交互游戏,回答A的哈希询问、密钥提取询问、重签名密钥询问、签名询问和重签名询问,从而解决因子分解问题。具体询问过程如下:

1)系统建立。挑战者C运行Setup算法获得系统参数par、系统主公钥mpk和系统主密钥msk,将mpk及系统参数发送给敌手,保密msk。

4)密钥提取询问。挑战者C收到敌手A关于身份IDi的密钥提取询问时,C首先查找Hlist列表中是否有(IDi,ui,pki)的项,若存在,则返回u给A;否则重新进行H()询问获得(IDi,ui,pki)的项并添加至列表Hlist,将ui作为回答返回给敌手A。

4.3 部分盲性证明

定理4本文提出的部分盲代理重签名方案具有部分盲性。

证明敌手B的目的是要将最终的重签名与部分盲代理重签名相对应,所以,本文假设挑战者D拥有任一用户的私钥并且能够产生原始签名,B拥有重签名密钥。下面将以挑战者D与敌手B的交互游戏来证明。

2)准备。敌手B选择两个长度相等可区分的消息m0和m1,以及公共消息c发送给挑战者D。

4)应答。B输出对b的猜测b′。

4.4 效率分析

表1 运算效率比较

由表1可以看出:文献[19]的方案使用了7次双线性对与2次指数运算,使得一般设备难以负担其计算开销,因此,与本文方案相比实用性较差;文献[10]方案虽然增加了部分盲性,但同样存在计算开销大影响实际应用;文献[20]方案存在的安全漏洞为不能抵御受托者的重签名伪造攻击,本文依据给出的安全模型及证明保证了方案的不可伪造性;与文献[13]的方案相比,本文方案在重签名阶段计算效率持平的前提下,增加了部分盲的特性,能够保护受托者的隐私并且保证了代理者的权利不被滥用,可用性更强。

5 结束语

为解决现有部分盲代理重签名方案计算成本高与证书管理难的问题,本文提出一种建立在大整数分解困难问题上基于身份的部分盲代理重签名方案,通过避免使用双线性对提高了计算效率。本文方案在随机预言模型下满足正确性、不可伪造性和部分盲性,效率分析结果也表明了其性能优势。本文方案不满足双向、多用的特性,在应用中具有一定程度的局限性,因此,下一步工作将在此方面对方案进行改进。