基于社会承诺机制的理性同时生效签名方案及其公平性＊

任祉静，彭长根，刘 海

(贵州大学 理学院，密码学与数据安全研究所，贵州 贵阳 550025)

同时生效签名，即公平交换电子签名，不需要可信第三方参与，能有效解决公平交换电子签名中的不公平问题，且不需要很强的交互性，主要应用于电子合同签署、电子招标等方面。

2004 年，Chen，Kudla 和Paterson［1］在欧密会上首次提出了同时生效签名方案。在该方案中，发起者掌握一个秘密消息keystone，在keystone 公布之前，任何第三方不能确定该签名由协议双方中的哪一个生成，而一旦公布keystone 后，签名将与签名者的身份绑定，实现了签名同时生效。该方案没有引入可信第三方，不会出现共谋问题，有效的解决了交换的公平性问题;且协议双方不用进行实时的在线交互。其后，Susilo［2］提出了完美同时生效签名，提高了其模糊性。S.Chow［3］提出的基于身份的同时生效签名。Nguyen［4］提出的非对称同时生效签名，比原方案匿名性强。Wang［5］指出完美同时生效签名中有缺陷，并对其进行改进。Huang［6］提出了两个更加高效和安全的基于身份的同时生效签名方案。Yuen［7］提出发起者与响应者分别掌握一个keystone 来解决公平性问题，但该方案存在谁先释放keystone 问题，也就是说不能从根本上解决公平性问题。Susilo［8］再次提出原方案的公平性问题，但依旧没有解决。在这些方案中虽然也有对公平性的研究，但都假设参与者是诚实的或者在某些应用场合会诚实的执行协议，若考虑参与者的自利性，由于发起者掌握一定程度的额外权限，必将导致协议不公平。

社会承诺机制常用在多智能体系统中，以保证智能体行为的逻辑理性和决策理性，Castelfranchi［9］指出社会承诺可对双方进行社会约束，但没有具体实现。Haddadi［10］考虑了具体实现，但没有社会约束。徐晋晖［11］以效用理论为基础建立了社会承诺机制。然而此机制不能防止双方的抵赖行为。

本文基于数字签名提出一种新的社会承诺机制，通过基于数字签名的社会承诺机制实现对双方恶意行为的抑制，且能防止双方抵赖，以此设计了一个无可信第三方的理性公平的电子签名交换协议，即理性公平的同时生效签名协议，首次从理性的角度对同时生效签名方案进行研究，并对该协议的安全性进行分析，得出协议满足正确性、不可伪造性、模糊性，用博弈论［12，13］对协议的公平性进行分析，证明该协议还满足理性公平性、稳定性，解决了同时生效签名中一直没解决的发起方掌握一定程度额外权力的不公平性问题。

1 基础知识

1.1 离散对数问题

1.2 扩展型博弈

1.2.1 扩展式博弈

一个扩展型博弈是一个五元组G=(P，H，F，A，U)，其中:

P={P1，…，Pn}指n 个参与者的集合，Pi表示第i 个参与者。

H 是历史序列集合，其中空字符ε ∈H。h ∈H表示历史序列。

函数F:(H)→P 表示行动组合到下一个参与者的映射，Z 表示所有的末端组成的集合，h ∈H 表示没有末端的行动集合。

A={A1，…，An}是参与者的行动集合，其中Ai={ai1，…，aim}为参与者Pi所有可选择的行动集合，aik表示参与者Pi的第k(1 ≤k ≤m)种行动。在h 之后可能出现的所有行动的组合记为A(h)={a| (h，a)∈H}，如果A(h)=φ，则h 称为末端。

U={u1，…，un}是参与者在不同行动组合下的效用函数集合，ui(a1，a2，…an)表示参与者分别选择行动组合(a1，a2，…an)的第i 个参与者的效用函数。

1.2.2 子博弈及子博弈完美均衡

子博弈:由一个动态博弈第一阶段以外的某阶段开始的后续博弈阶段构成的，有初始信息集和进行博弈所需要的全部信息，能够自成博弈的原博弈的一部分，称为原动态博弈的一个子博弈。即，一个扩展型博弈G=(P，H，F，A，U)的子博弈为

如果h' ∈H |h⇔(h，h')∈H，F |h(h')=f(h，h')，A|h(h')=A(h，h')，ui|h(h')=ui(h，h')。其中，|h表示历史序列h 以后的部分。

子博弈完美均衡:如果在一个完美信息的动态博弈中，A=(A1，…，An)这个策略组合及其子集形成的策略组合，是整个动态博弈及它的所有子博弈的纳什均衡，那么A=(A1，…，An)是该动态博弈的一个子博弈完美纳什均衡。即博弈G 的子博弈完美均衡为A=(A1，…，An)如果:∀Pi∈P，∀h ∈H，满足其中，ai|h为参与者Pi在子博弈G|h中的其他行动，为其他参与者的最优行动。换句话说:A|h是每一个子博弈G|h的一个纳什均衡。

1.3 社会承诺机制

社会承诺机制的优势在于不需要可信第三方，依靠社会约束来实现。所以设计社会承诺机制既要考虑到社会约束，还要考虑建立和解除过程，在现实生活中，合同结构能很好的对其进行描述，所以引入合同结构来描述社会承诺机制。

合同结构C={P，R，D}，其中:

P:对象组为理性参与者P={P1，…，Pn}

R:约束，R(Pi，B，F，A)

B:责任(条件;必须采取行动;效用;期限)

F:禁止(条件;不能采取行动;罚金;期限)

A:允许(条件;行动;期限)

D:期限(期限结束，社会承诺解除)。

2 基于社会承诺机制的理性同时生效签名

考虑参与者的自利性，定义参与者为理性参与者，即参与者最大化自己的收益max ui，基于社会承诺机制对自利行为的约束，设计了基于社会承诺机制的理性同时生效签名。

2.1 一种新的合同结构

合同结构没有参与者的身份信息，容易出现抵赖行为，所以，在合同结构的基础上引入参与者身份信息，并对合同结构进行签名，提出新的描述社会承诺机制的合同结构。

合同结构C={对象组P，约束R，期限D，身份〈IDP〉}SKP，其中SKP为参与者P 的私钥。定理1 新的合同结构具有不可抵赖性。证明 新的合同结构用私钥签名，在敌手不知道私钥的情况下，不能产生对合同结构的签名，参与协议的双方不能伪造对方的签名。也就说，签名只能由自己生成，所以该合同结构对双方具有约束力，且双方不可抵赖。

2.2 基于社会承诺机制的理性同时生效签名的形式化定义

定义1 基于社会承诺机制的理性同时生效签名算法sign={SETUP，COMMIT，ASIGN，AVERIFY，VERIFY}，其中:

SETUP:输入参数l，输出以下描述的概率算法(即每次求解所得结果不同):理性参与者集合P，消息空间M，签名空间S，关键数空间K，关键数映射空间F，映射函数:KGEN:K →F。参与者的公钥集合PK，私钥集合SK，其他系统参数π，参与者效用函数集合U，承诺集合C={对象组P，约束R，期限D，签名的身份〈IDP〉}SKP;

COMMIT:输 入〈SKi，SKj，IDi，IDj〉，输 出C(P(u)，R(u)，D，〈IDP〉)SKP;

ASIGN:是一个概率算法，输入〈PKi，PKj，SKi，h2，m〉，输出对消息m 的模糊签名σ=〈s，h1，h2〉。其中，s ∈S，h1，h2∈F;

AVERIFY:一个算法，输入s=〈σ，PKi，PKj，m〉，输出接收或者拒绝，其中，若σ'=〈s，h2，h1〉，接收〈σ'，PKj，PKi，m〉=接收〈σ，PKi，PKj，m〉，如果拒绝，执行COMMIT;

VERIFY:一个算法，输入〈k，s〉，检查KGEN(k)=h2是否成立，若成立，接收，完成算法。若不成立，执行COMMIT。

2.3 基于社会承诺机制的理性同时生效签名方案

设P1，P2为同时生效签名的两个理性参与者，P1为发起方，即掌握着关键数k，P2为应答者。一个基于承诺机制的理性同时生效签名方案如下:

(1)选取两个大素数p 和q，其长度为l 且q|(p－1)，然后选一个生成元g ∈，且gq≡1 mod p。最后P1选取私钥为SK1∈(1，q)，计算其公钥为PK1=gSK1mod p，P2选取私钥为SK2∈(1，q)，计算其公钥为PK2=gSK2mod p。选择两个hash 函数H1，H2:{0，1}*→Zq，设定消息空间和关键数空间M=K={0，1}*，签名空间和关键数映射空间S=F=Zq;

(2)承诺建立:C={P，R，D，ID}SKP;其中:

其中，t0→t1表示t0到t1时间段;σ1'、σ2'、k' 分别表示不合法的σ1、σ2、k;、分别表示P1、P2按协议执行交换签名后的效用，、分别表示P1、P2按偏离协议后的罚金。

(3)P1随机选取一个消息m1∈M，选取一个关键数k，计算关键数k 的映射值h3=H1(k)。随机选择一个值t ∈Zq，计算

发送其模糊签名σ1=〈s1，h1，h3〉;

(4)P2接收到P1的模糊签名σ1后进行模糊验证，验证等式

如果等式成立，则P2选择一个消息MB进行签名。计算

发送其模糊签名σ2=〈s2，h2，h3〉给P1，否则P2执行C;

(5)P1到P2的签名σ2后进行模糊验证，

本文引入数据仓库集成思想，提出一个基于数据仓库集成的生物病毒序列数据集成系统框架，并在此基础上实现一个面向流感病毒序列数据仓库原型系统FLUDW。该系统通过对远程分散的序列数据的抽取、筛选、优化等手段实现数据的本地化。因此该系统既能促进本地序列数据的高效共享和利用，也可满足国内生物信息研究的需求，为实现对生物序列信息的进一步知识挖掘提供有力的支持。

若等式成立，P1发送关键数k 给P2，否则P1执行C。若P1不发送关键数k，P2执行C。

3 基于社会承诺机制的理性同时生效签名的安全性分析

在同时生效签名协议中，要满足正确性、模糊性、不可伪造性、公平性，本方案除了满足以上性质外，还满足了稳定性。

在本方案中，利用私钥对承诺进行签名，私钥不是公共知识，即只有自己知道，这也是随机预言机模型下选择消息攻击证明的条件，其他参数与文献［1］中相同，所以其安全性依赖于文献［1］的安全性，故其同样满足不可伪造性和模糊性。

3.1 正确性

P1，P2签名算法按正确执行，那么AVERIFY算法和VERIFY 算法返回accept。

若P1的模糊签名σ1=〈s1，h1，h3〉，则

若P1发送k，则h2=H1(k)。

综上所述，基于社会承诺机制的理性同时生效签名协议可正确执行。

3.2 公平性

基于社会承诺机制的理性同时生效签名用扩展式博弈描述如图1 所示。

图1 扩展式博弈

其形式化表述为:

其子博弈G|h1形式化描述为:

其子博弈G|h2形式化描述为:

下面给出理性公平的定义，提出定理并进行证明。

定义2 一个理性协议是一个扩展式博弈，且协议执行完成后每个理性参与者的最终效用都达到了利益最大化，即:)是纳什均衡行动组合，则称协议是理性公平的。

定理2 基于社会承诺机制的理性同时生效签名是理性公平的。即:(σ1，σ2，k)是基于社会承诺机制的理性同时生效签名博弈的纳什均衡行动组合。

证明 在第三阶段，F(h2)=P1，A3={a31，a32，a33}={k，quit，k' }，因为，根据P1会最大化效用，即:max u1，所以，h3|h1，h2=k。

在第二阶段，F(h1)=P2，A2={a21，a22，a23}={σ2，quit，σ2' }，P2分析P1会最大化效用，h3|h1，h2=k，因为u2(a1，σ2，k)=u+2，u2(a1，σ2'，k)=根据P2会最大化效用，即:max u2，所以，h2|h1=σ2。

在第一阶段，F(ε)=P1，A1={a11，a12，a13}={σ1，quit，σ1' }，P1分析P2会最大化效用，h2|h1=σ2，因为u1(σ1，σ2，k)=u+1，u1(σ1'，σ2，k)=0，u1(quit1，σ2，k)=0，＞0，根据P1会最大化效用，即:max u1，所以，h1=σ1。

综上所述，(σ1，σ2，k)是基于社会承诺机制的理性同时生效签名博弈的纳什均衡行动组合。所以基于社会承诺机制的理性同时生效签名是理性公平的。

3.3 稳定性

在扩展式博弈中，纳什均衡保证没有一个理性参与者偏离协议能获得更多的收益，然而，扩展式博弈的参与者轮流执行协议，导致“空威胁”使得协议不稳定。

如:文献［1］的同时生效签名由于u1(σ1，σ2，k)≥u1(a1，σ2，k)，u2(σ1，σ2，k)≥u2(σ1，a2，k)，u1(σ1，σ2，k)≥u1(σ1，σ2，a3)，所以A=(σ1，σ2，k)为纳什均衡。但是，

在第二阶段P2分析P1在第三阶段行动如下:

所以，该协议理性参与者P1、P2不一定会执行协议，导致协议不稳定。

下面给出稳定性的定义，提出定理，并进行证明。

定理3 基于社会承诺机制的理性同时生效签名满足稳定性。即:(σ2，k)是子博弈G|h1的纳什均衡行动组合，k 是子博弈G|h2的纳什均衡行动。

证明 先分析子博弈G|h1，在子博弈G|h1第二阶段，根据P1会最大化效用，即:max u1，所以，在子博弈G|h1第一阶段，F|h1(ε)=P2，A2={a21，a22，a23}={σ2，quit，σ2' }，P2分析P1会最大化效用，，因为u2|h1(σ2，k)，根据P2会最大化效用，即:max u2，所以。

所以，(σ2，k)是子博弈G|h1的纳什均衡行动组合。

综上所述，(σ1，σ2，k)是基于社会承诺机制的理性同时生效签名博弈的子博弈完美均衡行动组合。由3.2 知(σ1，σ2，k)还是基于社会承诺机制的理性同时生效签名博弈的纳什均衡行动组合。所以，基于社会承诺机制的理性同时生效签名满足稳定性。

4 结束语

本文将社会承诺机制进行改进，使得社会承诺机制具有不可抵赖性，并将其引入到同时生效签名中，构建了一个理性同时生效签名协议，协议满足正确性、模糊性、不可伪造性，进而基于博弈论提出理性同时生效签名协议公平性和稳定性的形式化定义，用博弈树分析其纳什均衡和子博弈完美均衡，证明协议满足理性公平性和稳定性，解决了同时生效签名的发起方掌握一定程度的额外权力的问题。然而，本文的通信次数和签名长度相比于文献［1］并没有降低，也就是说，在一般情况下无效率优势，但其较好的公平性和稳定性，使该理性公平的同时生效签名协议更适用于无需可信第三方的比较大额的电子签名交换。

［1］Chen L，Kudla C，Paterson K G.Concurrent signatures［C］//Eurocrypt 2004，Interlaken，Switzerland:Spriger-Verlag，2004:287－305.

［2］Susilo W，Mu Y，Zhang F.Perfect concurrent signatures schemes［C］//ICICS＇04，Malaga，Spain:Spriger-Verlag，2004:14－26.

［3］Chow S S M，Susilo W.Genericconstruction of (identity－based)perfect concurrent signatures［C］// ICICS＇05，Beijing:Springer-Verlag，2005:194－206.

［4］Nguyen K.Asymmetric concurrent signatures［C］//ICICS＇05，Beijing:Springer-Verlag，2005:181－193.

［5］Wang G L，Bao F，Zhou J Y.The fairness of perfect concurrent signatures［C］//ICICS＇06，Raleigh USA:Springer-Verlag，2006:435－451.

［6］Huang Z，Chen K，Lin X，et al.Analysis and improvements of two identity-based perfect concurrent signature schemes［J］.Informatica，2007，18(3):375－394.

［7］Yuen T H，Wong D S，Susilo W，et al.Concurrent signatures with fully negotiable binding control［C］// ProvSec 2011，Xi＇an:Springer-Verlag，2011:170－187.

［8］Susilo W，Au M H，Wang Y，et al.Fairness in concurrent signatures revisited［C］//ACISP 2013，Brisbane，Austrain:Springer-Verlag，2013:318－329.

［9］Castelfranchi C.Commitment:from individual intentions to groups and organizations［C］//ICMAS-95，Cambridge:MIT Press，1995:41－48.

［10］Haddadi A.Communication and cooperation in agent systems:A Pragmatic Theory［M］.Berlin:Springer，1996.

［11］徐晋晖，石纯一.一个基于信念－期望－意图和效用的社会承诺机制［J］.软件学报，1999，10(8):829－834.

［12］田有亮，马建峰，彭长根.秘密共享体制的博弈论分析［J］.电子学报，2011，39(12):32－46.

［13］Roughgarden T，Tardos E，Vazirani V V.Algorithmic game theory［M］.Cambridge:Cambridge University Press，2007:181－207.