任祉靜，彭長(zhǎng)根，劉 海

(貴州大學(xué) 理學(xué)院，密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽(yáng) 550025)

同時(shí)生效簽名，即公平交換電子簽名，不需要可信第三方參與，能有效解決公平交換電子簽名中的不公平問(wèn)題，且不需要很強(qiáng)的交互性，主要應(yīng)用于電子合同簽署、電子招標(biāo)等方面。

2004 年，Chen，Kudla 和Paterson［1］在歐密會(huì)上首次提出了同時(shí)生效簽名方案。在該方案中，發(fā)起者掌握一個(gè)秘密消息keystone，在keystone 公布之前，任何第三方不能確定該簽名由協(xié)議雙方中的哪一個(gè)生成，而一旦公布keystone 后，簽名將與簽名者的身份綁定，實(shí)現(xiàn)了簽名同時(shí)生效。該方案沒(méi)有引入可信第三方，不會(huì)出現(xiàn)共謀問(wèn)題，有效的解決了交換的公平性問(wèn)題;且協(xié)議雙方不用進(jìn)行實(shí)時(shí)的在線交互。其后，Susilo［2］提出了完美同時(shí)生效簽名，提高了其模糊性。S.Chow［3］提出的基于身份的同時(shí)生效簽名。Nguyen［4］提出的非對(duì)稱同時(shí)生效簽名，比原方案匿名性強(qiáng)。Wang［5］指出完美同時(shí)生效簽名中有缺陷，并對(duì)其進(jìn)行改進(jìn)。Huang［6］提出了兩個(gè)更加高效和安全的基于身份的同時(shí)生效簽名方案。Yuen［7］提出發(fā)起者與響應(yīng)者分別掌握一個(gè)keystone 來(lái)解決公平性問(wèn)題，但該方案存在誰(shuí)先釋放keystone 問(wèn)題，也就是說(shuō)不能從根本上解決公平性問(wèn)題。Susilo［8］再次提出原方案的公平性問(wèn)題，但依舊沒(méi)有解決。在這些方案中雖然也有對(duì)公平性的研究，但都假設(shè)參與者是誠(chéng)實(shí)的或者在某些應(yīng)用場(chǎng)合會(huì)誠(chéng)實(shí)的執(zhí)行協(xié)議，若考慮參與者的自利性，由于發(fā)起者掌握一定程度的額外權(quán)限，必將導(dǎo)致協(xié)議不公平。

社會(huì)承諾機(jī)制常用在多智能體系統(tǒng)中，以保證智能體行為的邏輯理性和決策理性，Castelfranchi［9］指出社會(huì)承諾可對(duì)雙方進(jìn)行社會(huì)約束，但沒(méi)有具體實(shí)現(xiàn)。Haddadi［10］考慮了具體實(shí)現(xiàn)，但沒(méi)有社會(huì)約束。徐晉暉［11］以效用理論為基礎(chǔ)建立了社會(huì)承諾機(jī)制。然而此機(jī)制不能防止雙方的抵賴行為。

本文基于數(shù)字簽名提出一種新的社會(huì)承諾機(jī)制，通過(guò)基于數(shù)字簽名的社會(huì)承諾機(jī)制實(shí)現(xiàn)對(duì)雙方惡意行為的抑制，且能防止雙方抵賴，以此設(shè)計(jì)了一個(gè)無(wú)可信第三方的理性公平的電子簽名交換協(xié)議，即理性公平的同時(shí)生效簽名協(xié)議，首次從理性的角度對(duì)同時(shí)生效簽名方案進(jìn)行研究，并對(duì)該協(xié)議的安全性進(jìn)行分析，得出協(xié)議滿足正確性、不可偽造性、模糊性，用博弈論［12，13］對(duì)協(xié)議的公平性進(jìn)行分析，證明該協(xié)議還滿足理性公平性、穩(wěn)定性，解決了同時(shí)生效簽名中一直沒(méi)解決的發(fā)起方掌握一定程度額外權(quán)力的不公平性問(wèn)題。

1 基礎(chǔ)知識(shí)

1.1 離散對(duì)數(shù)問(wèn)題

1.2 擴(kuò)展型博弈

1.2.1 擴(kuò)展式博弈

一個(gè)擴(kuò)展型博弈是一個(gè)五元組G=(P，H，F(xiàn)，A，U)，其中:

P={P1，…，Pn}指n 個(gè)參與者的集合，Pi表示第i 個(gè)參與者。

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

函數(shù)F:(H)→P 表示行動(dòng)組合到下一個(gè)參與者的映射，Z 表示所有的末端組成的集合，h ∈H 表示沒(méi)有末端的行動(dòng)集合。

A={A1，…，An}是參與者的行動(dòng)集合，其中Ai={ai1，…，aim}為參與者Pi所有可選擇的行動(dòng)集合，aik表示參與者Pi的第k(1 ≤k ≤m)種行動(dòng)。在h 之后可能出現(xiàn)的所有行動(dòng)的組合記為A(h)={a| (h，a)∈H}，如果A(h)=φ，則h 稱為末端。

U={u1，…，un}是參與者在不同行動(dòng)組合下的效用函數(shù)集合，ui(a1，a2，…an)表示參與者分別選擇行動(dòng)組合(a1，a2，…an)的第i 個(gè)參與者的效用函數(shù)。

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

子博弈:由一個(gè)動(dòng)態(tài)博弈第一階段以外的某階段開(kāi)始的后續(xù)博弈階段構(gòu)成的，有初始信息集和進(jìn)行博弈所需要的全部信息，能夠自成博弈的原博弈的一部分，稱為原動(dòng)態(tài)博弈的一個(gè)子博弈。即，一個(gè)擴(kuò)展型博弈G=(P，H，F(xiàn)，A，U)的子博弈為

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

子博弈完美均衡:如果在一個(gè)完美信息的動(dòng)態(tài)博弈中，A=(A1，…，An)這個(gè)策略組合及其子集形成的策略組合，是整個(gè)動(dòng)態(tài)博弈及它的所有子博弈的納什均衡，那么A=(A1，…，An)是該動(dòng)態(tài)博弈的一個(gè)子博弈完美納什均衡。即博弈G 的子博弈完美均衡為A=(A1，…，An)如果:?Pi∈P，?h ∈H，滿足其中，ai|h為參與者Pi在子博弈G|h中的其他行動(dòng)，為其他參與者的最優(yōu)行動(dòng)。換句話說(shuō):A|h是每一個(gè)子博弈G|h的一個(gè)納什均衡。

1.3 社會(huì)承諾機(jī)制

社會(huì)承諾機(jī)制的優(yōu)勢(shì)在于不需要可信第三方，依靠社會(huì)約束來(lái)實(shí)現(xiàn)。所以設(shè)計(jì)社會(huì)承諾機(jī)制既要考慮到社會(huì)約束，還要考慮建立和解除過(guò)程，在現(xiàn)實(shí)生活中，合同結(jié)構(gòu)能很好的對(duì)其進(jìn)行描述，所以引入合同結(jié)構(gòu)來(lái)描述社會(huì)承諾機(jī)制。

合同結(jié)構(gòu)C={P，R，D}，其中:

P:對(duì)象組為理性參與者P={P1，…，Pn}

R:約束，R(Pi，B，F(xiàn)，A)

B:責(zé)任(條件;必須采取行動(dòng);效用;期限)

F:禁止(條件;不能采取行動(dòng);罰金;期限)

A:允許(條件;行動(dòng);期限)

D:期限(期限結(jié)束，社會(huì)承諾解除)。

2 基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名

考慮參與者的自利性，定義參與者為理性參與者，即參與者最大化自己的收益max ui，基于社會(huì)承諾機(jī)制對(duì)自利行為的約束，設(shè)計(jì)了基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名。

2.1 一種新的合同結(jié)構(gòu)

合同結(jié)構(gòu)沒(méi)有參與者的身份信息，容易出現(xiàn)抵賴行為，所以，在合同結(jié)構(gòu)的基礎(chǔ)上引入?yún)⑴c者身份信息，并對(duì)合同結(jié)構(gòu)進(jìn)行簽名，提出新的描述社會(huì)承諾機(jī)制的合同結(jié)構(gòu)。

合同結(jié)構(gòu)C={對(duì)象組P，約束R，期限D(zhuǎn)，身份〈IDP〉}SKP，其中SKP為參與者P 的私鑰。定理1 新的合同結(jié)構(gòu)具有不可抵賴性。證明 新的合同結(jié)構(gòu)用私鑰簽名，在敵手不知道私鑰的情況下，不能產(chǎn)生對(duì)合同結(jié)構(gòu)的簽名，參與協(xié)議的雙方不能偽造對(duì)方的簽名。也就說(shuō)，簽名只能由自己生成，所以該合同結(jié)構(gòu)對(duì)雙方具有約束力，且雙方不可抵賴。

2.2 基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名的形式化定義

定義1 基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名算法sign={SETUP，COMMIT，ASIGN，AVERIFY，VERIFY}，其中:

SETUP:輸入?yún)?shù)l，輸出以下描述的概率算法(即每次求解所得結(jié)果不同):理性參與者集合P，消息空間M，簽名空間S，關(guān)鍵數(shù)空間K，關(guān)鍵數(shù)映射空間F，映射函數(shù):KGEN:K →F。參與者的公鑰集合PK，私鑰集合SK，其他系統(tǒng)參數(shù)π，參與者效用函數(shù)集合U，承諾集合C={對(duì)象組P，約束R，期限D(zhuǎn)，簽名的身份〈IDP〉}SKP;

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

ASIGN:是一個(gè)概率算法，輸入〈PKi，PKj，SKi，h2，m〉，輸出對(duì)消息m 的模糊簽名σ=〈s，h1，h2〉。其中，s ∈S，h1，h2∈F;

AVERIFY:一個(gè)算法，輸入s=〈σ，PKi，PKj，m〉，輸出接收或者拒絕，其中，若σ'=〈s，h2，h1〉，接收〈σ'，PKj，PKi，m〉=接收〈σ，PKi，PKj，m〉，如果拒絕，執(zhí)行COMMIT;

VERIFY:一個(gè)算法，輸入〈k，s〉，檢查KGEN(k)=h2是否成立，若成立，接收，完成算法。若不成立，執(zhí)行COMMIT。

2.3 基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名方案

設(shè)P1，P2為同時(shí)生效簽名的兩個(gè)理性參與者，P1為發(fā)起方，即掌握著關(guān)鍵數(shù)k，P2為應(yīng)答者。一個(gè)基于承諾機(jī)制的理性同時(shí)生效簽名方案如下:

(1)選取兩個(gè)大素?cái)?shù)p 和q，其長(zhǎng)度為l 且q|(p－1)，然后選一個(gè)生成元g ∈，且gq≡1 mod p。最后P1選取私鑰為SK1∈(1，q)，計(jì)算其公鑰為PK1=gSK1mod p，P2選取私鑰為SK2∈(1，q)，計(jì)算其公鑰為PK2=gSK2mod p。選擇兩個(gè)hash 函數(shù)H1，H2:{0，1}*→Zq，設(shè)定消息空間和關(guān)鍵數(shù)空間M=K={0，1}*，簽名空間和關(guān)鍵數(shù)映射空間S=F=Zq;

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

其中，t0→t1表示t0到t1時(shí)間段;σ1'、σ2'、k' 分別表示不合法的σ1、σ2、k;、分別表示P1、P2按協(xié)議執(zhí)行交換簽名后的效用，、分別表示P1、P2按偏離協(xié)議后的罰金。

(3)P1隨機(jī)選取一個(gè)消息m1∈M，選取一個(gè)關(guān)鍵數(shù)k，計(jì)算關(guān)鍵數(shù)k 的映射值h3=H1(k)。隨機(jī)選擇一個(gè)值t ∈Zq，計(jì)算

發(fā)送其模糊簽名σ1=〈s1，h1，h3〉;

(4)P2接收到P1的模糊簽名σ1后進(jìn)行模糊驗(yàn)證，驗(yàn)證等式

如果等式成立，則P2選擇一個(gè)消息MB進(jìn)行簽名。計(jì)算

發(fā)送其模糊簽名σ2=〈s2，h2，h3〉給P1，否則P2執(zhí)行C;

(5)P1到P2的簽名σ2后進(jìn)行模糊驗(yàn)證，

本文引入數(shù)據(jù)倉(cāng)庫(kù)集成思想，提出一個(gè)基于數(shù)據(jù)倉(cāng)庫(kù)集成的生物病毒序列數(shù)據(jù)集成系統(tǒng)框架，并在此基礎(chǔ)上實(shí)現(xiàn)一個(gè)面向流感病毒序列數(shù)據(jù)倉(cāng)庫(kù)原型系統(tǒng)FLUDW。該系統(tǒng)通過(guò)對(duì)遠(yuǎn)程分散的序列數(shù)據(jù)的抽取、篩選、優(yōu)化等手段實(shí)現(xiàn)數(shù)據(jù)的本地化。因此該系統(tǒng)既能促進(jìn)本地序列數(shù)據(jù)的高效共享和利用，也可滿足國(guó)內(nèi)生物信息研究的需求，為實(shí)現(xiàn)對(duì)生物序列信息的進(jìn)一步知識(shí)挖掘提供有力的支持。

若等式成立，P1發(fā)送關(guān)鍵數(shù)k 給P2，否則P1執(zhí)行C。若P1不發(fā)送關(guān)鍵數(shù)k，P2執(zhí)行C。

3 基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名的安全性分析

在同時(shí)生效簽名協(xié)議中，要滿足正確性、模糊性、不可偽造性、公平性，本方案除了滿足以上性質(zhì)外，還滿足了穩(wěn)定性。

在本方案中，利用私鑰對(duì)承諾進(jìn)行簽名，私鑰不是公共知識(shí)，即只有自己知道，這也是隨機(jī)預(yù)言機(jī)模型下選擇消息攻擊證明的條件，其他參數(shù)與文獻(xiàn)［1］中相同，所以其安全性依賴于文獻(xiàn)［1］的安全性，故其同樣滿足不可偽造性和模糊性。

3.1 正確性

P1，P2簽名算法按正確執(zhí)行，那么AVERIFY算法和VERIFY 算法返回accept。

若P1的模糊簽名σ1=〈s1，h1，h3〉，則

若P1發(fā)送k，則h2=H1(k)。

綜上所述，基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名協(xié)議可正確執(zhí)行。

3.2 公平性

基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名用擴(kuò)展式博弈描述如圖1 所示。

圖1 擴(kuò)展式博弈

其形式化表述為:

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

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

下面給出理性公平的定義，提出定理并進(jìn)行證明。

定義2 一個(gè)理性協(xié)議是一個(gè)擴(kuò)展式博弈，且協(xié)議執(zhí)行完成后每個(gè)理性參與者的最終效用都達(dá)到了利益最大化，即:)是納什均衡行動(dòng)組合，則稱協(xié)議是理性公平的。

定理2 基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名是理性公平的。即:(σ1，σ2，k)是基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名博弈的納什均衡行動(dòng)組合。

證明 在第三階段，F(xiàn)(h2)=P1，A3={a31，a32，a33}={k，quit，k' }，因?yàn)椋鶕?jù)P1會(huì)最大化效用，即:max u1，所以，h3|h1，h2=k。

在第二階段，F(xiàn)(h1)=P2，A2={a21，a22，a23}={σ2，quit，σ2' }，P2分析P1會(huì)最大化效用，h3|h1，h2=k，因?yàn)閡2(a1，σ2，k)=u+2，u2(a1，σ2'，k)=根據(jù)P2會(huì)最大化效用，即:max u2，所以，h2|h1=σ2。

在第一階段，F(xiàn)(ε)=P1，A1={a11，a12，a13}={σ1，quit，σ1' }，P1分析P2會(huì)最大化效用，h2|h1=σ2，因?yàn)閡1(σ1，σ2，k)=u+1，u1(σ1'，σ2，k)=0，u1(quit1，σ2，k)=0，＞0，根據(jù)P1會(huì)最大化效用，即:max u1，所以，h1=σ1。

綜上所述，(σ1，σ2，k)是基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名博弈的納什均衡行動(dòng)組合。所以基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名是理性公平的。

3.3 穩(wěn)定性

在擴(kuò)展式博弈中，納什均衡保證沒(méi)有一個(gè)理性參與者偏離協(xié)議能獲得更多的收益，然而，擴(kuò)展式博弈的參與者輪流執(zhí)行協(xié)議，導(dǎo)致“空威脅”使得協(xié)議不穩(wěn)定。

如:文獻(xiàn)［1］的同時(shí)生效簽名由于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在第三階段行動(dòng)如下:

所以，該協(xié)議理性參與者P1、P2不一定會(huì)執(zhí)行協(xié)議，導(dǎo)致協(xié)議不穩(wěn)定。

下面給出穩(wěn)定性的定義，提出定理，并進(jìn)行證明。

定理3 基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名滿足穩(wěn)定性。即:(σ2，k)是子博弈G|h1的納什均衡行動(dòng)組合，k 是子博弈G|h2的納什均衡行動(dòng)。

證明 先分析子博弈G|h1，在子博弈G|h1第二階段，根據(jù)P1會(huì)最大化效用，即:max u1，所以，在子博弈G|h1第一階段，F(xiàn)|h1(ε)=P2，A2={a21，a22，a23}={σ2，quit，σ2' }，P2分析P1會(huì)最大化效用，，因?yàn)閡2|h1(σ2，k)，根據(jù)P2會(huì)最大化效用，即:max u2，所以。

所以，(σ2，k)是子博弈G|h1的納什均衡行動(dòng)組合。

綜上所述，(σ1，σ2，k)是基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名博弈的子博弈完美均衡行動(dòng)組合。由3.2 知(σ1，σ2，k)還是基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名博弈的納什均衡行動(dòng)組合。所以，基于社會(huì)承諾機(jī)制的理性同時(shí)生效簽名滿足穩(wěn)定性。

4 結(jié)束語(yǔ)

本文將社會(huì)承諾機(jī)制進(jìn)行改進(jìn)，使得社會(huì)承諾機(jī)制具有不可抵賴性，并將其引入到同時(shí)生效簽名中，構(gòu)建了一個(gè)理性同時(shí)生效簽名協(xié)議，協(xié)議滿足正確性、模糊性、不可偽造性，進(jìn)而基于博弈論提出理性同時(shí)生效簽名協(xié)議公平性和穩(wěn)定性的形式化定義，用博弈樹(shù)分析其納什均衡和子博弈完美均衡，證明協(xié)議滿足理性公平性和穩(wěn)定性，解決了同時(shí)生效簽名的發(fā)起方掌握一定程度的額外權(quán)力的問(wèn)題。然而，本文的通信次數(shù)和簽名長(zhǎng)度相比于文獻(xiàn)［1］并沒(méi)有降低，也就是說(shuō)，在一般情況下無(wú)效率優(yōu)勢(shì)，但其較好的公平性和穩(wěn)定性，使該理性公平的同時(shí)生效簽名協(xié)議更適用于無(wú)需可信第三方的比較大額的電子簽名交換。

［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］徐晉暉，石純一.一個(gè)基于信念－期望－意圖和效用的社會(huì)承諾機(jī)制［J］.軟件學(xué)報(bào)，1999，10(8):829－834.

［12］田有亮，馬建峰，彭長(zhǎng)根.秘密共享體制的博弈論分析［J］.電子學(xué)報(bào)，2011，39(12):32－46.

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