本文研究了英式电子拍卖的安全协议，给出一个安全电子拍卖方案。该方案实现了竞拍者身份的匿名性、获胜竞拍者的不可否认性、可公开验证性、竞拍者不可伪装性、可跟踪同一拍卖中某竞拍者的投标以及某个竞拍者在不同拍卖中不可关联性等问题。本文的工作重点是引入了可信第三方并利用知识证实签名来解决其它协议中撤消竞拍者的问题，可简单地撤消某个竞拍者并保证拍卖的高效率。
1 引 言
拍卖是起源于对古董珍品等没有固定价格的商品而进行一种交易活动。随着互联网的迅速发展，网上电子商务活动的日益增多，电子拍卖交易也在Internet网上快速地开展起来，也出现了Yahoo 拍卖[1]等电子拍卖系统。目前电子拍卖主要有以下三种形式：（1）英式拍卖，是最普遍的一种交易形式。用户竞出他们乐意出的最高价，交易期限一到，交易也同时停止，物品将卖给出价最高者。（2）最高价秘密投标，买主在竞拍开始后将标书密封形式投标，在卖家公布投标结束后打开标书，由出价最高者成交。（3）最二高价秘密投标，也是一种密封投标方式，不同之处在于最高出价者是以第二最高出价者所出价格买走交易品。
电子拍卖系统的发展也提出许多安全方面的问题，本文研究了英式电子拍卖协议的安全问题，给出一个电子拍卖的安全协议，工作重点是引入了可信第三方的并利用知识证实签名解决了撤消竞拍者和效率低的问题。本文方案可简单有效地撤消竞拍者，从而保证了拍卖的高效率。
本文的结构安排如下：第 2节简要介绍了电子拍卖的基本协议、应有特性以及已有的相关工作；第 3节通过可信第三方的引入基于知识证实签名设计了一个高效地可撤消竞拍者的英式电子拍卖方案；第 4节分析了我们方案的安全性和性能分析；第5节作为本文的结束语；
2 电子拍卖的背景及其相关方案
电子拍卖协议由以下几个基本部分组成：
在电子拍卖过程中要保护竞拍者的匿名性及竞拍者的投标信息，任何人包括权威机构都无法单独地获得竞拍者的身份及其投标信息。拍卖结束后只公开赢家的身份及最高出价，任何人都能验证拍卖结果的有效性。电子拍卖系统应有特性：
目前大部分的电子拍卖方案是基于群签名方案[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ｑ (这里"‖"表示串的连接操作，Ｈ表示无碰撞单向散列函数)，传送(ｃ,ｒ)给验证者。
验证者：检验ｃ
Ｈ( ｍ‖ｇ‖ｈ‖ｇrｈc ) 。
定义2 满足ｃ=Ｈ( ｍ‖ｇ‖ｈ‖rｈc )的二元组 (ｃ,ｒ)称为是ｈ关于底ｇ的离散对数的知识，对于消息ｍ∈{ 0, 1}* 的签名，记为：ＳＰＫ{αｈ =ｇa } (ｍ)。
。 
，并计算公钥为
； 
（这里的mC 是CA公布的消息）向CA证实其知道以g为底的 yi 的离散对数 xi，并登记其身份信息； 
并计算 
(mod p) (i=1,…,I) 和gr ; } ( i=1,…,I )，而竞拍者的身份信息保密。 
来确认自己是当前拍卖的合法竞拍者。因为CA每次拍卖都会重新选择一个随机数r，这样在每次拍卖中每个竞拍者都有不同的公开密钥 。 
并利用已知的
计算
(mod p)； 
，公布混乱后的{Ti}(i=1,…,I) ，
和当前拍卖物品信息。 计算Ti =
，并且核实该Ti 是否已经存在于AM所公开的{Ti}(i=1,…,I)中。 由于每次拍卖都会重新选取随机数s，每个用户在每次拍卖中有不同的Ti =
（mod p）。除了AM没有人能知道 和Ti 对应关系，因为 被AM所选取的保密随机数s隐藏。但AM并不知道yi 与Ti 的对应关系，因为yi 被CA所知道的保密随机数 r 隐藏。所以CA及AM都无法单独从已经公开的信息中获得竞拍者的身份。由于在每次拍卖都将重新随机选择r及s ，所以可以保证在多次拍卖中竞拍者身份的不可关联性。
当竞拍者Bi出价时，他发送如下投标信息(
) 给AM，其中
是Ti 的标识号，mi 为拍卖品编号与出价；
，V2i 是竞拍者Bi 利用知道的 xi 的知识对mi 的签名， 并由此证实自己是一个合法的竞拍者。
AM验证投标书的知识证实签名V2i 来确认标书有效，而且由于{ }(i=1,…,I)的公开，任何人都能够验证该投标书。假如验证不通过，AM 丢掉该非法的投标书。通过验证知识证实签名V2i的有效性，可确认该投标书的发送者Bi 确实拥有私钥xi并由此证实自己是一个合法的竞拍者。
假设竞拍者 Bk 是拍卖的最终获胜者，其投标书为(
)。为了揭示该获胜者的身份，AM必须公开证实Tk 与
是相关联的，以便CA能够揭示获胜者身份。AM生成如下的知识证实签名来证实Tk 与
是相关联的：
其中mc 是CA发布的消息。AM公开(
)及V3k ，利用V2k 和 Tk 可以验证获胜投标书的有效性，利用mk 可知该拍卖品的最高出价。任何人都可以通过验证V3k 的有效性来确认Tk 与
是相关联。可信权威机构CA验证知识证实签名V3k有效性后，CA就能确认Tk 与 是相关联，并能揭示获胜者的身份。
和 yk 相关联的。于是CA生成知识证实签名V4k ： 
，其中ma 是AM公布的信息。CA公开 V4k 、
和 yk ，那么任何人都能通过验证签名 V4k 的有效性来确认获胜者身份。拍卖方案示意图见图1。 
4 方案的安全性及性能分析
知道他投标次数及出价，但仍不知该竞拍者身份。 
为底 
的离散对数，也就是知道了 xi ,这相当于求解离散对数问题，因此即使CA和AM共谋也不能伪装成某个竞拍者进行竞拍，其他竞拍者更无法伪装成另一个竞拍者来投标。 任何竞拍者能够仅一次注册参加多个拍卖，即使是获胜竞拍者在参与下一轮的拍卖活动时也无需重新注册，拍卖过程中他的身份匿名性仍能得到保护。
在英式电子拍卖过程中，撤消竞拍者是频繁发生的，如竞拍者想要撤出拍卖过程或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
新闻热点
疑难解答
