高效的在线/离线代理重签名方案

杨小东 王彩芬

(西北师范大学数学与信息科学学院 兰州 730070)

1 引言

数字签名在保证数据的机密性、完整性和不可否认性等方面起着极为重要的作用，被广泛用于设计电子支付、电子投标、电子拍卖、电子彩票和电子投票等应用协议，是安全电子商务和安全电子政务的关键技术之一。根据实际应用背景的需要，人们提出了诸多特殊的数字签名方案，代理签名就是其中的一种。代理签名将签名者的某些权利委托给可靠的代理者，让代理者代表签名者行使相应的签名权利。但在代理签名中，委托者必须高度信任代理者。

为了分散代理者的签名权利，文献[1]提出了代理重签名的概念。在代理重签名中，一个拥有重签名密钥的半可信代理者(semi-trusted proxy)将受托者(delegatee)的签名(也称原始签名)转换为委托者(delegator)对同一消息的签名(也称重签名)，但这个代理者不能单独生成受托者或委托者的任何原始签名。所谓半可信，指的是仅仅相信这个代理者一定会按方案进行签名的转换。代理重签名在简化证书管理、管理群签名、提供遍历的路径证明、构造审查系统和数字版权管理系统等方面有广泛的应用前景[2]。

在线/离线签名[3]是把数字签名分成两个阶段的签名方式，它是为了提高签名方案的效率而提出来的一种解决方案。第1阶段是离线阶段，在未知签名消息的情况下进行签名预计算。由于此阶段有足够的时间，因而离线阶段签名算法并不影响消息的签名速度；第2阶段是在线阶段，这是在消息出现后开始的，由于离线阶段已做了预计算，所以此阶段签名速度非常快。在线/离线签名在现实中有广泛的应用，如智能卡等。

在已有的代理重签名方案中[1,2,4-7]，重签名生成算法中有幂指数运算，严重影响了代理重签名方案的签名效率。为了改善代理重签名的性能，本文基于变色龙哈希函数提出了一个在线/离线代理重签名方案。该方案将代理重签名的特性与在线/离线签名的特性进行了有效融合，能将已有的任意一个代理重签名方案转换为一个高效的在线/离线代理重签名方案。在线/离线代理重签名大大提高了代理重签名的实时性和安全性，可应用在重签名时间受限或重签名设备计算能力有限的场合，如无线传感器网络、无线路由器协议、PDA等。如果是时间受限，在空闲时间进行离线阶段的运算，将计算结果保存，预备用于在线阶段的重签名运算；如果是设备的计算能力有限，让具有较强计算能力的设备进行离线阶段的计算，将计算结果存储在计算能力有限的设备上，用于在线阶段进行重签名。代理重签名是近年来密码学研究的一个热点，主要集中于研究代理重签名[1,2,4-7]、盲代理重签名[8]、无证书代理重签名[9]和门限代理重签名[10]等，但关于在线/离线代理重签名的公开文献几乎没有。

2 预备知识

2.1 椭圆曲线离散对数假设

选择大素数t,E(Ft)是定义在有限域Ft上的一个椭圆曲线，#E(Ft)是E(Ft)中点的数目。点P∈E(Ft),P的阶为素数q，这里q|#E(Ft)。G是P生成的一个q阶循环群。椭圆曲线离散对数问题(ECDLP)：给定 (P,P1)∈E(Ft)，寻找一个整数a∈Zq，使得在G中有P1=aP。

定义 1(椭圆曲线离散对数假设)如果没有一个概率多项式时间算法在时间T内以至少ε的概率解决群G上的椭圆曲线离散对数问题，则称群G上的(T,ε)-ECDLP假设成立。

2.2 变色龙哈希函数

变色龙哈希函数CH(⋅,⋅)是一种特殊的哈希函数[3]，拥有一个门限密钥TK和一个公钥HK，并且满足以下性质：

(1)有效性：给定公钥HK，一个消息m和一个随机数r，存在一个多项式时间算法计算CHHK(m,r)。

(2)抗碰撞性：输入公钥 HK，不存在任何一个概率多项式时间算法以一个不可忽略的概率输出(m1,r1)和 (m2,r2)，使得m1≠m2且 C HHK(m1,r1)=CHHK(m2,r2)。

(3)门限碰撞：给定门限密钥 TK，公钥 HK，两个不同的消息 (m1,m2)和一个随机数r1，一定存在一个概率多项式时间算法输出一个值r2，使得CHHK(m1,r1)=CHHK(m2,r2)；如果r1服从均匀分布，则r2服从的分布与均匀分布在计算上是不可区分的。

2.3 基于椭圆曲线离散对数假设的变色龙哈希函数

基于椭圆曲线离散对数假设，构造一个变色龙哈希函数，利用它构造在线/离线代理重签名方案。选择大素数t,E(Ft)是定义在有限域Ft上的一个椭圆曲线，#E(Ft)是E(Ft)中点的数目。点P∈E(Ft),P的阶为素数q，这里q|#E(Ft)。G是P生成的一个循环群。定义一个安全的哈希函数f：Zq×G→Zq。具体描述如下：

(1)门限密钥生成算法：选择两个随机数k,x∈Zq，计算Y=xP,K=kP，则门限密钥TK=(k,x)，公钥HK=(K,Y)。

(2)哈希函数生成算法：对于公钥HK=(K,Y)，构造变色龙哈希函数CHHK：Zq×Zq→G，定义为CH(m,r)=f(m,K)P+rY。

定理1CH(m,r)=f(m,K)P+rY是一个基于椭圆曲线离散对数假设的变色龙哈希函数。

证明下面证明CH(m,r)=f(m,K)P+rY满足变色龙哈希函数的性质：

(1)有效性 给定公钥HK=(K,Y)，一个消息m∈Zq和一个随机数r∈Zq，在多项式时间内能计算出CH(m,r)=f(m,K)P+rY。

(2)抗碰撞性 给定公钥HK=(K,Y)，假设存在一个概率多项式时间算法以一个不可忽略的概率输出 (m1,r1)和 (m2,r2)，使得 C H(m1,r1)=CH(m2,r2)且m1≠m2，则在多项式时间内能计算出Y的离散对数x。即f(m1,K)P+r1xP=f(m2,K)P+r2xP。

于是有

因为椭圆曲线离散对数是个困难问题，而上述结论与椭圆曲线离散对数假设相矛盾，所以这个概率多项式时间算法不存在。即变色龙哈希函数满足抗碰撞性。

(3)门限碰撞 给定公钥HK=(K,Y)，门限密钥TK=(k,x)，两个不同的消息 (m1,m2)和一个随机数r1，寻找r2使得 C H(m1,r1)=CH(m2,r2)。可通过下式在多项式时间内计算出r2，

如果r1在Zq中服从均匀分布，那么r2在Zq中也服从均匀分布。 证毕

3 在线/离线代理重签名的形式化定义

定义 2 (代理重签名)一个代理重签名方案PRS=(KeyGen,ReKey,Sign,ReSign,Verify)由以下5个算法组成[2]：

(1)KeyGen是密钥生成算法：输入一个安全参数1k，输出系统参数和用户的公私钥对(pk,sk)。

(2)ReKey是重签名密钥生成算法：输入一个受托者的公私钥对(pkA,skA)和一个委托者的公私钥对(pkB,skB)，输出一个重签名密钥rkA→B。代理者使用rkA→B可将受托者的签名转换为委托者的签名。

(3)Sign是签名生成算法：输入一个消息m和一个私钥sk，输出一个消息m的签名σ。可用对应的公钥pk来验证签名σ的合法性。

(4)ReSign是重签名生成算法：输入一个重签名密钥rkA→B，一个消息m，一个公钥pkA和一个签名σA，该算法首先验证σA的合法性，若Verify (pkA,m,σA)=1，则输出一个对应于公钥pkB的消息m的签名σB；否则，输出⊥。

(5)Verify是签名验证算法：输入一个消息m，一个公钥pk和一个签名σ，如果σ是对应于公钥pk的消息m的合法签名，输出1；否则，输出0。

Ateniese和Hobenberger定义了代理重签名的安全模型[2]：外部安全和内部安全。外部安全性可使用户免受来自系统外部的攻击者的恶意攻击，而内部安全性主要考虑来自系统内部的攻击，如代理者发起的攻击或他与委托双方中其中一方的合谋攻击。如果没有一个攻击者在多项式时间内以不可忽略的优势伪造PRS方案的合法签名，则称PRS方案在适应性选择消息攻击下是不可伪造的[2,4]。

定义 3(在线/离线代理重签名)一个在线/离线代理重签名方案 OPRS=(RekeyOn/Off,ReSignOn/Off,Ver)由以下3个算法组成：

(1)RekeyOn/Off是重签名密钥生成算法：输入一个安全参数1k，输出系统参数params、用户的公私钥对(pk,sk)和代理者的重签名密钥rkA→B。

(2)ReSignOn/Off是重签名生成算法：该算法分以下两个阶段进行：

(a)离线阶段：输入私钥和重签名密钥，输出状态信息Ki。

(b)在线阶段：输入一个消息m，一个公钥pkA，消息m的签名ρA，状态信息Ki和私钥，首先验证ρA的合法性，若Verify (pkA,m,ρA)=1，则输出一个对应于公钥pkB的消息m的重签名ρB；否则，输出⊥。

(3)Ver是签名验证算法：输入一个消息m，一个公钥pk和一个签名ρ，如果ρ是对应于公钥pk的消息m的合法签名，输出1；否则，输出0。

攻击模型：采用在静态攻陷模式下挑战者C和攻击者A之间的游戏来定义在线/离线代理重签名的安全性模型。攻击者A在游戏开始前必须确定已被攻陷的用户，攻击游戏分3个阶段进行。首先是建立阶段，挑战者C生成系统参数 params，并将params发送给攻击者A。其次是查询阶段，攻击者A可以适应性地向挑战者C进行用户的公钥/私钥询问、重签名密钥询问、签名询问和重签名询问，挑战者C通过相应的预言机(密钥预言机、重签名密钥预言机、原始签名预言机和重签名预言机)响应攻击者所发起的各种询问请求，并将询问结果返回给攻击者A。这个阶段的安全性定义与一般的代理重签名的安全性定义[2,4]基本相同。最后是伪造阶段，攻击者A输出一个伪造，即一个消息/签名对。

如果攻击者A能生成一个新消息m的合法签名，那么我们就说攻击者A伪造成功。攻击者A在上面游戏中的优势可以定义AdvA=Pr[A succeeds]，这个概率完全取决于挑战者A和攻击者C之间的抛币概率。

定义 4(不可伪造性)如果没有一个攻击者在多项式时间内以不可忽略的优势赢得上述游戏，那么称在线/离线代理重签名方案 OPRS在适应性选择消息攻击下能抵抗存在性伪造。

基于变色龙函数构造的在线/离线代理重签名方案，其安全性可归约为所关联的代理重签名的安全性或变色龙函数的安全性。如果攻击者输出一个在线/离线代理重签名的伪造，则可利用这个伪造构造一个所关联的代理重签名的伪造或找到变色龙函数的一个碰撞。因此，只要所基于的代理重签名方案是安全的且变色龙哈希函数具有抗碰撞性，则相应的在线/离线代理重签名方案也是安全的。

4 在线/离线代理重签名方案

基于变色龙哈希函数CH(m,r)=f(m,K)P+rY，本文提出了一个在线/离线代理重签名方案。该方案可将已有的任意一个代理重签名方案[1,2,5-8]转换为一个相应的在线/离线代理重签名方案，用PRS表示这些方案中的任意一个代理重签名方案。选择大素数t,E(Ft)是定义在有限域Ft上的一个椭圆曲线，#E(Ft)是E(Ft)中点的数目。P∈E(Ft),P的阶为素数q,q|#E(Ft)。G是P生成的一个循环群。签名的消息mi∈Zq，可通过哈希函数g：{0,1}*→Zq延伸签名消息空间。选择安全的哈希函数f：Zq×G→Zq。

4.1 方案描述

假定PRS=(KeyGen,ReKey,Sign,ReSign,Verify)是一个安全的代理重签名方案[2,5-8]，则相应的在线/离线代理重签名方案 OPRS=(RekeyOn/Off,ReSignOn/Off,Ver)由以下3个算法组成：

(1)RekeyOn/Off：主要生成系统参数、用户的公私钥对和重签名密钥，具体描述如下：

(a)输入安全参数1k，运行PRS的KeyGen算法生成系统参数params和用户的公私钥对(pk,sk)。

(b)输入受托者的公私钥对(pkA,skA)和委托者的公私钥对(pkB,skB)，运行PRS的ReKey算法生成重签名密钥rkA→B。

(c)选择一个随机数x∈Zq，计算Y=xP,X=x-1，则TK=x,HK=Y。

(d)选择一个随机数k*∈Zq，计算h=k*Y。

(e)运行PRS的Sign算法生成受托者对h的原始签名σA。即代理者请求受托者生成h的原始签名σA，但代理者不知道受托者的私钥skA的任何信息。

(f)运行PRS的ReSign算法生成委托者对h的重签名σB。即代理者使用rkA→B将受托者对h的签名σA转换为委托者对h的重签名σB。

公开参数(params,pkA,pkB,E(Ft),G,t,q,f,g,CH(⋅,⋅),σA,σB,Y,h)，代理者的重签名密钥是(rkA→B,x,X,k*)。

(2)ReSignOn/Off：给定一个重签名密钥(rk,x,X,k*)，代理者进行如下操作：A→B

(a)离线阶段：

(i)选择一个随机数ki∈Zq，计算Ki=ki P；

(ii)保存状态信息Ki。

(b)在线阶段：输入一个待签名的消息mi∈Zq，一个公钥pkA和消息mi的签名ρAi，代理者进行如下操作：

(i)提取状态信息Ki；

(ii)计算ri=k*-f(mi,Ki)X(modq)；

(iii)委托者对消息mi的重签名ρB=(ri,Ki,σB,ρAi)；因为σB作为公开参数发布，所以mi的重签名实际上是ρB=(ri,Ki,ρAi)。

(3)Ver：输入一个消息mi，委托者的公钥pkB和一个签名ρB=(ri,Ki,ρAi)，为了验证ρB是对应于公钥pkB的消息mi的有效签名，进行如下操作：

(a)计算CH(mi,ri)=f(mi,Ki)P+riY；

(b)运行PRS的Verify算法，如果Verify (pkA,mi,ρAi)=1 且 Verify(pkB,CH(mi,ri),σB)=1，那么ρB是委托者对消息mi的合法重签名，输出1；否则，输出0。

4.2 正确性分析

因为σB是PRS中委托者对h的有效重签名，所以σB也是 PRS中委托者对CH(mi,ri)的合法重签名。

4.3 安全性分析

定理2 在随机预言模型下，如果循环群G上的(T,ε)-ECDLP假设成立，代理重签名方案PRS=(KeyGen,ReKey,Sign,ReSign,Verify)在适应性选择消息攻击下是不可伪造的，那么本文所提的在线/离线代理重签名方案 OPRS=(RekeyOn/Off,ReSignOn/Off,Ver)在适应性选择消息攻击下也是不可伪造的。

证明假设A是在线/离线代理重签名方案OPRS的一个攻击者，OPRS的挑战者将公开参数(params,pkA,pkB,E(Ft),G,t,q,f,g,C H(⋅,⋅))发送给A。qS表示A询问签名预言机(包括原始签名预言机和重签名预言机)的最大次数，qf表示A询问哈希函数预言机的最大次数。假设(mi,Ki)是A第i次询问哈希函数预言机的输入，预言机返回相应的哈希函数值ei;mj是A第j次询问签名预言机的输入，预言机返回相应的签名攻击者A在适应性选择消息攻击下在时间T内以不可忽略的概率ε成功伪造OPRS的一个签名(m,r,K,ρA)，即

给定系统参数(params,pkA,pkB,E(Ft),G,t,q,f,g,CH(⋅,⋅))，定义一个概率多项式时间算法B，利用攻击者A的伪造解决一个椭圆曲线离散对数问题的实例。假设B收到的椭圆曲线离散对数问题实例是(P,aP)∈G,B的目标是确定aP的离散对数a∈Zq。B进行如下的操作：

(1)选择一个随机数b∈Zq，令Y=aP，计算h=bY=abP；运行PRS的Sign算法生成h的原始签名σA；运行PRS的ReSign算法生成h的重签名σB；公开(σA,σB,Y,h)。

(2)维持一个列表，记为f-list，初始值为空。对于A的第i次哈希函数值询问(mi,Ki),B首先检查列表f-list中是否存在(mi,Ki)，如果存在，返回ei；否则，从Zq中随机选取ei，将(mi,Ki,ei)添加到f-list中并返回ei。

(3)对于A的第j(1 ≤j≤qS)次签名询问mj,B首先检查列表f-list中是否存在若存在，则计算否则，从Z中随机q选取)，计算加到f-list中。然后询问签名预言机获得受托者对消息mj的原始签名。最后B返回消息mj的签名

挑战者B返回给攻击者A关于mi的签名与攻击者A询问OPRS的签名预言机获得的签名，在计算上是不可区分的。最后，攻击者A以大于等于ε的概率输出 OPRS的一个伪造(m,r,K,ρA)，这里h=f(m,K)P+rY,m≠mi,i=1,…,qS。 根 据Forking引理[9]，假设对于不同的哈希函数值f(m,K)和f'(m,K)，攻击者A输出同一消息m的两个合法的 OPRS签名(m,r,K,ρA)和(m,r',K,ρA)，其中h=f(m,K)P+rY,h=f'(m,K)P+r'Y，存在下面的等式：

于是，攻击者B以大于等于ε的概率解决了椭圆曲线离散对数问题的一个实例(P,aP)∈G。如果循环群G上的(T,ε)-ECDLP假设成立，那么本文所提的在线/离线代理重签名方案 OPRS=(RekeyOn/Off,ReSignOn/Off,Ver)在适应性选择消息攻击下是不可伪造的。 证毕

4.4 有效性分析

在本文所提的在线/离线代理重签名方案中，重签名密钥生成算法的运算主要包括两次椭圆曲线点乘计算，一次代理重签名方案中的密钥生成算法的执行，一次重签名密钥生成算法的执行，一次签名算法的执行和一次重签名算法的执行。由于σB和h是公开参数，σB是h的合法重签名，于是只需验证CH(mi,ri)=f(mi,Ki)P+riY=h，所以签名验证算法Ver的运算实际上是一次变色龙哈希函数值的计算和两次代理重签名方案中的签名验证算法 Verify的执行。离线阶段重签名算法是一次椭圆曲线点乘运算。在线阶段的重签名算法是寻找变色龙哈希函数的一次碰撞，而寻找这样的一次碰撞仅需要一次模乘法算法和一次模减法运算。由于消息mi的重签名ρB=(ri,Ki,ρAi)，所以本方案与大部分代理重签名方案[6,7,10]的重签名长度基本相同。

Ateniese等人[2]指出代理重签名方案BBS是不安全的。在BBS方案中，任何人都能通过原始签名和重签名计算出重签名密钥并且成为恶意代理者；进一步，委托者(或受托者)可以从重签名密钥计算出受托者(或委托者)的私钥，所以本方案不与 BBS方案进行签名效率的比较。一旦签名消息到来时，在线阶段生成实际消息的重签名，因此在线/离线代理重签名方案的重签名效率只考虑在线阶段。将已有的代理重签名方案和本方案的重签名算法进行签名效率比较，其结果见表1。

表1 重签名算法的性能比较

从表1中可以看出，在本文所提的在线/离线代理重签名方案中，在线重签名算法仅需要1次模减法运算和1次模乘法运算；当签名消息到来时，能在很短的时间生成消息的重签名。而模减法运算和模乘法运算相对于模幂运算和配对运算而言，其计算量是可以忽略不计的。所以，本文所提的在线/离线代理重签名方案大大改善了代理重签名方案的性能，更适用于网络安全应用。

5 结束语

结合门限代理重签名与变色龙哈希函数，本文提出了一个在线/离线代理重签名方案，该方案能将任意一个安全的代理重签名方案转换为一个相应的在线/离线代理重签名方案。在随机预言模型下证明了该方案在适应性选择消息攻击下是不可伪造的，并与已有的代理重签名方案进行了性能比较，其结果表明本方案重签名效率更高，仅需要1个模减法运算和1个模乘法运算就能生成消息的重签名，具有一定的实用性。将来的工作是设计在标准模型下可证安全的在线/离线代理重签名方案。

[1]Blaze M,Bleumer G,and Strauss M.Divertible protocols and atomic proxy cryptography[C].Proceedings of EUROCRYPT’98,Helsinki,Finland,May 31-June 4,1998：127-144.

[2]Ateniese G and Hohenberger S.Proxy re-signatures：new definitions,algorithms,and applications[C].Proceedings of the 12th ACM CCS,Alexandria,USA,Nov.7-11,2005：310-319.

[3]Chen X,Zhang F,Tian H,et al..Efficient generic on-line/off-line signatures without key exposure[C].Proceedings of ACNS 2007,Zhuhai,China,June 5-8,2007：18-30.

[4]Shao J,Feng M,Zhu B,et al..The security model of unidirectional proxy re-signature with private re-signature key[C].Proceedings of the 15th Australasian Conference on Information Security and Privacy,Sydney,Australia,July 5-7,2010：216-232.

[5]Shao J,Cao Z,Wang L,et al..Proxy re-signature schemes without random oracles[C].Proceedings of INDO-CRYPT 2007,Chennai,India,Dec.9-13,2007：197-209.

[6]Sherman C and Raphael P.Proxy re-signatures in the standard model[C].Proceedings of the 11th International Conference on Information Security,Taibei,China,Sept.15-18,2008：260-276.

[7]Benoit L and Damien V.Multi-use unidirectional proxy re-signatures[C].Proceedings of the 15th ACM Conference on Computer and Communications Security,Alexandria,USA,Oct.27-31,2008：511-520.

[8]Kiate K,Ikkwon Y,and Secogan L.Remark on shao et al'.s bidirectional proxy re-signature scheme in indocrypt'07[J].International Journal of Network Security,2009,9(1)：8-11.

[9]David P and Jacques S.Security arguments for digital signatures and blind signatures[J].Journal of Cryptology,2000,13(3)：361-369.

[10]Deng Y,Du M,and You Z,et al..A blind proxy re-signatures scheme based on standard model[J].Journal of Electronics＆Information Technology,2010,32(5)：1119-1223.