标准模型下基于身份的传递签名

马小龙，谷利泽，崔巍，杨义先，胡正名

（1.北京邮电大学 网络与交换技术国家重点实验室信息安全中心，北京100876；2. 北京邮电大学 网络与信息攻防技术教育部重点实验室， 北京100876；3. 北京邮电大学 灾备技术国家工程实验室，北京100876；4. 科学技术部 信息中心，北京 100862）

1 引言

传递签名的概念最早是由Rivest在2000年提出的，2002年，Micali和Rivest在文献[1]中正式提出了传递签名的概念, 主要用于对具有传递性的二元关系进行高效签名。Micali-Revist 传递签名原语是一个原型系统，考虑了签名值被传递的问题，并且抓住了传递签名的最基本语义。签名的传递代表的是二元关系的传递，因而传递签名在与传递信息认证有关的多个领域都有重要应用。

传递签名提出后，许多研究人员对其进行了深入的研究，经过Micali、Rivest、Bellare等密码学家的努力，现在人们已经知道了如何基于大整数分解难题（IFP，integer factoring problem）[2,3]、离散对数难题（DLP，discrete logarithm problem）以及与双线性配对（bilinear pairings）有关的密码学难题假设[4]来实现传递签名。Gregory在他的论文中提出了一个基于RSA的新方案并详细阐述了构成传递签名的各个要素。在此基础上，Shahandashti于2005年提出了基于双线性配对的传递签名并给出了方案的安全性证明，同年黄振杰[5]和Kuwakado[6～9]等人在现有的方案的基础上同时提出了有向传递签名，此后王励成[10]在辫子群下实现了一个新的传递签名方案。现有的传递签名方案主要基于数字证书，并没有提出有效的基于身份的数字签名方案，本文使用双线性配对并结合传递签名的特点设计了第一个基于身份的传递签名，并给出了基于标准模型下的证明。

第2节简要描述所需的背景知识，在第3节介绍传递签名方案，第4节给出签名方案的证明，最后是结束语。

2 预备知识

本文需要的基础知识主要包括：图的传递闭包，双线性配对的基础知识和复杂性假设。

2.1 图的传递闭包

定义1 图G=(V, E)的传递闭包G*=(V*,E*)满足以下条件：V*=V且边(i, j)∈E*当且仅当中有一条从i至j的通路。图G=(V, E)的传递简约G′=(V′, E′)是和G有相同的传递闭包的图中边数最少的图，图的传递简约可以根据文献[11]有效求得。

2.2 双线性配对

定义2 令G1和G2分别为阶为q的加法群和乘法群并且P∈G1，P为G1的生成元。一个双线性映射e: G1×G1→G2具有以下性质。

1) 双线性: 对于任意的(P, Q)∈G1×G1和a, b∈Zp满足e( aP, bQ)=e( P, Q)ab。

2) 非退化性：存在(P, Q)∈G1×G1使得e( P, Q)≠I，其中I为G2中单位元。

3) 可计算性：存在有效的多项式时间算法计算e( P, Q)，其中P、Q∈G1。

其中e为椭圆曲线上Weil或者Tate配对[12]，该配对被用于建立一个双线性映射。

2.3 复杂性假设

本文方案的安全性被归约到CDH[13]问题上，即在群G中计算Diffie-Hellman问题是困难的，将CDH问题定义如下。

定义3 给定一个群G其次数为p生成元为P，任选a、b∈RZp并且aP、bP∈G，则给定aP、bP∈G计算abP在概率多项式时间是困难的。

定义4 假定在群G中CDH问题对于任意有效算法以时间t和概率ε保证其不被攻破。

3 基于身份的传递签名方案

根据Paterson和Waters[14]的思想，本文提出一个新的传递签名方案。该方案包括系统参数生成、私钥生成、签名、验证、边签名、边验证、传递组合几个步骤, 并且签名生成方可以通过使用签署消息的随机数rm∈R来构造身份选项。此外，若消息空间的无限制可将消息M串联时间戳γ2使消息M′=M‖γ2，所以攻击者就不能简单的通过重放攻击对签名进行伪造。下面考虑该签名的基本构造，由以下的多项式时间算法组成。

系统参数 给定参数k, PKG选择线性映射群(G1, G2)，并且(G1,+)和(G2,·)的次数均为p(p＞2k )构造线性配对e: G1×G1→G2，其中P是G1中的生成元。PKG随机选择α∈RZp, 计算P1=αP并任选择bP=P2∈G1。PKG从G1中选择元素u′和m′，并生成长度分别为nu和nm的2个向量U=(ui)、M=(mi)，其中u1, u2,…,unu和m1, m2,…,mnm均为G1中的元素。公开参数为Pparam=(G1, G2, P, P1, P2,U,M,u′, m′)，PKG的私钥是αP2。在这里假设消息的长度和身份的长度分别为nm和nu。

私钥 令uI为长度为nu的比特字符串并作为图G=(V, E)节点I的身份，其中ui为uI的第i bit，并定义U⊂{1,…,nu}当且仅当u[ i]=1。为构建用户私钥PKG随机选择ru∈Zq，计算ruP的散列值hu=H( ruP)=H( S2)，并生成节点I的私钥：

签名 当签名人对消息M=(m1, m2,…,mnm)进行签名时，随机选择rm∈Zq并计算：S1=sku+rm，S2=ruP，S3=rmP。其中，σ=(S1, S2,S3)是对消息M的签名。

边签名 给定传递边(i, j)∈E，通过下式计算传递边签名。

边验证 如果等式边签名ijσ当执行下式正确时，边签名验证成功。

传递组合 若有向图G=(V, E)中存在(i, j, k,σij,σjk)可计算传递签名为σik=σij-σjk。这里，假定i＜j＜k。正确性: 计算SK=SI-σik。可知，与标准签名生成的结果相同并确定其正确性。

4 安全性证明

在基于RSA的方案中Micali和Rivest提出了基本的传递签名方案，Bellare在该方案的基础上给出了一个的简要证明。此后Gregory将上述方案进行汇总，提出了一个详尽的随机预言模型的证明方法。Shahandashti虽提出了一个双线性配对的传递签名方案，但该方案是基于证书的，同时也给出了相应的证明。本文以Paterson和Waters的安全性为基础，通过采用标准模型的证明方法对传递签名的基本签名方案和可传递性进行证明。

定理1 Paterson的方案以(ε′,t′, qe′, qs′ )不可伪造，那么上述基于身份的传递签名方案以(t, qe, qs, qts)归约为Paterson的方案并保证其不可伪造性，qe, qs, qts分别表示进行提取查询、边签名查询和传递边组合查询的次数。其中

证明 假定存在(t, qe, qs, qts)的敌手A，能够构造出概率多项式时间的子查询算法B以不超过ε′′的概率来伪造一个Paterson的签名。

算法B被给定Paterson签名的系统参数Pparam=(G1, G2, P, P1, P2, U′, M′, u′, m′)，其中U′和M′是长度分别为nu和nm的2个向量U′=(ui)、M′=(mi)，其中u′, u1, u2,…,unu和m′, m1, m2,…,mnm均为G1中的元素。

私钥提取查询：当攻击者A询问身份Ii（1≤i≤qe）的私钥时，算法B询问自己的私钥提取预言机，并将返回的身份Ii的私钥发送给攻击者A。

边签名查询：当攻击者A询问传递边(i, j)∈E的边签名时，算法B向自己的标准签名查询进行询问，得到对消息MI和MJ的签名SI=(SI1,SI2,SI3)和SJ=(SJ1,SJ2,SJ3)，然后算法B计算边签名：σij=SI1-SJ1

传递边组合查询：攻击者A对基于身份I和边签名σij,σjk进行传递边组合查询。算法B向自己的边签名查询进行询问，得到边签名σij、σjk，并计算σik=σij-σjk，算法B把得到的签名σik作为传递边的组合返回给攻击者A。

算法B的时间分析如下：B的运行时间等于攻击者A的伪造时间加上回答qe次提取查询的时间，qs次边签名查询的时间，qts次传递组合查询的时间。提取查询和可验证加密签名查询的时间复杂度为O(1)，仲裁查询的时间复杂度为O( nu+nm)，由此可得：t′=t+O( qe+qs+(nu+nm)qts)。

定理2 如果攻击者在时间t内，进行qe次提取查询，qs次边签名查询，qts次传递组合查询，并且成功攻破传递性的概率至少是ε，那么就能够以(ε′,t′)攻破CDH问题。其中，

ρ为群加法运算所需要的时间，τ为群标量乘运算所需要的时间。

证明 假设存在(ε,t, qe, qs, qts)攻击者A，使用攻击者A构造一个概率多项式时间算法B，他能以至少ε′的概率和最多t′的时间来解决CDH问题。

将群G1和生成元P及aP, bP发送给算法B，为了能够使用攻击者A去计算CDH难题abP，算法B要向攻击者A模拟一个挑战者，算法B的模拟如下。

系统参数生成 对于给定的qe,qs,qts,nu和nm，算法B令lu=2(qe+qs+qts)， lm=2(qs+qts)，随机选择整数ku和km，且0≤ku≤nu，0≤km≤nm，算法B假设lu( nu+1)＜p，lm(nm+1)＜p。B选择整数x′∈RZlu和长度为nu的向量X=(xi)，其中xi∈RZlu(i=1,…,nu)。同理，随机选择z′∈RZlm和长度为nm的向量Z=(zj)，其中zj∈RZlu(j=1,…,nm)。算法B同样选择整数y′, w′∈Zp和2个长度分别为nu和nm的向量Y=(yi)，W=(wj)，其中，yi, wj∈RZp，i=1,…,nu，j=1,…,nm。

为分析简便，定义如下两组函数分别用来表示身份u和消息m：

下面，算法B通过计算以下等式构造出签名方案所需的系统参数：

通过这种指派，可以看出PKG的私钥为aP2=abP，并且对于所有的身份u和消息m有以下等式成立：

将所有的系统参数发送给攻击者A。

密钥提取查询 考虑对身份u进行私钥查询，B现在并不知道PKG的私钥，但可假设F( u)≠0mod p并通过任选ru∈RZp可以构造以下私钥：

由以上过程可以看出，对于攻击者A来说，由算法B伪造的私钥与PKG产生的私钥是不可区分的。此外，如果F( u)=0mod p，算法B的计算会被迫中断。为了方便分析，在遇到F( u)=0modlu的情况时，算法B的计算就会终止。由于假设了lu( nu+1)＜p，所以能得到0≤luku≤p ，这2个公式，所以若F( u)=0modp成立就一定存在F( u)=0modlu；若F( u)≠0modlu则能导出F( u)≠0modp。因此，算法B对身份u的私钥进行伪造在以上条件下是充分的。

传递边签名查询 给定身份uI，uJ和消息mI，mJ可查询一个可验证加密签名。

伪造 若B在上述查询中都正确执行，A根据给定的假设条件以至少ε的概率返回一个伪造的身份和消息⌒，并返回一个伪造的可验证加密边签名。由于签名方案中加入了S2的散列，可能导致伪造过程出现2种可能的结果。一种结果是B伪造出与原先设定的身份一致的伪造结果，另一种是伪造出与方案不一致的身份但改身份与原始签名中部分相等。下面分别讨论这2种情况。

1) 输出与原始签名身份uJ一致的伪造签名。存在当子查询B计算：

根据上述构造解决了CDH困难问题，其身份部分分离的结果能够与伪造的任意顶点结合，生成新的伪造边签名σik′。

2) 输出与原始签名节点uJ不一致的伪造签名，但部分计算结果相同。计算：

证明分析：若A可以生成一个伪造传递边签名，子查询B在不改变边签名取值的情况下，通过变换构造一个新的Paterson签名方案，并计算出传递边签名，解决了CDH困难问题。

复杂度分析：通过上述的构造，可以计算出子查询B不被中断并退出构造的概率。分析B不被中断的概率为：

在构造过程中，如果使得模拟完成并且在中间过程不发生终止，需要满足以下3个条件：

① 对身份u的密钥提取查询都有F( u)=0modlu；

② 对于所有攻击者A进行边签名查询的身份和消息对(uI, mI)和(uJ,mJ)，等式F( u)≠0modlu与K( m)≠0modlm至少要有一个成立；

③ 对于攻击者A所产生有效签名的身份和消息对(u*, m*)，等式F( u*)=0modlu成立，并且等式K( m*)=0modlm也成立。

将上述分析表示成概率公式为

可以看出函数F与K是互不相容事件，所以可以将上式分开进行计算。根据以上的假设条件，当lu( nu+1)＜p由F( uI)=0modp⇒F( uI)=0mod lu。计算概率：

还可以得到下式：

由于身份u1, u2代入F中是不同的2个函数值，其结果也不相同。所以条件概率中任意必然是互不相容的。在这里认为事件 A 和i事件对于任何身份都是独立的，并且有，因此可以进行如下计算：

在证明开始时，设置 lu= 2 (qe+ qs+ qts)，因此有：

这样

在B能够正常进行查询的情况下，敌手A以至少ε的概率对该协议进行伪造，其子查询B能够计算出CDH问题。通过上述分析在给定敌手A的时间复杂度为t的情况下，子查询B的时间复杂度为：

通过以上分析，定理证明完毕。

5 结束语

传递签名是近年来提出的用于对传递二元关系进行签名的签名方案，已有的为数不多的传递签名方案都缺乏可证安全或仅在随机预言模型中是可证安全的。本文根据 CDH问题构造了一个基于身份的传递签名方案，并在标准模型下对其安全性进行了证明。这种基于身份的二元关系认证具有重要的现实意义，它可以将传统的单点认证扩展到对2个认证主体之间某种“关系”进行认证。如果将这种“关系”进行形式化即可以组成一个可传递的关系网络，其中信任管理网络就是一种重要的应用。但本文提出的方案适用于无向网络，而实际应用中“关系”有可能是矢量，因此还需要将方案向有向传递签名进行扩展。

[1] MICAILI S, RIVEST R L. Transitive signaure schemes[A]. CT-RSA 2002(LNCS 2271)[C]. Springer-Verlag, 2002. 236-243.

[2] BELLARE M, NEVEN G. Transitive signatures based on factoring and RSA[A]. ASIACRYPT 2002(LNCS 2501)[C]. Springer-Verlag,2002. 397-414.

[3] BELLARE M, NEVEN G. Transitive signatures: new schemes and proofs [J]. IEEE Transactions on Information Theory, 2005, 51(6):2133-2151.

[4] SHAHANDASHTI S F, SALMASIZADEH M, MOHAJERI J. A provably secure short transitive signature scheme from bilinear group Pairs[A]. SCN 2004(LNCS 3352)[C]. Springer-Verlag, 2005.60-76.

[5] 黄振杰, 郝艳华, 王育民等. 一个高效的有向传递签名方案[J]. 电子学报, 2005,33(8):1497-1501.HUANG Z J, HAO Y H, WANG Y M, et al. Efficient directed transitive signature scheme[J]. Acta Electronica Sinica2005, 33(8):1497-1501.

[6] KUWAKADO H, TANAKA H. Transitive signature scheme for directed trees[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2003,E86-A(5): 1120- 1126.

[7] YI X, TAN C H, OKAMOTO E. Security of Kuwakado-Tanaka transitive signature scheme for directed trees[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,2004, E87-A(4): 955-957.

[8] YI X. Directed transitive signature scheme[A]. CT-RSA 2007(LNCS 4377)[C]. Springer-Verlag, 2007. 129–144.

[9] MA C, WU P, GU G. A new method for the design of stateless transitive signature schemes[A]. APWeb 2006(LNCS 3842)[C]. Springer-Verlag, 2006. 897-904.

[10] WANG L C, CAO Z F, ZHENG S H, et al. Transitive signature from braid groups[A]. IndoCrypt 2007(LNCS 4859)[C]. Springer-Verlag,2007. 183-196.

[11] AHO A V, GAREY M R, ULLMAN J. The transitive reduction of adirected graph[J]. SIAM Journal of Computing , 1972, 1(2): 131-137.

[12] BONEH D, LYNN B, SHACHAM H. Short signature from the Weil pairing[J]. Journal of Cryptology, 2004, 17(4): 297-319.

[13] HERRANZ J, LAGUILLAUMIE F. Blind ring signatures secure under the chosen-target-CDH assumption[A]. ISC 2006(LNCS 4176)[C].Springer-Verlag, 2006. 117-130.

[14] LU S, OSTROVSKY R, SAHAI A, et al. Sequential aggregate signturesand multisignatures without random oracles[A]. Eurocrypt 2006(LNCS 4004)[C], Springer-Verlag, 2006. 465-485.