基于社會承諾機制的理性同時生效簽名方案及其公平性＊

任祉靜，彭長根，劉 海

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

同時生效簽名，即公平交換電子簽名，不需要可信第三方參與，能有效解決公平交換電子簽名中的不公平問題，且不需要很強的交互性，主要應用于電子合同簽署、電子招標等方面。

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

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

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

1 基礎知識

1.1 離散對數(shù)問題

1.2 擴展型博弈

1.2.1 擴展式博弈

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

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

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

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

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

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

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

子博弈:由一個動態(tài)博弈第一階段以外的某階段開始的后續(xù)博弈階段構(gòu)成的，有初始信息集和進行博弈所需要的全部信息，能夠自成博弈的原博弈的一部分，稱為原動態(tài)博弈的一個子博弈。即，一個擴展型博弈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 以后的部分。

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

1.3 社會承諾機制

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

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

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

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

B:責任(條件;必須采取行動;效用;期限)

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

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

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

2 基于社會承諾機制的理性同時生效簽名

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

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

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

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

2.2 基于社會承諾機制的理性同時生效簽名的形式化定義

定義1 基于社會承諾機制的理性同時生效簽名算法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={對象組P，約束R，期限D(zhuǎn)，簽名的身份〈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〉，如果拒絕，執(zhí)行COMMIT;

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

2.3 基于社會承諾機制的理性同時生效簽名方案

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

(1)選取兩個大素數(shù)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 函數(shù)H1，H2:{0，1}*→Zq，設定消息空間和關(guān)鍵數(shù)空間M=K={0，1}*，簽名空間和關(guān)鍵數(shù)映射空間S=F=Zq;

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

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

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

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

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

如果等式成立，則P2選擇一個消息MB進行簽名。計算

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

(5)P1到P2的簽名σ2后進行模糊驗證，

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

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

3 基于社會承諾機制的理性同時生效簽名的安全性分析

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

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

3.1 正確性

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

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

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

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

3.2 公平性

基于社會承諾機制的理性同時生效簽名用擴展式博弈描述如圖1 所示。

圖1 擴展式博弈

其形式化表述為:

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

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

下面給出理性公平的定義，提出定理并進行證明。

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

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

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

在第二階段，F(xiàn)(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)=根據(jù)P2會最大化效用，即:max u2，所以，h2|h1=σ2。

在第一階段，F(xiàn)(ε)=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，根據(jù)P1會最大化效用，即:max u1，所以，h1=σ1。

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

3.3 穩(wěn)定性

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

如:文獻［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在第三階段行動如下:

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

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

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

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

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

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

4 結(jié)束語

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

［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.