本文研究了英式电子拍卖的安全协议，给出一个安全电子拍卖方案。该方案实现了竞拍者身份的匿名性、获胜竞拍者的不可否认性、可公开验证性、竞拍者不可伪装性、可跟踪同一拍卖中某竞拍者的投标以及某个竞拍者在不同拍卖中不可关联性等问题。本文的工作重点是引入了可信第三方并利用知识证实签名来解决其它协议中撤消竞拍者的问题，可简单地撤消某个竞拍者并保证拍卖的高效率。
1 引 言
拍卖是起源于对古董珍品等没有固定价格的商品而进行一种交易活动。随着互联网的迅速发展，网上电子商务活动的日益增多，电子拍卖交易也在Internet网上快速地开展起来，也出现了Yahoo 拍卖[1]等电子拍卖系统。目前电子拍卖主要有以下三种形式：（1）英式拍卖，是最普遍的一种交易形式。用户竞出他们乐意出的最高价，交易期限一到，交易也同时停止，物品将卖给出价最高者。（2）最高价秘密投标，买主在竞拍开始后将标书密封形式投标，在卖家公布投标结束后打开标书，由出价最高者成交。（3）最二高价秘密投标，也是一种密封投标方式，不同之处在于最高出价者是以第二最高出价者所出价格买走交易品。
电子拍卖系统的发展也提出许多安全方面的问题，本文研究了英式电子拍卖协议的安全问题，给出一个电子拍卖的安全协议，工作重点是引入了可信第三方的并利用知识证实签名解决了撤消竞拍者和效率低的问题。本文方案可简单有效地撤消竞拍者，从而保证了拍卖的高效率。
本文的结构安排如下：第 2节简要介绍了电子拍卖的基本协议、应有特性以及已有的相关工作；第 3节通过可信第三方的引入基于知识证实签名设计了一个高效地可撤消竞拍者的英式电子拍卖方案；第 4节分析了我们方案的安全性和性能分析；第5节作为本文的结束语；
2 电子拍卖的背景及其相关方案
电子拍卖的基本协议：
电子拍卖协议由以下几个基本部分组成：
初始化：拍卖治理者(简称AM)选择系统参数并公布这些参数及有关拍卖品的信息（如拍卖品编号、拍卖时间等）；
竞拍者注册：每个竞拍者发送他的公钥给AM进行注册；
拍卖预计算：AM为此次拍卖计算协议中所需数据，竞拍者可以下载这些公开数据；
拍卖：竞拍者计算他的拍卖密钥并且投标出价；
拍卖结束：公开获胜竞拍者，AM通过计算得到赢家的身份及他的出价，而其它出价保密，任何人都能公开地验证赢家的投标出价。
电子拍卖系统应具有的特性：
在电子拍卖过程中要保护竞拍者的匿名性及竞拍者的投标信息，任何人包括权威机构都无法单独地获得竞拍者的身份及其投标信息。拍卖结束后只公开赢家的身份及最高出价，任何人都能验证拍卖结果的有效性。电子拍卖系统应有特性：
竞拍者的匿名性：即使在拍卖结果公开后，包括可信权威机构的任何人都不能获知竞拍失败人的身份及其投标出价;
不可抵赖性：获胜竞拍者不能否认其已经提交的最高出价，而且可以确切地获得的获胜竞拍者身份。
公开验证性：任何人都能公开验证获胜竞胜者有效性，并能验证获得获胜竞拍者是所有竞拍者中的最高出价方。
不可欺骗性：任何人都不能伪装某个已注册的竞拍者进行竞价；
协议健壮性：即使竞拍者提交一个无效的投标，拍卖过程也不会受到影响；
拍卖的效率：在英式电子拍卖中拍卖的效率是非常重要的，因为竞拍者不断地实时地出价，因此英式电子拍卖协议主要是提高拍卖的效率，拍卖过程的验证投标书及撤消竞拍者的计算量和通信量应适合实际使用。
相关电子拍卖方案
目前大部分的电子拍卖方案是基于群签名方案[2-4]构造的，K . Nguyen和J. Traore所设计的英式电子拍卖方案[5]（简称NT拍卖方案）就是这样的一个典型方案，这个方案主要实现了竞拍者的匿名性。但NT拍卖方案同时具有了与群签名方案相似的缺陷，首先是群签名是一个复杂签名生成和签名验证的过程，需要大量的模乘运算，同样NT拍卖过程经常需要生成签名、验证签名和验证投标书的有效性，这是严重的效率问题。其次NT方案的第二缺陷是很难撤消一个竞拍者，拍卖初始化时竞拍者的成员证书已经被分发，而在拍卖过程中撤消竞拍者是较频繁的，如竞拍者想要撤出拍卖或拍卖治理者想要取消某个竞拍者的竞拍资格，那么所有竞拍者的证书不得不重新分发，将严重影响拍卖的进行。文献[8，9]实现了一个可撤消成员的群签名方案，然而在英式电子拍卖协议中频繁撤消竞拍人的情况下使用这两个方案的效率是极低的。针对基于群签名现有方案的缺点，我们引入可信第三方来构造一个新的英式电子拍卖方案，该方案有着简单的拍卖过程和验证过程，大大地减少了拍卖过程及投标书验证所需的计算量和通信量，提高了拍卖效率。而且撤消竞拍者是轻易且高效地。
3 高效地可撤消竞拍者的英式电子拍卖方案
我们基于离散对数的知识证实签名设计了高效地可撤消竞拍者的英式电子拍卖方案，方案的要害点是引入可信第三方（简称CA），而不是象现有方案使用组签名方案。本节将具体介绍此方案：
基于离散对数的知识证实签名
本方案是基于离散对数密码技术来描述的，其安全性依靠于离散对数问题（Discrete Logarithm PRoblem）的难解性，离散对数问题定义如下：
定义1 给定大素数 p 且满足 p>2512，有限域 Zp* 的生成元 g ，已知 y ∈ Zp** ，很难求得整数 x ,使得 gx =y (mod p)。
在我们的方案中所使用的盲签名方案是Camenish和Michels[4]所提出的知识证实的签名方案。这个知识证实签名是基于Schnorr签名方案[10]，若证实者想向验证者证实他知道h关于底ｇ的离散对数(即ｘ=log g h)的知识，并用这个离散对数对消息ｍ∈ { 0, 1}*做签名，他可以通过以下的协议来实现：
证实者：随机选取ｓ∈RＺq ,计算ｈ1=ｇs,ｃ=Ｈ(ｍ‖ｇ‖ｈ‖ｈ1)和ｒ=ｓ-ｃｘ modｑ (这里"‖"表示串的连接操作，Ｈ表示无碰撞单向散列函数)，传送(ｃ,ｒ)给验证者。
验证者：检验ｃ
定义2满足ｃ=Ｈ( ｍ‖ｇ‖ｈ‖rｈc )的二元组 (ｃ,ｒ)称为是ｈ关于底ｇ的离散对数的知识，对于消息ｍ∈{ 0, 1}* 的签名，记为：ＳＰＫ{αｈ =ｇa } (ｍ)。
电子拍卖方案
CA初始化：选择两个大素数p、q ，且满足q > 2160，p>2512，q (p-1) 。定义乘法群Zq*上的阶为ｑ的子群Gq以及Gq的生成元
竞拍者Bi注册：
竞拍者Bi 选择私钥
Bi 发送yi 给CA，利用知识证实签名
CA验证 Bi 所发送的公钥 yi 有效的并公开 yi ；
拍卖预计算：设有 I 个已注册竞拍者参加拍卖。
在拍卖开始前CA随机选取一个随机数
可信第三方CA公开如下参数：{p, q, g}，gr ，竞拍者Bi的公钥和混乱后的 {
竞拍者Bi通过验证
AM随机选取一个随机数
AM为每个竞拍者Bi 计算拍卖密钥Ti =
竞拍者Bi利用AM公开的
由于每次拍卖都会重新选取随机数s，每个用户在每次拍卖中有不同的Ti =
拍卖
当竞拍者Bi出价时，他发送如下投标信息(
AM验证投标书的知识证实签名V2i 来确认标书有效，而且由于{
拍卖结束：
假设竞拍者 Bk 是拍卖的最终获胜者，其投标书为(
其中mc 是CA发布的消息。AM公开(
公开获胜者： CA公开的获胜者身份，为了向AM证实获胜者身份属实，需证实
4 方案的安全性及性能分析
安全性分析：
竞拍者身份匿名性。包括AM在内的任何人在没有CA的帮助下都无法从已公开的信息中获得竞拍者的身份信息。即使竞拍获胜者的身份在以前的拍卖中被揭示，他也能匿名地竞拍以后的其他拍卖活动。
不可否认性：CA验证AM提供的信息有效，并根据这些信息来揭示竞拍获胜者身份。而竞拍获胜者无法否认其已经提交过的获胜投标。
公开验证性：任何人都能验证投标书的签名 V2i , 而且任何人都能通过验证拍卖密钥确认一个竞拍者是否是有效竞拍者。任何人通过检验签名 V3k 、V4k 来公开地验证公开的获胜者Bk 身份信息。
健壮性：AM通过验证签名V2i 不合法性，则拒绝接受该投标书，当然也要拒绝低于当前出价的投标书。
在多次拍卖中的不可关联性：由于CA和AM在每次拍卖中选取的随机数 r 和 s 不同，一个竞拍者在每次拍卖中所使用的密钥也不同，没有人能将这个竞拍者在不同拍卖中的投标书联系起来。
同一拍卖中的关联性：在一次拍卖中任何人能通过某个竞拍者在拍卖中签名所使用相同的
不可伪造性：在拍卖中，CA和AM都不能伪造某个竞拍者的投标书来出价。假设他们能伪造竞拍者 Bi 对进行知识证实签名 V2i，那就意味着他们知道以
协议性能分析
一次注册
任何竞拍者能够仅一次注册参加多个拍卖，即使是获胜竞拍者在参与下一轮的拍卖活动时也无需重新注册，拍卖过程中他的身份匿名性仍能得到保护。
简单的可撤消性
在英式电子拍卖过程中，撤消竞拍者是频繁发生的，如竞拍者想要撤出拍卖过程或CA撤消某个欺诈的竞拍者。所以要求撤消竞拍者是简单而轻易的，而且当某个竞拍者被取消竞拍资格后，他的拍卖记录仍应该是保密的。在我们的方案中，CA只需要删除该竞拍者的相关信息：竞拍者的身份信息及其公钥。而文献[8，9]所提出的方案在英式电子拍卖协议中频繁撤消竞拍者的情况下的效率是极低的，我们的方案撤消竞拍者是很轻易而且高效地。
计算量与通信量
若用文献[2]的群签名方案设计的电子拍卖方案比NT拍卖方案更有效率。我们对比本文方案与文献[2]的组签名方案的计算量与通信量，对于文献[2]方案的效率，生成签名平均需要11000次模1200位数的模乘运算，签名的长度为1K 字节；而我们的方案，生成签名相当于计算知识证实签名V2i ,所以只需要220次模1200位数的模乘运算，签名长度只有约50字节长。可以看出本文方案一次拍卖过程的计算量和通信量都大大地减少。另外拍卖预计算也减少拍卖过程的计算量，CA和AM只需O(I)计算量来更新每个竞拍者的拍卖密钥，竞拍者只需下载这些拍卖密钥即可。
5 结束语
我们设计了一个高效地可撤消竞拍者的英式电子拍卖方案，不是象其它电子拍卖方案中使用群签名技术，而是引入了可信第三方并利用知识证实签名方法，该方案实现了竞拍者身份的匿名性、获胜竞拍者身份的可跟踪性、可公开验证性、可跟踪同一拍卖中某竞拍者的投标及某个竞拍者在不同拍卖中是不可关联等安全问题。本文的工作重点是解决了在拍卖过程中撤消竞拍者问题，该协议使得竞拍者的撤消简单而高效率。另外本协议计算量与通信量小，使得拍卖可以在PDA等有限计算能力手持终端上进行，使得电子拍卖更加方便、可靠。
QQRead.com 推出数据恢复指南教程 数据恢复指南教程
数据恢复故障解析
常用数据恢复方案
硬盘数据恢复教程
数据保护方法
数据恢复软件
专业数据恢复服务指南
参考资料
Yahoo. http://aUCtions.yahoo.com
J. Camenisch and M. Michels . " A Group Signature Scheme with Improved Efficiency". In Advances in Cryptology- ASIACRYPT'98, LNCS 1514, Springer-Verlag, pages 160-174,1998.
J. Camenisch and M. Michels . " Separability and Efficiency for Generic Group Signature Schemes". In Advances in Cryptology- ASIACRYPT'99, LNCS 1666, Springer-Verlag, pages 106-121, 1999.
J. Camenisch and M. Stadler. "Efficient Group Signature Schemes for Large Groups". In Advances in Cryptology- ASIACRYPT'97, LNCS 1294, Springer-Verlag, pages 410-424,1997.
K. Nguyen and J. Traore. " An Online Public Auction Protocol Protocol protecting Bidder Privacy". In Proceeds of the 5th Australasian Conference on Information and Privacy(ACISP 2000), LNCS 1841, Springer-Verlag, pages 427-442, 2000.
Y. Frankel, Y. Tsiounis, M.Yung In direct discourse proof: achieving fair off line e-cash [A]. Proc. of Asiacrypt'96[C]. German: Springer Verlag, 1996. 286-300.
Frankel Y, Tsiounis Y, Yung M. Fair off-line e-cash made easy[A], Proc. of Asiacrypt'96[C]. Berlin: Springer Verlag, 1998.257-270.
E. Bresson and J. Stern. "Efficient Revocation in Group Signatures". In Proceedings of the 4-th International Workshop on Practice and Theory in Public Key Cryptosystems(PKC 2001), LNCS 1992, Springer-Verlag, pages 190-206, 2001.
H. Kim, J. Lim, and D.Lee. "Efficient and Secure Member Deletion in Group Signature Schemes". In Proceedings of the Third International Conference on Information Securtiy and Cryptology(ICISC 2000), LNCS 2015, Springer-Verlag, pages 150-161, 2000.
C. Schnorr, Efficient Identification and Signatures for Smart-Cards, Advances in cryptology: Proceedings of Eurocrypt'89, Berlin, LNCS 435, pp. 239-252,Springer-Verlag, 1990.
关于作者
戴元军，男，28岁，北京邮电大学信息安全中心博士生，参加国家自然科学基金项目、国家973项目、国家863项目，并已发表多篇学术文章。主要研究方向：网络安全与信息安全，密码学，电子支付，数字水印。Email: dai_yuanjun@163.com
