基于并发签名的公平交易协议的分析与改进

孙艳宾，谷利泽，孙燕，卿斯汉，杨义先，陈广辉

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