一种基于多服务器的分布式电子拍卖方案

刘 玉，薛开平

(1. 合肥学院管理系，合肥 230 601；2. 中国科学技术大学电子工程与信息科学系，合肥 23002 7)

一种基于多服务器的分布式电子拍卖方案

刘 玉1，薛开平2

(1. 合肥学院管理系，合肥 230 601；2. 中国科学技术大学电子工程与信息科学系，合肥 23002 7)

电子拍卖是传统拍卖的在线实现，其中，密封式电子拍卖由于其所具有的隐私保护和安全性受到广泛关注，但目前多数方案都是基于存在可信第三方假设的，而实际中很难建立可信的第三方。为此，基于LaGrange门限秘密共享体制和BIT承诺方法，设计一种多服务器参与的分布式电子拍卖方案。在投标阶段，投标者基于LaGrange门限秘密共享方案将投标结果分别提供给不同的拍卖服务器；在开标阶段，由不少于一定阈值的服务器提交结果，并基于BIT承诺方法得出最终投标者。该方案可避免单服务器的单点瓶颈，同时保护用户隐私，规定只有成功投标者的身份和投标价格才能被揭示。安全性和效率分析结果表明，该方案满足一个安全电子拍卖方案的要求，同时能节省计算开销和通信开销。

多拍卖服务器；分布式电子拍卖；密封式拍卖；BIT承诺；LaGrange门限秘密共享；投标者匿名

1 概述

随着社会的发展，拍卖作为一种有效的价格决定方法也逐渐发展成熟，在日常生活中应用也越来越多，并形成了一套独特的经济学理论体系，在市场经济中具有重要作用。近年来，随着电子技术和Internet网络的发展，信息技术作为工具被引入到商务活动中产生了电子商务。由于在网络的平台上进行商务活动，因此电子商务具有市场范围大、交易快捷、成本低廉等优点。而使用网络平台来实现拍卖活动即产生了电子拍卖。电子拍卖按照标价是否公开可以分为开放式拍卖和密封式拍卖[1]。密封式拍卖由于其所具有的隐私保护和安全性越来越受到关注[2]。

一个安全的密封式拍卖需要满足以下6个基本要求：

(1)投标者匿名：投标参与者的隐私得到保护，除非最终投标成功，否则身份不被暴露；

(2)不可否认性：成功的投标者不能否认其投标；

(3)可证实性：可以公开证明最终成功投标者的合法性；

(4)投标价保密：除最终成功投标的价格之外的其他所有投标者的价格应该保持保密性，不被泄露；

(5)时限性：确保在所有参与投标者都投标结束后，才能开始揭示投标结果；

(6)公平性：投标者地位相同，系统无偏向性。

现有多数电子拍卖方案都基于假设存在一个可信第三方，方案的以上属性都建立在第三方可信假设成立的基础上。而在电子拍卖系统中，第三方的可信性假设往往是被质疑的，因此，大量的分布式拍卖方案被陆续提出：文献[3]基于环签名提出了一种投标者匿名的电子拍卖方案；文献[4]提出了一种无注册中心的基于拉格朗日秘密分享技术和多方安全计算技术的安全分布式电子拍卖方案；在国内，文献[2]提出了一种基于不可信第三方的电子拍卖方案；文献[5]提出了一个新的安全的分布式电子拍卖协议。对于上文所提出的六大属性，现有的方案往往在保证某些属性的前提下弱化了其他属性，或者需要复杂的计算开销和通信开销。文献[6]基于可验证签名共享技术给出了一个利用电子现金秘密投标进行电子拍卖的协议，但依然基于可信第三方假设；文献[7]强化了投标者匿名和投标价保密的特性，但计算开销较大；文献[8]提供了一种多物品拍卖时如何保证投标价保密的方案，但并不满足电子拍卖的所有要求，且开销需要进一步优化；文献[9]提出了一种基于拉格朗日(LaGrange)多项式和BIT承诺的密封式电子拍卖方案，但其缺乏真正的匿名信保证，同时，计算开销也较大。此外，文献[10]提出了一种基于背包问题的电子拍卖方案，但与文献[9]类似，匿名性保证和开销问题有待于进一步优化。

本文借鉴文献[9]方案，采用多拍卖服务器参与的系统架构，从而弱化传统方案中存在可信第三方的假设，进而提出一种优化的分布式拍卖方案。

2 预备知识

2.1 BI T承诺

BIT承诺方案是密码学协议的重要组成成分，其基本思想描述如下：当承诺者Alice向接受者Bob承诺一个消息时，一方面，Bob不可能获得承诺信息的任何信息，另一方面，经过一段时间后，Alice能够向Bob证实她所承诺的消息，但BIT承诺方案要能够保证Alice不能够欺骗Bob。一种典型的BIT承诺协议见文献[11]。BIT承诺协议具有不可否认性、不可伪造性和完整性，是实现抗否认攻击的有力工具[12]。

本文所用到的BIT承诺方法描述如下：

2.2 La Grange门限秘密共享体制

秘密分享系统是将秘密s在一组包含n个参与者的集合P中进行分配，文献[13-14]分别给出了(t, n)门限体制的定义，它将秘密s分成n份发送给集合中的n个参与者，使得P中任意子集A，如果A中元素不少于t个，可以重构出秘密s；否则，不可重构s。文献[13]则利用有限域GF( P)上的t–1次多项式：

构造秘密共享的(t, n)门限体制。其中，所选随机素数p要大于最大可能的秘密s和与总数n，并且公开；s=h(0)=a0为秘密，而a1, a2,…,at-1为选用的随机系数，这些均需保密，在生成n个秘密份额后即可销毁。通过计算多项式h( x) 对n个不同xi的取值就给出每个人的秘密份额：

每个(xi, si)都是曲线h上的一点，因此，任意t个点都可以唯一确定对应的t–1次多项式：

所以，秘密s可以从任意t个秘密份额中重构，即h(0)。

3 系统模型

如图1所示，整个系统由一个卖者、n个拍卖服务器和m个投标人组成，其中参与各方均有自己的公钥私钥对。拍卖持续期间，每个拍卖服务器(例如i)对应一个随机数βi∈Zp。系统中设置一电子公告牌，用于公布一些即时的信息，提供即时交互和公开验证功能。

图1 系统组成结构

4 方案描述

方案包含设标、投标、开标、认证过程4个过程，具体描述如下。

4.1 设标过程

拍卖开始时，卖者公布商品信息，并公布k个可接受的标价p1,p2,…,pk，设定价格是逐渐下降的，即p1＞p2＞…＞pk。投标者也只能从这k个中选择其一作为投标价格。

4.2 投标过程

投标的具体步骤如下：

Step1 除非中标，投标者都希望能够保护自己的身份不被泄露。因而，在本文的方案中，在投标前，按本文2.1节所描述的BIT承诺方法，每个投标者首先计算一个临时的安全标识SID，计算为：

其中，rj为随机数；IDj为投标者的全局用户标识；EPuK j()表示公钥加密；EPrKj()表示采用私钥加密，即签名。

Step2 每个投标者(例如第j个，j=1,2,…,m)，选择k个如下形式的t项多项式(t＜n)：

其中，l=1,2,…,k，所有的系数都是随机选择的。对于sj, l做如下设定：如果投标者j的投标价格等于当前价格pl，那么sj, l=SIDj, l=1,2,…,k ，否则sj, l=0。

Step3 投标者j根据每个拍卖服务器发布的随机数β（ii=1,2,…,n），计算投标向量：

投标者向各个拍卖服务器(例如为i)发送如SIDj和相应的投标向量。

Step4 每个拍卖服务器(例如为i)收到所有投标者的投标向量后，得到以下矩阵：

Step5 每个投标者向电子公告牌发布自己的安全标识SID和r值。

4.3 开标阶段

为避免泄漏更多的信息和减少不必要的计算开销，开标的过程本文设定为交互式的，即卖者在电子公告牌上设定当前的考察价格，从大到小一个一个地开标，即第一次开标的价格为p1，然后p2，以此类推。开标的具体步骤如下：

Step1卖者在电子公告牌上设定当前的考察价格为pl(首先为l=1，然后l=2,3,…,k，以此类推)，各个拍卖服务器(举例为i)就向电子公告牌提供与此价格对应的Fl(βi)的值。

Step2所有人都可以使用不少于t个Fl(βi)的值，根据LaGrange秘密共享理论恢复出一个形如下式的多项式：

对于s的值，结果可能为3种情况：

(1)s=0，表明没有人对此价格投标，那么此时需要降低考察价格重复以上步骤，即l=l+1，返回Step1。

(2)s为电子公告牌上发布的某个安全标识SID，那么表明只有一个投标者对此价格进行了投标，s的值为此投标者的安全标识值，此时表示有唯一用户拍卖成功。成功投标者就是该安全标识对应的用户，成功投标者提供自己的用户标识，通过4.4节的验证，则拍卖成功。

(3)s≠0，且为多个2个安全标识的加和，那么表明有多个投标者对此价格投标。通过计算得到电子公共牌上发布的多个安全标识。相应的投标者按本文4.4节的方法分别对这几个安全标识进行声明，并成功通过BIT承诺验证，则对应的多个投标者进入下轮拍卖，若验证失败，则说明其中有欺诈行为，不允许对应的投标者进入下轮拍卖。

需要注意的是，在本文方案中，只有在本轮拍卖中投了最高价格的投标者才能参与下轮的拍卖，而其他投标者则不需要再进行投标，再次进行拍卖时，系统重新执行本文4.1节～4.3节步骤，以此类推，直至得出拍卖结果，这样就大大提高了拍卖效率。

4.4 验证阶段

5 安全性和效率分析

5.1 安全性分析

本文方案中使用了LaGrange多项式秘密共享体制和BIT承诺技术，整个方案没有可信的第三方的参与。

本文方案按照备选的多个可能的价格按照自高而低的开标方式，使得投标者的投标值的私密性得到了极大的保证，即除了各轮拍卖的获胜投标值公布外，其他的投标值在开标阶段均不重构，从而有效地解决了其他方案中非最终成功投标用户的投标价泄漏问题。此外，这种开标方式还大大减少了重构投标值时的计算开销，有利于提高系统的效率。

本文方案使用BIT承诺技术，可有效防止恶意投标人问题，虚假的投标或者投无效的标值在BIT认证阶段能够被有效地发现，使得拍卖秩序得到保障。同时SID的使用保证了用户的匿名性，在有用户声明对某个SID的拥有之前，任何人都无法知道SID和ID之间的关联关系。而对某个SID的拥有需要通过BIT 承诺的证明过程。在本文方案中，只有最终成功投标的用户才需要揭示和证明自己的身份。

此外，结合LaGrange秘密共享技术和电子公告牌，本文方案的另一个重要的优点是可以实现公开验证，即拍卖的任何一个参与方都可以验证成功投标者的合法性。在开标完成前，即使拍卖服务器也无法知道拍卖价格和最终的成功投标者。

5.2 效率分析

在投标阶段，假设按照自高而低，卖者在电子公告牌上设定当前的考察价格为pl，根据t个拍卖服务器提供的Fl(βi)可以恢复出Fl(x)：

(1)如果Fl(0)=0，则为4.3节Step2中的第1种情况，选择次低的考察价格为再次进行开标过程；

(2)如果Fl(0)等于电子公告牌上公示的某个SID，则为本文4.3节Step2中的第2种情况，当前考察价格即为成功拍卖的最终价格，某个用户在通过验证后即为最终的成功投标者；

(3)如果Fl(0)为电子公告牌上的几个SID的加和同余，则为本文4.3节Step2中的第3种情况，则通过验证的用户进入下一轮的拍卖，重新执行本文方案的过程。

在文献[5-6]方案中，需要针对每个用户解拉格朗日多项式，这样对于某个特定的考察价格需要求解m个LaGrange多项式，而在本文中只需要求解一个LaGrange多项式即得到结果。相比较于文献[9]方案，本文方案可以直接得到中标的投标，并且采用临时的安全标识，保证了用户的私密性，只有最终成功投标者才被要求公开，符合拍卖的基本规则。

在本文方案中，每轮拍卖只有在本轮拍卖中投了最高价的投标者才能参加下轮的拍卖，而其他投标者不需要再进行投标，符合拍卖的基本原则。同时在开标过程中采用考察价格逐渐下降的方式，当求得某个拍卖价格时的拉格朗日多项式常数项不为0时，小于当前考察价格的，将不需要再求解，这样做的好处是大大提高了系统的效率，减少了许多计算开销和通信量。

6 结束语

本文基于LaGrange多项式秘密共享体制，结合BIT承诺，提出一种多拍卖服务器参与的分布式拍卖方案，该方案能够满足密封式拍卖所要求的安全需求，且具有高效的特点。下一步将从优化交互流程和协议信令的设计角度完善本文方案，并构建原型系统。

[1] 庞 雷, 罗守山, 耿 涛, 等. 保护隐私的逢低买入拍卖协议及其推广[J]. 北京邮电大学学报, 2012, 35(3): 99-102.

[2] 曹 刚. 基于不可信第三方的电子拍卖方案[J]. 计算机工程, 2010, 36(20): 140-141, 144.

[3] Chang Chin-Chen, Cheng Tingfang, Chen Weiyi. A Nov el Electronic English Auction System with a Secure On-shelf Mechanism[J]. IEEE Transactions on Information Forensics and Security, 2013, 8(3/4): 657-668.

[4] Kikuchi H, Hakavy M, Tygar D. Multi-round Anonymous Auction Protocols[J]. IEICE Transactions on Information and Systems, 1999, E82-D(4): 769-777.

[5] 姬东耀, 王育民. 一个新的分布式安全电子拍卖协议[J].计算机学报, 2001, 24(5): 449-454.

[6] Franklin M K, Reiter M K. The Design and Implementation of a Secure Auction Service[J]. IEEE Transactions on Software Engineering, 1996, 22(5): 302-312.

[7] Li Ming-Jheng, Jua n J S, Tsai J Hui. Practical Electronic Auction Schem e w ith Strong A nonymity and Bidding Privacy[J]. Information Sciences, 2011, 181(12): 2576-2586.

[8] Shiha Dong-Her, Ye nb D C, Cheng Chih-Hung, et al. A Secure Multi-item E-auction Mechanism w ith Bid Privacy[J]. Computers & Security, 2011, 30(4): 273-287.

[9] 章志明, 邓建刚, 余 敏. 一种安全有效的多轮电子拍卖协议[J]. 计算机工程, 2006, 32(10): 157-158, 195.

[10] 章志明, 邓建刚, 余 敏. 一种基于背包理论的有效多轮电子拍卖协议[J]. 计算机工程与应用, 2006, 42(4): 207-209.

[11] 王继林, 余斌霄, 王育民. 一类基于BIT 承诺的安全电子拍卖模型[J]. 计算机学报, 2004, 27(3): 347-351.

[12] 郑 东, 陈克非, 谷大武, 等. 一种有效的比特承诺方案[J].通信学报, 2000, 21(2): 78-80.

[13] Shmir A. How to S hare a Secret[J]. ACM Communications, 1979, 22(11): 612-613.

[14] Blakley G R. S afeguarding Cryptographic Keys[C]//Proc. of AFIIPS’79. New York, USA: [s. n.], 1979: 313-317.

编辑 金胡考

A Distributed Electronic Auction Scheme Based on Multiple Servers

LIU Yu1, XUE Kai-ping2

(1. Department of Management, Hefei University, Hefei 230601, China; 2. Department of Electric Engineering & Information Science, University of Science and Technology of China, Hefei 230027, China)

Electronic auction is online realizatio n of traditional actions. Due to its privacy protection and security, sealed-bid auction scheme attracts widespread attention. However, most of these auction schemes are based on the assumption of existing trusted th ird party, which is often difficult to be esta blished in fact. Based on LaGrange threshold se cret sharing sche me and BIT comment mechanism, a distributed electronic auction scheme w ith multiple servers is proposed in this pape r. In the bidding phase, based on LaG range threshold secret sharing scheme, the bidder computes fragmentations of the bidding result and separately gives them to different auction servers. In the opening phase, no less than a certain threshold of servers s ubmit their fragmentations. The final success bidder can be verified by BIT commit based m ethod. It not only prevents a single point of bottleneck of a si ngle auction server, but also cuts down auction proces s computational overhead. The scheme ensures the protection of users’ privacy, only the identity of the final successful bidder and the relative bid price can be revealed. Analysis results of the security a nd performance show tha t it satisfies the requirements of a secure electronic auction scheme. Meanwhile, it can reduce the computation and communication overhead.

multiple auction servers; distributed electronic auction; sealed-bid auction; B IT commitment; LaGrange threshold secr et sharing; bidder anonymity

10.3969/j.issn.1000-3428.2014.05.025

国家自然科学基金资助项目(60903216)；安徽省自然科学基金资助项目(090412048)；安徽省优秀青年人才基金资助项目(2012SQRW127)。

刘 玉(1981－)，女，讲师、硕士，主研方向：信息安全；薛开平，副教授、博士。

2014-01-16

2014-03-11E-mail：sissi_liuyu@163.com

1000-3428(2014)05-0120-04

A

TP309