基于并發簽名的公平交易協議的分析與改進

孫艷賓，谷利澤，孫燕，卿斯漢，楊義先，陳廣輝

(1. 北京郵電大學 網絡與交換技術國家重點實驗室信息安全中心，北京 100876；2. 北京郵電大學 網絡與信息攻防技術教育部重點實驗室，北京 100876；3. 石家莊陸軍指揮學院 軍事運籌中心，石家莊 050084；4. 北京大學 軟件與微電子學院，北京 102600)

1 引言

隨著計算機網絡的發展，如何在互不信任的各方之間以公平的方式通過網絡進行電子數據的交易受到廣泛關注。公平交易是指當兩方或多方在利用協議交易信息時，能保證其參與者或者得到期望的電子數據信息或者得不到任何有用的信息。公平交易協議(FEP)是實現公平交易的關鍵，在設計公平交易協議時，公平性是最基本的也是最難實現的安全性質。

公平交易協議一直是安全協議領域的研究熱點，研究人員提出了很多不同的解決方案。公平交易協議大致分為2類：逐步公平交易協議和帶可信第三方(TTP)的公平交易協議。由于逐步公平交易協議[1,2]需要逐步釋放相關秘密消息和假設交易雙方擁有相同的計算能力，因此對交易雙方并不能實現真正的公平性。目前，研究人員關注的重點是帶TTP的公平交換協議。根據TTP介入的程度和介入的方式可把帶 TTP的公平交換協議分為以下 2大類：On-line TTP公平交易協議[3～5]和Off-line公平交易協議[6～8]。其中，On-line TTP需要介入交易過程，幫助參與者完成公平交易，經常在交易雙方之間扮演一個強制中介的角色；而Off-line TTP正常情況下不介入交易過程，只有當某個參與者不誠實或者交易雙方發生糾紛時才介入，以保證協議順利完成。

目前對公平交易協議的研究中 TTP一直是制約其執行效率的一個瓶頸，因此降低對TTP的依賴是目前公平交易協議的研究重點，而能夠設計出無需 TTP又能保證公平的交易協議一直是設計公平交易協議的目標。Chen等在文獻[9]中提出了并發簽名(CS)，這一新穎的概念為實現上述目標提供了一種途徑。即，無需第三方參與即可實現參與者雙方公平的交換簽名的目的。Susilo等在文獻[10]中指出：在文獻[9]中，如果交易雙方都誠實，任何第三方在keystone公布之前都能區分出2個模糊簽名的真正簽署方，從而文獻[9]中并發簽名方案并沒有達到真正的模糊性。為了實現真正的模糊性，Susilo等對文獻[9]中的并發簽名方案進行了改進，利用Schnorr環簽名和雙線性對構造了 2個完美的并發簽名(PCS)方案。然而文獻[9, 10]中的交易協議僅實現了弱公平性，原因在于：交換雙方各自生成相應消息的模糊簽名并發送給對方，而初始簽名者擁有相關秘密消息keystone。如果初始簽名者不公布秘密消息keystone，則雙方的模糊簽名無法綁定到其真實的簽名者(即任何第三方，在 keystone公布之前，他只能判斷2個模糊簽名是由交易雙方所生成，而無法區分出具體的簽署方)。從而初始簽名者可以選擇對自己有利的時機公布keystone。

Chen等在文獻[11]中基于Schnorr環簽名PCS方案[10]構造了一個簡潔高效且無需 TTP參與的公平交易協議(簡記為CQQY協議)。交易雙方起初交換相關數據的模糊簽名，然后發起者公布秘密消息keystone (keystone公布之前任何第三方無法區分出2個模糊簽名的真正簽署者)，2個模糊簽名同時綁定到交易雙方，之后另一方發送解密商品的密鑰，從而實現雙方公平得到對方物品的目的。同時Chen等人通過分析，聲稱協議能保證弱公平性、不可否認性以及不可濫用性。

不可濫用性[12～15]作為公平交易協議所需滿足的條件越來越受到研究者的關注。而不可濫用性是指交易的任何一方都不能向第三方證明他有能力使交易內容生效或無效，即任意參與方都不能向第三方證明他得到了另一參與方對交易內容的承諾。CQQY協議的不可濫用性是通過 PCS方案[10]的模糊性來實現的。

本文通過分析指出在2個參與者都誠實可信的情況下，CQQY協議并不滿足不可濫用性。即CQQY協議中交易雙方產生的2個模糊簽名，在keystone公布之前，任意第三方都能區分出2個模糊簽名的真正簽署方。從而其中一個參與者可以向第三者聲稱得到了另外一方對交易內容的承諾。根據PCS方案的思想，本文對CQQY協議進行了改進，改進的公平交易協議在保證公平性、安全性、不可否認性的基礎上滿足不可濫用性。

2 預備知識

2.1 完美并發簽名算法

文獻[10]中的基于 Schnorr環簽名的完美并發簽名（PCS）方案包括：參數建立，模糊簽名算法，模糊驗證算法及其驗證算法。其具體算法如下。

1) 參數建立：設置消息與 keystone空間，M=K={0 ,1}*，F=。隨機選擇2個大素數 p , q滿足q( p - 1 )，q階生成元 g ∈Zp，散列函數H1, H2∶{0 ,1}* → Zq， xi和 yi為 公 私 鑰 對 ， 且= gximodp ， i = 1 ,2。

2) 模糊簽名算法：輸入參數為(yi, yj, xi, s, m)，輸 出模 糊簽 名 σ = ( c, s′, s)。 而 s = H1(k),k ∈ K,m∈M，

3) 模糊驗證算法：輸入（ σ , yi, yj, m ），如果成立，則輸出“接受”，否則輸出“拒絕”。

4) 驗證算法：輸入(k, S)，此處k∈K，S =(σ,yi, yj, m)。首先執行keystone驗證算法：如果 H1( k ) = s 成立，則i為初始簽名者；如果H1( k ) = s ′成立，則j為初始簽名者；如果前2種情況都不成立，則k無效，輸出“拒絕”。如果k驗證通過以后，執行模糊驗證算法，如果模糊驗證算法輸出“接受”，則最終驗證算法輸出“接受”，否則輸出“拒絕”。

2.2 公平交易協議

基于上述簽名算法，陳廣輝等人提出了一個無需 TTP參與的可以交易數字商品的公平交易(CQQY)協議[11]。協議假設用戶 A和商家B之間的信道為安全信道，且分別有各自的銀行賬戶。其協議簡要步驟如下：

step 1 A →B∶(σA, mA)；

step 3 A → B ∶ (k, k′)；

step 4 B→ A ∶ k′′。

其中， mA表示用戶 A把訂單信息連同面值為數字商品價格的電子支票一起生成的消息；σA表示用戶A利用模糊簽名算法生成的關于消息 mA的模糊簽名；mB= H2(mB′)表示對已加密的商品內容 m ′B做散列運算的結果；σB表示用戶B利用模糊簽名算法生成的關于消息 mB′的模糊簽名；k與k′分別表示A和B的秘密消息keystone；k′表示B加密商品的密鑰。協議的詳細過程請參閱文獻[11]。

3 CQQY協議的不可濫用性分析

CQQY協議是一個高效簡潔的無需 TTP參與的公平交易協議，但當A和B均誠實時，協議并不滿足不可濫用性，原因在于協議不滿足模糊性。即，任意的第三者在keystone公布之前，都能區分出2個簽名的真實簽署方。

考慮下面的場景：假設A和B均誠實的按照協議的步驟執行公平交易協議，則在執行 step3之前，A得到B的簽名消息 (σB, m ′B,)，B得到A的簽名消息(σA, mA)。因為 A與 B均誠實，則(σA, yA, yB, mA)與(σB, yA, yB, mB′ )均可通過模糊驗證算法驗證。從而可得下面結論。

結論1 協議參與雙方均誠實時，CQQY協議不滿足不可濫用性，即，任意第三者在秘密消息keystone公布之前都能區分出(σA, yA, yB, mA)與(σB, yA, yB, mB′ )的真正簽署方。

證明 由于假設A，B誠實，則(σA, yA, yB, mA)與(σB, yA, yB, mB′ )為A，B的真實簽名，即可通過模糊驗證算法驗證。由2個模糊簽名可知，消息 mA與是不相同的，第三者可以通過區分這2個消息來區分2個簽名的真正簽署方。由于是B的商品的散列值，第三者可以從商家B的網站上下載被加密的商品，并通過公開的散列函數 H2(·)計算加密商品的散列值，然后分別與 mA， m ′B進行比較，即可分辨出2個簽名的真正簽署方。最壞情況，第三者計算商家B網站上所有被加密商品的散列值，逐一對比，由于B的商品有限，則在有限的時間內，第三者仍可分辨出2個簽名的真正簽署方。通過上述方法，當A收到(σB, yA, yB, mB′ )后，可以對第三者聲稱已得到B的簽名消息，且第三者可以進行驗證并相信(σB, yA, yB, mB′ )是B對 mB′的簽名。同樣，B收到(σA, yA, yB, mA)后也可以通過 mA向第三者聲稱得到了A的簽名消息。因此，CQQY協議不滿足不可濫用性。

從結論的分析過程以及完美并發簽名的定義出發，對CQQY協議進行了改進。

4 改進的CQQY協議

根據完美并發簽名的思想，本文對CQQY協議進行了改進，改進的公平交易(ICQQY)協議的具體過程如下。

step1 A→B∶ (σA,m)：當用戶A在B的網站上選中想要的商品后，用戶下載被加密的商品 mB′和訂單信息，并把訂單信息連同電子支票一起生成消息 mA，同時計算 mB= H2(m ′B)并與 mA級聯為消息m，記為 m =mA||mB。隨機選擇keystone k∈K，計算 s2= H1( k)。輸入 ( yA, yB, xA,s2, m )運行模糊簽名算法，輸出 σA= ( c, s1, s2)，并發送(σA, m)給B。

step2 B →A∶(σB,m,)：當B收到A的消息后，從m中分離出 mA與 mB，然后檢查訂單信息、A的身份以及電子支票等信息，若任何一項驗證不通過(包括對 mB的確認)，則退出；否則，B運行模糊驗證算法驗證(σA, yA, yB,m)，若輸出“拒絕”，則退出；否則，B隨機選擇 t ∈Zq，計算輸入 ( yB, yA, xB,s1′, m)運行模糊簽名算法，輸出σB= ( c′, s1′ , s2′)，最后B 發送 (σB, m,)給A。

step3 A → B ∶ (k, k′)：在A收到 (σB, m,)之后，計算 r =modp,k ′ = r m od q ，驗證 s1′ ( s2+H1(k'))modq是否成立；輸入運行模糊驗證算法，若輸出“拒絕”則退出；若輸出“接受”，則發送(k, k′)給B。

step4 B→ A ∶ k′′：當B收到(k, k′)后，此時2個模糊簽名σA與σB可以同時綁定到各自的簽署方，則B發送加密商品的秘密密鑰k′給A。

當A收到k′后，即可解密加密的商品。同時，當(k, k′)公開發布后，任何第三者都可驗證s2= H1( k), s1′ = ( s2+ H1( k ′ ))mod q 是否成立，并分別輸入(σA, yA, yB,m)與(σB, yA, yB,m)運行模糊驗證算法，若均輸出“接受”，則 2個簽名合法，否則簽名無效。

5 對ICQQY協議的分析

ICQQY協議的公平性與 CQQY協議的公平性分析相同，在此不再贅述，詳細過程請參閱文獻[11]。下面將對ICQQY協議的不可否認性、安全性、不可濫用性進行分析，其具體過程如下。

1) 不可否認性。

定理1[10]假設離散對數問題是困難的，則在隨機預言模型中完美的并發簽名方案在選擇消息攻擊下是存在不可偽造的。

證明 略(詳細過程參閱文獻[10])。

由于 ICQQY協議是基于 PCS方案[10]構造的,因此由定理1很容易得到下面的定理。

定理2 ICQQY協議滿足不可否認性。

證明 在ICQQY協議step1、step2消息中，A、B的簽名均為模糊簽名，任意第三方不能區分簽名的真正簽署方，而keystone公開以后，則 2個簽名通過驗證算法同時綁定到各自的簽署方，2個簽名同時生效。由定理1可知模糊簽名方案是不可偽造的，因此很容易得出 ICQQY協議滿足不可否認性。

2) 安全性。

ICQQY協議與 CQQY協議中信道的假設是相同的，即用戶A與商家B之間的信道為安全信道，而在實際的網上交易中可以通過加密信道來實現，同時由定理1可知協議所用的并發簽名方案是不可偽造的，因而可以保證交易的安全性。

3) 不可濫用性。

定理 3[10]在完美的并發簽名方案中，秘密消息keystone公布之前，雙方的簽名是模糊的。

證明 略(詳細過程參閱文獻[10])。

通過對CQQY協議的分析可知，CQQY協議的不可濫用性的設計思想是利用 PCS簽名的模糊性來實現的（由前面分析可知CQQY協議并不滿足不可濫用性），而ICQQY協議仍然沿用了這一思想來實現不可濫用性。

定理 4 ICQQY協議滿足不可濫用性，即，任意第三者在秘密消息keystone公布之前無法區分模糊簽名(σA, yA, yB,m)與(σB, yA, yB,m)的真正簽署方。

證明 在ICQQY協議中，假設用戶A和B都誠實，且分別計算模糊簽名并發給對方后，A、B雙方同時擁有(σA, yA, yB,m)與(σB, yA, yB,m)。由前面的分析可知，(σA, yA, yB,m)與(σB, yA, yB,m)都能通過模糊驗證算法驗證，同時由定理3可知，PCS簽名在秘密消息 keystone公布之前是滿足模糊性的，因此，ICQQY協議中，A、B中的一方在不公布秘密消息keystone的情況下，無法向第三者證明另外一方對協議交換的內容做了承諾。因為2個簽名都可以通過模糊驗證算法的驗證，且對于第三者來說，在秘密消息keystone公布之前(σA, yA, yB,m)與(σB, yA, yB,m)沒有任何區別，因此對于任意第三者在秘密消息公布之前都不能區分出2個模糊簽名(σA, yA, yB,m)與(σB, yA, yB,m)的真正簽署方。因此ICQQY協議滿足不可濫用性。

4) 效率。

ICQQY協議與CQQY協議相同，不需要可信第三方，從而避免了利用可信第三方交易的瓶頸，且雙方之間只需4次通信。與 CQQY協議相比，ICQQY協議中交易雙方只有用戶A增加了消息的散列以及消息的級聯運算，且運算都可以在線下進行，從而并未增加交易協議的信息量，因此ICQQY協議仍保持了CQQY協議的簡潔高效特性。

6 結束語

Chen等在文獻[11]中提出了一個簡潔高效的基于并發簽名的公平交易協議，此協議無需可信第三參與，且可進行數據條目的交易。通過對此協議進行分析，發現此協議并不滿足不可濫用性。進而根據PCS方案的思想對此協議進行了改進。改進的協議滿足公平性、不可否認性、安全性以及不可濫用性，且保持了原有協議簡潔高效的特點。

[1] BLUM M. How to exchange (secret) keys[J]. ACM Transactions on Computer Systems, 1983, 1(2)∶175-193.

[2] EVEN S, GOLDREICH O, LEMPEL A. A randomized protocol for signing contracts[J]. Communications of the ACM, 1985, 28(6)∶637-647.

[3] FRANKLIN M K, REITER M K. Fair exchange with a semi-trusted third party[A]. The 4th ACM Conference on Computer and Communications Security[C]. ACM Press, 1997. 1-5.

[4] ZHANG N, SHI Q. Achieving non-repudiation of receipt [J]. The Computer Journal, 1996, 39(10)∶844-853.

[5] ZHOU J Y, GOLLMANN D. A fair non-repudiation protocol[A]. IEEE Symposium on Security and Privacy, Research in Security and Privacy[C]. IEEE CSP, 1996. 55-61.

[6] ASOKAN N, SHOUP V, WAIDNER M. Asynchronous protocols for optimistic fair exchange[A]. Proceedings of the IEEE Symposium on Research in Security and Privacy[C]. 1998. 86-99.

[7] ASOKAN N, SHOUP V, WAIDNER M. Optimistic fair exchange of digital signatures[J]. IEEE Journal on Selected Areas in Communications, 2000, 18(4)∶593-610.

[8] BAO F, DENG R H, MAO W. Efficient and practical fair exchange protocols with off-line TTP[A]. Proceedings of 1998 IEEE Symposium on Security and Privacy [C]. Akland, USA, 1998. 77-85.

[9] CHEN L, KUDLA C, PATERSON K G. Concurrent signatures[A].Eurocrypt 2004[C]. LNCS 3027, Spriger-Verlag, Berlin, 2004. 287-305.

[10] SUSILO W, MU Y, ZHANG F. Perfect concurrent signature schemes[A].ICICS 2004[C]. Springer-Verlag, Berlin, 2004. 14-26.

[11] 陳廣輝, 卿斯漢, 齊志峰等. 新穎的基于并發簽名的公平交易協議[J].通信學報, 2008, 29(7)∶ 39-43.CHEN G H, QING S H, QI Z F, et al. Novel fair exchange protocol based on concurrent signature[J]. Journal on Communications. 2008,29(7)∶ 39-43.

[12] GARAY J A, JAKOBSSON M, MACKENZIE P. Abuse-free optimistic contract signing[A]. CRYPTO'99[C]. Springer- Verlag, Berlin Heidelberg 1999. 449-466.

[13] GAO W, LI F, XU B H. An abuse-free optimistic fair exchange protocol based on BLS signature[A]. CIS2008[C]. 2008. 841-845.

[14] WANG G L. An abuse-free fair contract signing protocol based on the RSA signature[A]. WWW2005[C]. Chiba, Japan, 2005. 412-421.

[15] WANG G L. An abuse-free fair exchange protocol based on rsa signature[J]. IEEE Transactions on Information Forensics and Security,2009, 5(1)∶158-168.