简单的通用可组合代理重签名方案编程频道|福州电脑网

2024年4月28日发(作者：)

ISSN 1000-9825, CODEN RUXUEW E-mail: jos@

Journal of Software, Vol.21, No.8, August 2010, pp.2079−2088

doi: 10.3724/SP.J.1001.2010.03634 Tel/Fax: +86-10-62562563

简单的通用可组合代理重签名方案

洪璇

, 陈克非

2,3

, 万中美

∗

(上海师范大学计算机科学与技术系,上海 200234)

(上海交通大学计算机科学与工程系,上海 200240)

(现代通信国家重点实验室,四川成都 610041)

Simplified Universally Composable Proxy Re-Signature

HONG Xuan

, CHEN Ke-Fei

2,3

, WAN Zhong-Mei

(Department of Computer Science and Technology, Shanghai Normal University, Shanghai 200234, China)

(Department of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai 200240, China)

(National Laboratory of Modern Communications, Chengdu 610041, China)

Corresponding author: E-mail: ng@

Hong X, Chen KF, Wan ZM. Simplified universally composable proxy re-signature. Journal of Software, 2010,

21(8):2079−2088. /1000-9825/

Abstract: The paper presents a simple proxy re-signature scheme and its two equivalent security model. One is

based on the universal composability framework, another is game-based security model. The proposed scheme is

bidirectional, multi-use, transitive and key optimal. It is very attractive for its simplicity. Its security can be reduced

to the Computational Diffie-Hellman assumption in the Random Oracle Model. It is also secure under the universal

composability framework.

Key words: proxy re-signature; universally composable; provable security

摘要: 给出一个简单的代理重签名方案及其两个等价的安全模型:基于通用可组合安全框架的安全模型和基于

游戏的安全模型.提出的方案是双向的、多用的、可传递的和密钥最优化的,其安全性可以规约到随机预言机模型

下的计算Diffie-Hellman假设.该方案同时也满足通用可组合安全性.

关键词: 代理重签名;通用可组合安全;可证明安全

中图法分类号: TP309 文献标识码: A

Blaze等人

[1]

在1998年的EUROCRYPT中首次提出了代理重签名的概念.一个拥有某些额外信息的半可信

代理人可以把受理人的签名转换为授权人关于同一个消息的签名,而这个代理人不能得到受理人或授权人的

签名密钥,也不能任意生成他们的签名.代理重签名的概念虽然很早就被提出来了,但是由于Blaze等人

[1]

没有

∗

Supported by the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z456 (国家高技术研究

发展计划(863)); the National Basic Research Program of China under Grant No.2007CB311201 (国家重点基础研究发展计划(973)); the

National Laboratory of Modern Communications of China under Grant No.9140C1103020803 (现代通信国家重点实验室); the Shanghai

Normal University General Project of China under Grant 201037 (上海师范大学一般项目)

Received 2008-09-09; Revised 2009-01-14; Accepted 2009-03-31

2080

Journal of Software 软件学报 Vol.21, No.8, August 2010

给出代理重签名的形式化规范的定义,所以人们不能很好地认识其优点,也很容易把它与其他签名类型(如代理

签名、传递签名、群签名、多签名、聚合签名等)相混淆.为了改变这种情况,Ateniese等人

[2]

对代理重签名给出

了形式化的定义,特别是与上述几种签名类型进行区别.代理重签名方案由于其独特的签名转换功能,可以应用

于许多应用场景

[3,4]

,如简化证书管理、路径证明、管理群签名、构造DRM的跨域操作系统等.例如,通过代理

重签名可以简化不同证书中心(certificate authority,简称CA)的用户之间建立安全信道的过程.只要CA1和CA2

之间存在一个半可信的代理人,它就能暂时地把CA1的证书转换为CA2的证书,使得用户之间建立安全信道的

过程更为快捷.一般来说,代理重签名可以通过双向性或单向性、多用性或单用性、传递性或非传递性、密钥

最优化这几个属性

[2,5]

来进行分类.

多用的.但是,在受理人签名的产生过程首个代理重签名方案

[1]

是由Blaze等人提出来的.该方案是双向的、

和签名转换的过程中,用户需要进行k个指数计算,计算效率低下,因此,该方案不适合在实际应用中使用.虽然在

2003年Ivan和Dodis

[6]

再次讨论了代理重签名体制,但是他们所给出的方案对于每个授权过程都需要存储一个

相应的秘密信息,没有实现密钥最优化.Ateniese等人

[2]

首次形式化了代理重签名定义及其安全模型,并提出两

个方案,其中,S

是双向的和多用的,S

uni

是单向的和单用的.但是,他们对安全属性的描述不够简练,所给出的用

公式表示的安全模型存在很多冗余.第一个可证明安全的代理重签名方案S

是由Shao等人

[5]

提出来的,同时

还提出了第一个基于身份的方案S

id-mb

.这两个方案最主要的问题是需要大量的公开参数和耗时的计算.而且他

们定义的安全模型有很多限制,影响了方案在实际应用中的推广.

代理重签名是现代密码学的一个新兴研究领域.本文给出了代理重签名的形式化定义和两个等价的安全

模型:基于UC框架的安全模型和基于游戏的安全模型.这两个安全模型的等价确保了如果方案满足常用的基

于游戏的安全模型,那么该方案同时还具有通用可组合性.本文提出的基于游戏的安全模型吸收了以往的工作

成果,进行了一些改进,去除了一些限制,简化了一些描述.首先允许攻击者能够控制“corrupted”用户和“honest”

用户之间的代理人,其次确保了授权人和受理人的秘密信息的安全性.而本文的基于UC框架的安全模型则是

首次针对代理重签名概念提出来的.本文还提出了具有UC安全的双向代理重签名方案

BPRS

.方案

BPRS

是在

ElGamal族三元签名方案的基础上增加再签名密钥生成算法和再签名算法后变形得到的.与其他方案相比,方

案

BPRS

更简单,更容易应用于现有方案.方案

BPRS

是双向的、多用的、传递的和密钥最优的,其安全性可以规约

到随机预言机模型下的计算Diffie-Hellman假设.因为已经证明了两个安全模型等价,所以方案

BPRS

还具有通

用可组合安全性.

1 背景知识

1.1 代理重签名

定义1.1. 一个代理重签名方案由5个多项式时间算法(KeyGen,ReKey,Sign,ReSign,Verify)组成:

• KeyGen(1

)→(pk,sk).输入安全参数1

,密钥生成算法KeyGen输出一对公私钥(pk,sk).

• KeyGen(sk

,sk

)→(rk

a↔b

).输入用户A和用户B的密钥sk

,sk

,再签名密钥生成算法ReKey输出A和B

之间的再签名密钥rk

a↔b

• Sign(sk,m)→

.输入私钥sk、消息m,签名算法Sign输出消息m的签名

.该签名可以用对应sk的公钥

pk验证.称这种形式的签名为原始签名.

消息m、用户A的公钥pk

以及用pk

可以验证的m

• Resign(rk

a↔b

,pk

,m,

)→

′.输入再签名密钥rk

a↔b

、

的签名

,再签名算法Resign输出消息m的新签名

′.该签名可以用用户B的公钥pk

验证.称这种形式

的签名为再签名.

• Verify(pk,m,

)→f.输入消息m、公钥pk和签名

,如果签名

确实是可以用pk验证的m的签名,则验证

算法Verify输出1;否则,输出0.

洪璇等:简单的通用可组合代理重签名方案

1.2 通用可组合安全框架

2081

现有的绝大多数协议分析都需要先确立正确的模型,但一个完整的模型需要考虑的状态和情况非常多,难

以考虑周全.于是为了简化,许多协议的设计都是简单地考虑单一协议执行的情况.当协议应用到其他环境中

时,安全性就需要重新定义,从而带来了安全定义的指数爆炸性增长,给上层协议的安全性证明带来无法估量的

难度.于是,研究者们迫切需要一种新的研究方法和路线来应付日益复杂的协议运行环境,比如Internet.通用可

组合安全框架(简称UC框架)

[7,8]

正是适合这个要求的一种协议分析框架.其最优秀的性质就是模块化设计思

路:首先单独设计某个协议,只要该协议满足UC安全性,就保证了它与其他协议并行运行时的安全性.

UC框架由3个模型搭建而成:现实模型、理想模型以及混合模型.现实模型描述实际协议

执行的情况.理

想模型描述协议执行的理想情况,即通过理想功能(ideal functionality)F描述希望达到的任务.混合模型则是将

现实模型和理想模型进行混合.该模型中的协议可以访问理想功能.建立起这些模型之间的桥梁就是仿真.仿真

可以将现实模型的安全规约到理想模型的安全.如果攻击者攻击现实模型下的协议

不比攻击理想模型下的F

获得更大的影响或者更多的信息,那么

至少是和F一样安全的.

它与Bellare等人

[9]

于1998年提出的模式(modular)方法设计密钥交换协议有相近之处.但是,Bellare等人的

安全模型只是针对密钥交换协议所给出的,其安全在于攻击者与实际系统交互的结果和与理想系统交互的结

果一样多.而UC框架则是针对任意环境、任意攻击给出协议的描述.UC框架使用了“不可区分”的思想,通过仿

真说明现实模型与理性模型是不可区分的.为了更好地描述仿真的结果,引入环境机Z代表协议运行的整个外

部环境.它提供协议所有的输入,并读取协议所有的输出.

定义1.2(协议

安全实现理想功能F). 如果对于现实模型中任意的攻击者A都存在一个理想模型中的攻击

者S,在任何输入情况下,现实模型中运行A和协议

的环境机Z的输出,与理想模型中运行S和理想功能F的环

境机Z的输出都是不可区分的,则说协议

安全实现理想功能F.

定理1.3(通用可组合定理). 如果协议

安全实现了理想功能F,且协议

和理想功能F都是

的子程序,则协

议

安全仿真混合协议

.其中,

表示F-混合模型中的协议,

则表示

中对F的调用都以对

的调用来替代.

1.3 双线性配对

群G

和G

分别表示阶是素数p=

)的乘法交换群.令群G

和G

上的离散对数问题都是难解的.双线性

配对e是一个映射e=G

×G

→G

,满足3条性质:

abab

(1) 双线性性.对于所有g,h∈G

a,b∈

]

,都有e(g,h)=e(g,h).

(2) 可计算性.对于所有g,h∈G

,存在多项式时间算法计算配对e(g,h)∈G

(3) 非退化性.g是群G

的生成元,e(g,g)≠1.

1.4 计算Diffie-Hellman假设问题

群G的阶是素数p=

),g是群G的生成元.CDH问题:给定〈g,g

〉,其中,

a,b∈

]

,计算g.

假设算法A能够解决G上的CDH问题,而A的成功概率可以表示为Adv

=Pr[A(g,g

)→g

].如果对于所

有的算法都有Adv

是可忽略的,则称CDH问题是困难的.

2 代理重签名的安全模型

这一节给出代理重签名方案的基于游戏的安全模型和基于通用可组合安全框架的安全模型,并证明这两

个安全模型的等价性.如果方案符合常用的基于游戏的安全定义,那么该方案同时也满足通用可组合安全性.

2.1 基于游戏的安全模型

在吸收了以往工作成果

[1,2,5]

的基础上,本文定义了代理重签名的基于游戏的安全模型.它对以前的工作进

行了一些改进,去除了一些限制,简化了一些描述.首先允许攻击者能够控制在攻破用户和未被攻破用户之间的

代理人,其次确保授权人和受理人秘密信息的安全性.本文不仅考虑了外部用户不能得到方案的任何信息,而且

2082

Journal of Software 软件学报 Vol.21, No.8, August 2010

考虑了在代理人和授权人(受理人)都被控制的情况下,如何保证受理人(授权人)的安全.另外,本文采用的仍然

是静态攻击的模型,即在这个安全模型中,攻击者必须在游戏开始前就决定需要攻破哪些用户.代理重签名的基

于游戏的安全模型是从正确性、一致性和不可伪造性

[10]

加以说明.

• 正确性.代理重签名方案若满足正确性,就需要满足下面两个条件:首先,对于任意一个在消息空间里的

消息m和任何从算法KeyGen(1

)产生的公私钥对(pk,sk),计算

←Sign(m,sk),方案必须满足条件

Verify(pk,m,

)=1;其次,对于任意一个消息空间内的消息m,任何从算法KeyGen(1

)产生的公私钥对

(pk

,sk

),(pk

,sk

)和再签名密钥rk

a↔b

←ReKey(sk

,sk

),若A的签名是

←Sign(m,sk

),则方案还必须满足

条件Verify(pk

,m,ReSign(rk

a↔b

,m,

))=1.

• 一致性.如果代理重签名方案满足一致性,那么对于任何在消息空间里的消息m、公钥pk和签名

,两次

调用验证算法Verify(pk,m,

)必定得到相同的结果.

• 不可伪造性.通过挑战者和攻击者之间的游戏来定义代理重签名的不可伪造性.

定义2.1(PRS CMA game). 游戏由攻击者A查询一系列的随机预言机所组成:

(1) 查询

用户密钥预言机O

CkeyGen

.攻击者A输入查询某个用户的公钥pk,且该公钥是由密钥生成算法KeyGen合法

生成的公钥,则用户密钥预言机O

CKeyGen

返回攻击者A公钥pk相应的私钥sk.

再签名密钥预言机O

ReKey

.攻击者A输入查询两个用户的公钥pk

,pk

,其中,pk

,pk

是由密钥生成算法

KeyGen合法生成的公钥.再签名密钥预言机O

ReKey

返回攻击者A再签名密钥rk

a↔b

←ReKey(sk

,sk

),其中,sk

,sk

是对应于pk

,pk

的密钥.

签名预言机O

Sign

.攻击者A输入查询(pk,m),其中,pk是由算法KeyGen合法生成的公钥,m是消息空间中任

意的消息.签名预言机O

Sign

返回攻击者A签名

←Sign(sk,m),其中,

可以用对应于sk的公钥pk验证.

再签名预言机O

ReSign

:攻击者A输入查询(pk

,pk

,m,

),其中,pk

,pk

是由算法KeyGen合法生成的公钥,

是

消息m对应于pk

的签名.再签名预言机O

ReSign

返回A再签名

′←ReSign(ReKey(sk

,sk

),m,

),其中,sk

,sk

是对

应于pk

,pk

的密钥.

(2) 伪造

原始签名安全性.攻击者A最后输出(pk

),如果满足下面的条件,就称攻击者在PRS-CMA游戏后成功

地得到伪造的原始签名:

•

是可以用公钥pk

验证的消息m

的有效的原始签名;

• pk

不是密钥预言机O

CKeyGen

的查询;

• (pk

)不是签名预言机O

Sign

的查询.

再签名安全性.攻击者A最后输出(pk

),如果满足下面的条件就称攻击者在PRS-CMA游戏后成功地

得到伪造的再签名:

•

是可以用公钥pk

验证的消息m

有效的再签名;

• pk

不是密钥预言机O

CKeyGen

的查询;

• (pk

)不是签名预言机O

Sign

的查询;

• (◇,pk

)不是再签名密钥预言机O

ReKey

的查询,其中,◇代表任何用户的公钥;

• (◇,pk

,◆)不是再签名预言机O

ReSign

的查询,其中,◆代表任意的签名.

攻击者A在游戏后得到一个伪造的原始签名或者再签名的优势可以定义为Adv

=Pr[A succeeds],这里,概

率的大小完全取决于挑战者和攻击者之间的抛币概率.本文称一个代理重签名方案是选择消息攻击下存在性

不可伪造的,那么对于任意的攻击者A,这个游戏中Adv

都是可以忽略的.

2.2 基于通用可组合安全框架的安全模型

为了描述通用可组合安全性,本文定义了代理重签名基于通用可组合安全框架的安全模型.这个安全模型

的主要任务是定义一个恰当的代理重签名理想功能F

PRS

.Canetti和Hohenberger

[11]

给出了代理重加密的理想功

洪璇等:简单的通用可组合代理重签名方案

2083

能,它与代理重签名类似,一个拥有一些额外信息的半可信代理人可以把用户A的公钥加密的密文转换为用户

B的公钥加密的密文.本文仿照Canetti和Hohenberger的思路,给出代理重签名的理想功能F

PRS

如下:

• 密钥生成接口.接收到用户P的输入(KeyGen,sid)后,验证sid是否等于(P,sid′),F

PRS

把(KeyGen,sid)输入给

攻击者A.F

PRS

并接收到攻击者A的输出(Algorithms,sid,s

)和一个表示“corruption”的比特后(其中s

是一个非确定性多项式时间算法的描述,v

是一个确定性多项式时间算法的描述),记录(P,s

)并输出

(VerificationAlgorithm,sid,v

)给用户P.如果设置了“corrupted”比特,则F

PRS

记录用户P的状态“corrupted”.

• 再签名密钥生成接口.接收到用户P和P′的输入(ReKey,sid,P,P′,X),并验证sid的有效性后,F

PRS

把

(ReKey,sid,P,P′,X)输出给攻击者A.F

PRS

接受到攻击者A的输出(ResignAlgorithm,sid,s

P,P′

)和一个表示

“corruption”的比特,其中,s

P,P′

是一个多项式时间算法的描述.记录(P,P′,X,s

P,P′

),并输出(Proxy,sid,P,P′)给

代理人X.如果设置了“corrupted”比特,则F

PRS

记录代理人X的状态“corrupted”.

• 签名接口.接收到用户S的输入(Sign,sid,m),F

PRS

验证sid的有效性后,计算

(m),并记录(m,

).输出

(Signature,sid,m,

)给用户S.

• 再签名接口.接收到代理人X的输入(ReSign,sid,P,P′,m,

),F

PRS

验证sid的有效性后,判断是否存在记录

(P,P′,X,s

P,P′

):如果不存在,则输出⊥;否则,计算

′=s

P,P′

(m,

),记录(m,

′,v

),并输出(ReSignature,sid,m,

′)给

代理人X.

• 签名验证接口.接收到用户V的输入(Verify,sid,m,

)后,F

PRS

输出(Verified,sid,m,

,f )给用户V.其中,f按

照如下条件计算:

• 如果用户P的状态是“corrupted”,则令f=1(确保被控制的用户能够“注册”任意的原始签名或者再

签名);

• 如果

≠v

,则令f=0(确保当给定验证算法不合法时,所有的验证请求结果都是不合法的.F

PRS

只是记

录签名和验证算法的关联);

• 如果

且存在记录(m,

),则令f=1(确保合法用户合法产生的签名一定可以通过验证请求);

• 如果

但不存在记录(m,

),则令f=0(确保合法用户非法产生的签名(即伪造签名)一定不通过

验证请求).

代理重签名理想功能F

PRS

的基本思路是提供“注册机”的功能.签名者可以注册(消息、原始签名)对,代理人

可以注册(消息、再签名)对,而任何参与者都能检验某个签名是否已经被注册过.上面给出了代理重签名理想功

能F

PRS

的详细描述.它与签名理想功能F

SIG

类似.与F

SIG

不同,F

PRS

允许它的一个实例处理多个用户的密钥和多

个代理人的密钥.F

PRS

与F

SIG

相比还增加了两个模块:再签名密钥生成接口和再签名接口.代理重签名理想功能

PRS

共有5类输入,这些输入又分别对应5个基本模块:密钥生成接口、再签名密钥生成接口、签名接口、再签

名接口和签名验证接口.

验证算

代理重签名理想功能F

PRS

的密钥生成接口和再签名密钥生成接口都是由攻击者A决定签名算法、

法和再签名算法.同时,攻击者A还可以决定被攻破的用户和代理人的身份.但是,攻击者A需要在使用这些接口

之前确定这些被控制的用户和代理人的身份.这就限制了整个模型是静态攻击模型,即在签名接口和再签名接

口使用之前已经建立起所有的签名密钥和再签名密钥.

2.3 两种安全模型的等价性

为了证明代理重签名这两种安全模型之间的等价性,首先需要说明如何把代理再签名方案

转换成相应的

代理再签名协议

.令

=(KeyGen,ReKey,Sign,ReSign,Verify)为代理再签名方案,协议

由下面的步骤得到:

1. 接受到输入(KeyGen,sid)后,用户P调用密钥生成算法计算(pk,sk)←KeyGen(1

).算法s

(⋅)是签名算法

Sign(sk,⋅).算法v

(⋅)是验证算法Verify(pk,⋅).用户P输出(VerificationAlgorithm,sid,v

).如果P从攻击者

A处得到一个“corruption”请求,则把签名算法s

(⋅)输出给攻击者A.

2. 接受到输入(ReKey,sid,P,P′,X)后,代理人X调用再签名密钥生成算法计算rk

a↔b

←ReKey(sk

,sk

).算法

P,P′

(⋅)是再签名算法ReSign(rk

a↔b

).代理人X输出(Proxy,sid,P,P′).如果X从攻击者A处得到一个

2084

Journal of Software 软件学报 Vol.21, No.8, August 2010

“corrupted”请求,则把再签名算法s

P,P′

(⋅)输出给攻击者A.

接收到输入(Sign,sid,m)后,用户S调用签名算法计算

(m),并输出(Signature,sid,m,

接收到输入(ReSign,sid,P,P′,m,

)后,代理人X计算

′=s

P,P′

(m,

),并输出(ReSignature,sid,m,

′).

接收到输入(Verify,sid,m,

)后,验证者V计算f=Verify(pk,m,

),并输出(Verified,sid,m,

,f ).

一个代理重签名方案满足基于游戏的安全模型,等价于相应的代理重签名协议满足基于通用可组合安全

框架的安全模型.

定理2.2. 令

=(KeyGen,ReKey,Sign,ReSign,Verify)是代理重签名方案,则相应的协议

安全地实现了理想功

能F

PRS

,当且仅当方案

满足正确性、一致性、不可伪造性.

证明:首先证明充分性,即需要证明若

安全实现了理想功能F

PRS

,则

是正确的、一致的和不可伪造的.

假设当

不具有正确性、一致性或不可伪造性时,构造环境机Z和实际攻击者A,对于任何理想攻击者S,环境机

Z都能分辨它是与运行A和协议

交互,还是与运行S和理想功能F

PRS

交互.

(1) 假设

不具有正确性,即存在某个消息m,对于公私钥对(pk,sk)和签名

,协议

得到验证结果

Verify(pk,m,

)=0;或者,对于公私钥对(pk

,sk

),(pk

,sk

),再签名密钥rk

a↔b

和用户A的签名

,协议

验证Verify(pk

m,ReSign(rk

a↔b

,m,

))=0.环境机Z首先设sid=(S,0),并用请求(KeyGen,sid)激活S,然后请求对m签名或再签名操

作,最后验证所得原始签名或再签名.因为

不具有正确性,所以当Z与

交互后,Z返回的结果是0.而在理想过程

中,Z的验证结果一定是1.所以,当

不具有正确性时,环境机Z一定可以分辨它是与A和协议

交互,还是与S和

理想功能F

PRS

交互.

(2) 假设

不具有一致性,即两次调用签名验证算法Verify(pk,m,

)得到不同的结果.这样,环境机Z用

(pk,m,

)两次调用V,Z的结果就是判断两次验证结果是否一致.因为

不满足一致性,所以Z的结果是0.而在理

想过程中,Z的结果是1.所以,当

不具有正确性时,Z一定可以分辨它是与

还是F

PRS

交互.

(3) 假设

不具有不可伪造性,即存在

的一个成功的伪造者A.环境机Z首先就激活A,并如下执行:

• 如果A希望查询O

CKeyGen

,则Z调用新的用户并令其是“corrupted”,最后返回给A得到的密钥;

• 如果A希望查询O

ReKey

,则Z调用两个相关的用户,令其把签名权授权给“corrupted”代理人X,最后返回给

A得到的再签名密钥;

• 如果A希望查询O

Sign

,则Z调用相应的用户,用同一个签名请求其签名,最后返回给A得到的签名;

• 如果A希望查询O

ReSign

,则Z调用相应的代理人,用同一个再签名请求再签名,最后返回给A得到的结果;

• 若A最后提供某个原始签名或再签名,则环境机Z的结果是“real”;否则,Z的结果是“ideal”.

分析环境机Z的整个过程,在Z与协议

交互时,Z调用的攻击者A应该得到协议

所需的所有信息.因为A

是

的成功的伪造者,所以A能够以不可忽略的概念

得到伪造的原始签名或再签名.因此,Z就能以同样的概率

输出“real”.而当Z与F

PRS

交互后,Z的输出结果一定是“ideal”.所以,Z可以分辨它是与实际协议

还是与理想功

能F

PRS

交互.

接来下证明充分性,即证明若

是正确的、一致的和不可伪造的,则

安全实现了F

PRS

.假设

不能安全实现

PRS

,即存在环境机Z能够分辨它是与运行D(dummy adversary,完全按照Z的指令运行,只传递消息)和协议

交

互,还是与S和理想功能F

PRS

交互,其中,由攻击者S提供签名算法和验证算法.即使

具有正确性和一致性,也可

以调用Z构造一个成功的针对

的攻击者A.与攻击者A的交互过程如下所述:

• 当Z用输入(KeyGen,sid)激活某个“corrupted”的P,则A查询O

CKeyGen

,将结果(sk,pk)返回给Z

• 当Z用输入(ReKeyGen,sid,P,P′,X)激活两个用户P和P′,则A查询O

ReKey

,将结果rk

P→P′

返回给代理人

X.若代理人X的状态是“corrupted”,则同时返回rk

P→P′

给Z

• 当Z用输入(Sign,sid,m)激活用户S,则A查询O

Sign

并得到

,返回结果(Signature,sid,m,

)给S

• 当Z用输入(ReSign,sid,P,P′,m,

)激活用户S,则A查询O

ReSign

,将得到的再签名

′返回给S

• 当Z用输入(Verify,sid,m,

)激活验证者

,则A令

Verify

(

),输出(

Verified

sid

)给

接下来分析攻击者A成功的概率,即分析环境机Z能够成功地分辨出它是与协议

交互,还是与理想功能

洪璇等:简单的通用可组合代理重签名方案

2085

PRS

交互的概率.因为已经假设方案

是正确的和一致的,所以最后得到(

),用这个签名查询验证请求时结

果是1.而在理想过程下,用这个签名查询验证请求时结果则是0.这样,最后必定得到某个伪造的原始签名或再

签名.因为环境机Z能以某个不可忽略的概率分辨它是与协议

交互,还是与理想功能F

PRS

交互,所以构造的攻

击者A能够以同样的概率

赢得PRS-CMA游戏. □

3 UC安全的代理重签名

3.1 具体方案

本文的双向代理重签名方案是在两个阶为

)的群

和

上执行.公开参数是(

),其中,

和

是群

的两个生成元,

→

是双线性配对,而

(⋅)则是一个安全的哈希算法,能够把任意的字符串

映射到

]

中的元素.下面是方案

BPRS

的详细描述:

• 密钥的生成.输入安全参数1

后,随机选择

a∈

]

,输出用户的一对公私钥

mod

和

• 再签名密钥的生成.输入用户

和

的秘密信息

和

,输出用户

和

之间的再签名密

钥

a↔b

mod

• 签名.输入私钥

和消息

,随机选择

r∈

]

,并计算

mod

(

)⋅

mod

−1,

最后输出原始签名

• 再签名.输入再签名密钥

a↔b

,消息

,用户

的公钥

和用户

的原始签名

).首先检查

是否

是用户

对消息

的签名,即判断等式

Verify

(

)=1是否成立.如果等式不成立,则输出⊥;否则,随

机选取

Δr∈

]

并计算

′=

a↔b

⋅

Δr

′=

Δr

mod

最后输出再签名

′=(

′,

• 验证.输入公钥

、消息

以及签名

,令

(

),然后按照如下条件来判断:

• 如果

是原始签名,即签名的格式是

),则验证

≡

⋅

mod

是否成立.如果等式成立,则输

出1;否则,输出0.

• 如果

是再签名,即签名的格式是

),则验证

(

)⋅

(

)

⋅

(

)是否成立.如果等

式成立,则输出1;否则,输出0.

容易看出,方案

BPRS

具有双向性、多用性和可传递的.而且因为每个用户只需存储他自己的秘密信息,所以

不需要另外的存储空间,方案

BPRS

也是密钥最优化的.方案

BPRS

是在ElGamal族三元签名方案的基础上增加再

签名密钥生成算法和再签名算法变形而得到的.相对于其他方案,

BPRS

更容易应用到现有的体制中.而且方案

BPRS

更为简单、有效.在其签名算法和再签名算法中,用户只需进行群

上的模指数运算和模乘运算.只有当

需要验证再签名时,验证者才需要用到配对运算.与第一个可证明安全的方案

相比(需要用到大量的公开参

数),方案

BPRS

只需要很少的公开参数.

3.2 安全性证明

这一节将证明方案

BPRS

满足正确性、一致性和选择消息攻击下的不可伪造性.而且根据这两个安全模型

之间的等价性(定理2.2),方案

BPRS

满足通用可组合安全性.

定理3.1. 如果计算Diffie-Hellman问题假设在群

中成立,则方案

BPRS

在随机预言机模型下是正确的、

一致的和不可伪造的.

2086

Journal of Software

软件学报 Vol.21, No.8, August 2010

证明:方案的正确性和一致性很容易证明.首先看正确性.对于任何消息

和算法

KeyGen

)产生的公私钥

对(

),如果原始签名

Sign

(

)=(

),其中,

(

)⋅

mod

−1,那么一定有

≡

⋅

H(m||R)

mod

,即

Verify

(

)=1.而对于任何消息空间中的消息

,公私钥(

),(

),再签名密钥

a↔b

,用户

的签名

和

用户

的再签名

′,一定有

(

′,

(

)⋅

(

)

H(m||R)

⋅

(

),即

Verify

(

pkb

ReSign

(

a↔b

))=1.因此,方案

BPRS

满足正确性.

再看一致性.对于任何消息空间中的消息

、公钥

和任何签名

,两次调用

Verify

(

)就是根据是原

始签名还是再签名判断

≡

⋅

H(m||R)

mod

,或

(

)⋅

(

)

H(m||R)

⋅

(

).因为条件不变,所以两次的结果

一定是相同的.因此,方案

BPRS

满足一致性.

接下来看不可伪造性.这个安全属性通过规约来证明.假如存在一个攻击者

能够以一个不可忽略的概率

在时间

内破解方案

BPRS

,而且攻击者

能够查询最多

次签名预言机

Sign

、

次再签名预言机

ReSign

、

次用户密钥预言机

CKeyGen

和

次再签名密钥预言机

ReKey

以及

次哈希查询预言机

Hash

,那么可以构

造一个攻击者

,能够以概率

在时间

′

(3(t

)

⋅

))/

内解决群

上的

CDH

假设问题

希望解决的

CDH

假设是给定输入

(g,g

攻击者B的目的就是求出

攻击者B先建立了给攻击者A的

公开参数

安全参数

≥

|p|

、群

=〈g〉

和群

(

这两个群的阶是

及双线性配对

e:G

×G

→G

令

h=g

系统参数

是

(e,p,G

,g,h,H),

其中

,H(⋅)

是一个随机预言机

(1)

查询

B向A建立了如下的随机预言机

• O

Hash

接受到A查询输入是

(m,R)

时

攻击者B检查

(m,R)

是否存储在哈希的数据库D

中

如果存在这

条记录

则只需要直接回答存储的记录即可

;

如果没有这条记录

则攻击者B随机选取

∈

]

并在数据库

中记录

(m,R,

B把

作为对A的回答

• O

CKeyGen

接收到A查询用户

的密钥查询后

攻击者B随机选取

∈

]

并输出

(pk

,sk

)=(g

• O

ReKey

接收到A查询输入

(pk

,pk

)

后

攻击者B返回再签名密钥

↔

modp

• O

Sign

接收到A查询输入

(pk,m)

后

如果

的状态是

“corrupted”,

那么攻击者B返回直接用签名算法计算

的消息

的签名结果

,R),

并随机选取

r∈

分别计算

R=g

mod p,

=a+H(m||R)⋅r mod p−1;

否则

攻击者B伪造签名

随机选取

u,v,

令

R=g

⋅pk

mod p,

=−u/v mod p−1,

H(m||R)=−1/v mod p−1,

把

=H(m||R)=−1/v

作为哈希查询

(m,R)

的回答记录到哈希数据库D

中

这样

,R)

就与实际方案中的

签名具有相同的形式

是对

的一个有效的原始签名

• O

ReSign

接受到A查询输入

(pk

,pk

,m,

)

后

首先验证

Verify(pk

,m,

)=1,

攻击者B调用

ReSign(O

ReKey

(pk

),pk

,m,

)

计算出再签名

′.

最后输出A的再签名的结果

如果过程中失败

则输出

⊥.

(2)

伪造

如果B在一系列的查询之后也不出错

则A能以一个不可忽略的概率

返回消息

的某个签名

利用分叉引理可以得到本定理的结论

运行

次A

因为A是一个成功的伪造者

所以只要满足这个条件

B就能

以概率

输出消息

的一个有效签名

然后

B在相同条件下再运行另外两次

攻击者A

但是这两次中

B重排

他对A的

个均匀随机哈希查询内容

那么一定得到两个伪造的原始签名

或者两个伪造的再签名

如果是得到两个伪造的原始签名

那么当两个伪造的原始签名

(m,(

,R,e))

和

(m′,(

′,R′,e′))

满足条件

(m,R)=(m′,R′)

时

,“

成功分叉B的

提问

”

这个事件就会发生

由生日悖论

这个事件发生的概率大约是

对于这两个有效的原始签名

B可以计算

=a+e⋅r mod p,

洪璇

等

简单的通用可组合代理重签名方案

2087

′=a+e′⋅r′ mod p.

由

e≠e′,

推出

≠

′,

所以有

′

⋅

−

⋅

′

modp

−

′

−

′

⋅

−

⋅

′

−

根据这个结论可以计算解决

CDH

假设问题

)modp.

如果是得到两个伪造的再签名

则当两个伪造的再签名

(m,(

,R,K,e))

和

(m′,(

′,R′,K′,e′))

满足条件

(m,R,K)=

(m′,R′,K′)

时

,“

成功分叉B的

提问

”

这个事件就会发生

由生日悖论

这个事件发生的概率大约是

1/Q

对于

这两个有效的原始签名

B可以计算

⋅

′

由

e≠e′,

推出

≠

′,

所以有

⎛

′

⎞

⎜

⎟

⎝

′

⎠

′

−

′

⋅

′

因为

h=g

所以可以解决

CDH

假设问题

⎛

′

⎞

⎜

⎟

⎝

′

⎠

′

−

modp.

分析攻击者B如何成功完成整个模拟的过程可知

攻击者B成功的概率是

Pr[

succeeds]=

而攻击

者B所需的时间是

′

3(t

)

⋅

)

□

因此

该定理得证

下面的推论可以直接由定理

2.2

和定理

3.1

推导出

推论3

如果计算

Diffie-Hellman

假设问题在群

上成立

则方案

BPRS

在随机预言机模型下安全地实现

了F

PRS

满足了

安全性

4 结论

本文给出了代理重签名的形式化定义和两个等价的安全模型

一个是基于通用可组合安全框架的安全模

型

另一个是基于游戏的安全模型

这样就保证了如果方案满足基于游戏的安全性定义

那么方案同时还满足通

用可组合安全性

然后

本文还提出了满足

安全的双向代理重签名方案

BPRS

方案

BPRS

被证明是正确的、一

致的、不可伪造的和通用可组合安全的

其安全性可以规约到随机预言机模型下的计算

Diffie-Hellman

假设

本文给出代理重签名基于

框架的安全模型

为以后研究

安全的代理重签名协议铺平了道路

与之前的文

献一样

本文考虑的仍然是静态攻击模型

即攻击者必须在一开始就确定这些被控制的用户和代理人的身份

我

们以后的工作致力于研究代理重签名动态攻击模型下的安全模型

致谢

在此

我们向对本文的工作给予支持和建议的上海交通大学密码与信息安全实验室的各位老师和同学

表示感谢

References

[1] Blaze M, Bleumer G, Strauss M. Divertible protocols and atomic proxy cryptography. In: Proc. of the EUROCRYPT’98. LNCS

1403, Berlin, Heidelberg: Springer-Verlag, 1998. 127−144.

2088

Journal of Software

软件学报

Vol.21, No.8, August 2010

[2] Ateniese G, Hohenberger S. Proxy re-signatures: New definitions, algorithms, and applications. In: Proc. of the ACM CCS 2005.

Berlin, Heidelberg: Springer-Verlag, 2005. 310−319.

[3] Ateniese G, Fu K, Green M, Hohenberger S. Improved proxy re-encryption schemes with applications to secure distributed storage.

In: Proc. of the 12th Annual Network and Distributed System Security Symp. (NDSS 2005). Berlin, Heidelberg: Springer-Verlag,

2005. 29−43.

[4] Taban G, Cárdenas AA, Gligor VD. Towards a secure and interoperable DRM architecture. In: Proc. of the ACM DRM 2006.

Berlin, Heidelberg: Springer-Verlag, 2006. 69−78.

[5] Shao J, Chao ZF, Wang LC, Liang XH. Proxy re-signature schemes without random oracles. In: Proc. of the Indocrypt 2007. LNCS

4859, Berlin, Heidelberg: Springer-Verlag, 2007. 197−209.

[6] Ivan A, Dodis Y. Proxy cryptography revisited. In: Proc. of the 10th Annual Network and Distributed System Security Symp.

(NDSS 2003). Berlin, Heidelberg: Springer-Verlag, 2003. 196−204.

[7] Canetti R. Universally composable security: A new paradigm for cryptographic protocols. In: Proc. of the IEEE Symp. on

Foundations of Computer Science. Berlin, Heidelberg: Springer-Verlag, 2001. 136−145.

[8] Canetti R. Universally composable signature, certification, and authentication. In: Proc. of the 17th Computer Security Foundations

Workshop (CSFW 2004). Berlin, Heidelberg: Springer-Verlag, 2004. 219−233.

[9] Bellare M, Canetti R, Krawczyk H. A modular approach to the design and analysis of authentication and key exchange protocols.

In: Proc. of the 30th Annual ACM Symp. on the Theory of Computing. ACM Press, 1998. 419−428.

[10] Goldwasser S, Micali S, Rivest RL. A digital signature scheme secure against adaptive chosen message attacks. SIAM Journal of

Computing, 1998,17:281−308. [doi: 10.1137/0217017]

[11] Canetti R, Hohenberger S. Chosen-Ciphertext secure proxy re-encryption. In: Proc. of the ACM CCS 2007. ACM Press, 2007.

185−194.

洪璇(1982－),女,江西宜黄人,博士,讲师,

主要研究领域为密码算法与可证明安全,

通用可组合安全框架.

万中美(1973－),女,博士生,讲师,主要研

究领域为信息安全技术.

陈克非(1959－),男,博士,教授,博士生导

师,主要研究领域为密码算法,可证明安全

性,数字水印及应用技术.

简单的通用可组合代理重签名方案

发布评论取消回复

最近发表

相关推荐

标签列表

简单的通用可组合代理重签名方案

发布评论 取消回复

最近发表

相关推荐

标签列表

发布评论取消回复