劉 玉，薛開平

(1. 合肥學(xué)院管理系，合肥 230 601；2. 中國科學(xué)技術(shù)大學(xué)電子工程與信息科學(xué)系，合肥 23002 7)

一種基于多服務(wù)器的分布式電子拍賣方案

劉 玉1，薛開平2

(1. 合肥學(xué)院管理系，合肥 230 601；2. 中國科學(xué)技術(shù)大學(xué)電子工程與信息科學(xué)系，合肥 23002 7)

電子拍賣是傳統(tǒng)拍賣的在線實現(xiàn)，其中，密封式電子拍賣由于其所具有的隱私保護和安全性受到廣泛關(guān)注，但目前多數(shù)方案都是基于存在可信第三方假設(shè)的，而實際中很難建立可信的第三方。為此，基于LaGrange門限秘密共享體制和BIT承諾方法，設(shè)計一種多服務(wù)器參與的分布式電子拍賣方案。在投標(biāo)階段，投標(biāo)者基于LaGrange門限秘密共享方案將投標(biāo)結(jié)果分別提供給不同的拍賣服務(wù)器；在開標(biāo)階段，由不少于一定閾值的服務(wù)器提交結(jié)果，并基于BIT承諾方法得出最終投標(biāo)者。該方案可避免單服務(wù)器的單點瓶頸，同時保護用戶隱私，規(guī)定只有成功投標(biāo)者的身份和投標(biāo)價格才能被揭示。安全性和效率分析結(jié)果表明，該方案滿足一個安全電子拍賣方案的要求，同時能節(jié)省計算開銷和通信開銷。

多拍賣服務(wù)器；分布式電子拍賣；密封式拍賣；BIT承諾；LaGrange門限秘密共享；投標(biāo)者匿名

1 概述

隨著社會的發(fā)展，拍賣作為一種有效的價格決定方法也逐漸發(fā)展成熟，在日常生活中應(yīng)用也越來越多，并形成了一套獨特的經(jīng)濟學(xué)理論體系，在市場經(jīng)濟中具有重要作用。近年來，隨著電子技術(shù)和Internet網(wǎng)絡(luò)的發(fā)展，信息技術(shù)作為工具被引入到商務(wù)活動中產(chǎn)生了電子商務(wù)。由于在網(wǎng)絡(luò)的平臺上進行商務(wù)活動，因此電子商務(wù)具有市場范圍大、交易快捷、成本低廉等優(yōu)點。而使用網(wǎng)絡(luò)平臺來實現(xiàn)拍賣活動即產(chǎn)生了電子拍賣。電子拍賣按照標(biāo)價是否公開可以分為開放式拍賣和密封式拍賣[1]。密封式拍賣由于其所具有的隱私保護和安全性越來越受到關(guān)注[2]。

一個安全的密封式拍賣需要滿足以下6個基本要求：

(1)投標(biāo)者匿名：投標(biāo)參與者的隱私得到保護，除非最終投標(biāo)成功，否則身份不被暴露；

(2)不可否認(rèn)性：成功的投標(biāo)者不能否認(rèn)其投標(biāo)；

(3)可證實性：可以公開證明最終成功投標(biāo)者的合法性；

(4)投標(biāo)價保密：除最終成功投標(biāo)的價格之外的其他所有投標(biāo)者的價格應(yīng)該保持保密性，不被泄露；

(5)時限性：確保在所有參與投標(biāo)者都投標(biāo)結(jié)束后，才能開始揭示投標(biāo)結(jié)果；

(6)公平性：投標(biāo)者地位相同，系統(tǒng)無偏向性。

現(xiàn)有多數(shù)電子拍賣方案都基于假設(shè)存在一個可信第三方，方案的以上屬性都建立在第三方可信假設(shè)成立的基礎(chǔ)上。而在電子拍賣系統(tǒng)中，第三方的可信性假設(shè)往往是被質(zhì)疑的，因此，大量的分布式拍賣方案被陸續(xù)提出：文獻[3]基于環(huán)簽名提出了一種投標(biāo)者匿名的電子拍賣方案；文獻[4]提出了一種無注冊中心的基于拉格朗日秘密分享技術(shù)和多方安全計算技術(shù)的安全分布式電子拍賣方案；在國內(nèi)，文獻[2]提出了一種基于不可信第三方的電子拍賣方案；文獻[5]提出了一個新的安全的分布式電子拍賣協(xié)議。對于上文所提出的六大屬性，現(xiàn)有的方案往往在保證某些屬性的前提下弱化了其他屬性，或者需要復(fù)雜的計算開銷和通信開銷。文獻[6]基于可驗證簽名共享技術(shù)給出了一個利用電子現(xiàn)金秘密投標(biāo)進行電子拍賣的協(xié)議，但依然基于可信第三方假設(shè)；文獻[7]強化了投標(biāo)者匿名和投標(biāo)價保密的特性，但計算開銷較大；文獻[8]提供了一種多物品拍賣時如何保證投標(biāo)價保密的方案，但并不滿足電子拍賣的所有要求，且開銷需要進一步優(yōu)化；文獻[9]提出了一種基于拉格朗日(LaGrange)多項式和BIT承諾的密封式電子拍賣方案，但其缺乏真正的匿名信保證，同時，計算開銷也較大。此外，文獻[10]提出了一種基于背包問題的電子拍賣方案，但與文獻[9]類似，匿名性保證和開銷問題有待于進一步優(yōu)化。

本文借鑒文獻[9]方案，采用多拍賣服務(wù)器參與的系統(tǒng)架構(gòu)，從而弱化傳統(tǒng)方案中存在可信第三方的假設(shè)，進而提出一種優(yōu)化的分布式拍賣方案。

2 預(yù)備知識

2.1 BI T承諾

BIT承諾方案是密碼學(xué)協(xié)議的重要組成成分，其基本思想描述如下：當(dāng)承諾者Alice向接受者Bob承諾一個消息時，一方面，Bob不可能獲得承諾信息的任何信息，另一方面，經(jīng)過一段時間后，Alice能夠向Bob證實她所承諾的消息，但BIT承諾方案要能夠保證Alice不能夠欺騙Bob。一種典型的BIT承諾協(xié)議見文獻[11]。BIT承諾協(xié)議具有不可否認(rèn)性、不可偽造性和完整性，是實現(xiàn)抗否認(rèn)攻擊的有力工具[12]。

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

2.2 La Grange門限秘密共享體制

秘密分享系統(tǒng)是將秘密s在一組包含n個參與者的集合P中進行分配，文獻[13-14]分別給出了(t, n)門限體制的定義，它將秘密s分成n份發(fā)送給集合中的n個參與者，使得P中任意子集A，如果A中元素不少于t個，可以重構(gòu)出秘密s；否則，不可重構(gòu)s。文獻[13]則利用有限域GF( P)上的t–1次多項式：

構(gòu)造秘密共享的(t, n)門限體制。其中，所選隨機素數(shù)p要大于最大可能的秘密s和與總數(shù)n，并且公開；s=h(0)=a0為秘密，而a1, a2,…,at-1為選用的隨機系數(shù)，這些均需保密，在生成n個秘密份額后即可銷毀。通過計算多項式h( x) 對n個不同xi的取值就給出每個人的秘密份額：

每個(xi, si)都是曲線h上的一點，因此，任意t個點都可以唯一確定對應(yīng)的t–1次多項式：

所以，秘密s可以從任意t個秘密份額中重構(gòu)，即h(0)。

3 系統(tǒng)模型

如圖1所示，整個系統(tǒng)由一個賣者、n個拍賣服務(wù)器和m個投標(biāo)人組成，其中參與各方均有自己的公鑰私鑰對。拍賣持續(xù)期間，每個拍賣服務(wù)器(例如i)對應(yīng)一個隨機數(shù)βi∈Zp。系統(tǒng)中設(shè)置一電子公告牌，用于公布一些即時的信息，提供即時交互和公開驗證功能。

圖1 系統(tǒng)組成結(jié)構(gòu)

4 方案描述

方案包含設(shè)標(biāo)、投標(biāo)、開標(biāo)、認(rèn)證過程4個過程，具體描述如下。

4.1 設(shè)標(biāo)過程

拍賣開始時，賣者公布商品信息，并公布k個可接受的標(biāo)價p1,p2,…,pk，設(shè)定價格是逐漸下降的，即p1＞p2＞…＞pk。投標(biāo)者也只能從這k個中選擇其一作為投標(biāo)價格。

4.2 投標(biāo)過程

投標(biāo)的具體步驟如下：

Step1 除非中標(biāo)，投標(biāo)者都希望能夠保護自己的身份不被泄露。因而，在本文的方案中，在投標(biāo)前，按本文2.1節(jié)所描述的BIT承諾方法，每個投標(biāo)者首先計算一個臨時的安全標(biāo)識SID，計算為：

其中，rj為隨機數(shù)；IDj為投標(biāo)者的全局用戶標(biāo)識；EPuK j()表示公鑰加密；EPrKj()表示采用私鑰加密，即簽名。

Step2 每個投標(biāo)者(例如第j個，j=1,2,…,m)，選擇k個如下形式的t項多項式(t＜n)：

其中，l=1,2,…,k，所有的系數(shù)都是隨機選擇的。對于sj, l做如下設(shè)定：如果投標(biāo)者j的投標(biāo)價格等于當(dāng)前價格pl，那么sj, l=SIDj, l=1,2,…,k ，否則sj, l=0。

Step3 投標(biāo)者j根據(jù)每個拍賣服務(wù)器發(fā)布的隨機數(shù)β（ii=1,2,…,n），計算投標(biāo)向量：

投標(biāo)者向各個拍賣服務(wù)器(例如為i)發(fā)送如SIDj和相應(yīng)的投標(biāo)向量。

Step4 每個拍賣服務(wù)器(例如為i)收到所有投標(biāo)者的投標(biāo)向量后，得到以下矩陣：

Step5 每個投標(biāo)者向電子公告牌發(fā)布自己的安全標(biāo)識SID和r值。

4.3 開標(biāo)階段

為避免泄漏更多的信息和減少不必要的計算開銷，開標(biāo)的過程本文設(shè)定為交互式的，即賣者在電子公告牌上設(shè)定當(dāng)前的考察價格，從大到小一個一個地開標(biāo)，即第一次開標(biāo)的價格為p1，然后p2，以此類推。開標(biāo)的具體步驟如下：

Step1賣者在電子公告牌上設(shè)定當(dāng)前的考察價格為pl(首先為l=1，然后l=2,3,…,k，以此類推)，各個拍賣服務(wù)器(舉例為i)就向電子公告牌提供與此價格對應(yīng)的Fl(βi)的值。

Step2所有人都可以使用不少于t個Fl(βi)的值，根據(jù)LaGrange秘密共享理論恢復(fù)出一個形如下式的多項式：

對于s的值，結(jié)果可能為3種情況：

(1)s=0，表明沒有人對此價格投標(biāo)，那么此時需要降低考察價格重復(fù)以上步驟，即l=l+1，返回Step1。

(2)s為電子公告牌上發(fā)布的某個安全標(biāo)識SID，那么表明只有一個投標(biāo)者對此價格進行了投標(biāo)，s的值為此投標(biāo)者的安全標(biāo)識值，此時表示有唯一用戶拍賣成功。成功投標(biāo)者就是該安全標(biāo)識對應(yīng)的用戶，成功投標(biāo)者提供自己的用戶標(biāo)識，通過4.4節(jié)的驗證，則拍賣成功。

(3)s≠0，且為多個2個安全標(biāo)識的加和，那么表明有多個投標(biāo)者對此價格投標(biāo)。通過計算得到電子公共牌上發(fā)布的多個安全標(biāo)識。相應(yīng)的投標(biāo)者按本文4.4節(jié)的方法分別對這幾個安全標(biāo)識進行聲明，并成功通過BIT承諾驗證，則對應(yīng)的多個投標(biāo)者進入下輪拍賣，若驗證失敗，則說明其中有欺詐行為，不允許對應(yīng)的投標(biāo)者進入下輪拍賣。

需要注意的是，在本文方案中，只有在本輪拍賣中投了最高價格的投標(biāo)者才能參與下輪的拍賣，而其他投標(biāo)者則不需要再進行投標(biāo)，再次進行拍賣時，系統(tǒng)重新執(zhí)行本文4.1節(jié)～4.3節(jié)步驟，以此類推，直至得出拍賣結(jié)果，這樣就大大提高了拍賣效率。

4.4 驗證階段

5 安全性和效率分析

5.1 安全性分析

本文方案中使用了LaGrange多項式秘密共享體制和BIT承諾技術(shù)，整個方案沒有可信的第三方的參與。

本文方案按照備選的多個可能的價格按照自高而低的開標(biāo)方式，使得投標(biāo)者的投標(biāo)值的私密性得到了極大的保證，即除了各輪拍賣的獲勝投標(biāo)值公布外，其他的投標(biāo)值在開標(biāo)階段均不重構(gòu)，從而有效地解決了其他方案中非最終成功投標(biāo)用戶的投標(biāo)價泄漏問題。此外，這種開標(biāo)方式還大大減少了重構(gòu)投標(biāo)值時的計算開銷，有利于提高系統(tǒng)的效率。

本文方案使用BIT承諾技術(shù)，可有效防止惡意投標(biāo)人問題，虛假的投標(biāo)或者投無效的標(biāo)值在BIT認(rèn)證階段能夠被有效地發(fā)現(xiàn)，使得拍賣秩序得到保障。同時SID的使用保證了用戶的匿名性，在有用戶聲明對某個SID的擁有之前，任何人都無法知道SID和ID之間的關(guān)聯(lián)關(guān)系。而對某個SID的擁有需要通過BIT 承諾的證明過程。在本文方案中，只有最終成功投標(biāo)的用戶才需要揭示和證明自己的身份。

此外，結(jié)合LaGrange秘密共享技術(shù)和電子公告牌，本文方案的另一個重要的優(yōu)點是可以實現(xiàn)公開驗證，即拍賣的任何一個參與方都可以驗證成功投標(biāo)者的合法性。在開標(biāo)完成前，即使拍賣服務(wù)器也無法知道拍賣價格和最終的成功投標(biāo)者。

5.2 效率分析

在投標(biāo)階段，假設(shè)按照自高而低，賣者在電子公告牌上設(shè)定當(dāng)前的考察價格為pl，根據(jù)t個拍賣服務(wù)器提供的Fl(βi)可以恢復(fù)出Fl(x)：

(1)如果Fl(0)=0，則為4.3節(jié)Step2中的第1種情況，選擇次低的考察價格為再次進行開標(biāo)過程；

(2)如果Fl(0)等于電子公告牌上公示的某個SID，則為本文4.3節(jié)Step2中的第2種情況，當(dāng)前考察價格即為成功拍賣的最終價格，某個用戶在通過驗證后即為最終的成功投標(biāo)者；

(3)如果Fl(0)為電子公告牌上的幾個SID的加和同余，則為本文4.3節(jié)Step2中的第3種情況，則通過驗證的用戶進入下一輪的拍賣，重新執(zhí)行本文方案的過程。

在文獻[5-6]方案中，需要針對每個用戶解拉格朗日多項式，這樣對于某個特定的考察價格需要求解m個LaGrange多項式，而在本文中只需要求解一個LaGrange多項式即得到結(jié)果。相比較于文獻[9]方案，本文方案可以直接得到中標(biāo)的投標(biāo)，并且采用臨時的安全標(biāo)識，保證了用戶的私密性，只有最終成功投標(biāo)者才被要求公開，符合拍賣的基本規(guī)則。

在本文方案中，每輪拍賣只有在本輪拍賣中投了最高價的投標(biāo)者才能參加下輪的拍賣，而其他投標(biāo)者不需要再進行投標(biāo)，符合拍賣的基本原則。同時在開標(biāo)過程中采用考察價格逐漸下降的方式，當(dāng)求得某個拍賣價格時的拉格朗日多項式常數(shù)項不為0時，小于當(dāng)前考察價格的，將不需要再求解，這樣做的好處是大大提高了系統(tǒng)的效率，減少了許多計算開銷和通信量。

6 結(jié)束語

本文基于LaGrange多項式秘密共享體制，結(jié)合BIT承諾，提出一種多拍賣服務(wù)器參與的分布式拍賣方案，該方案能夠滿足密封式拍賣所要求的安全需求，且具有高效的特點。下一步將從優(yōu)化交互流程和協(xié)議信令的設(shè)計角度完善本文方案，并構(gòu)建原型系統(tǒng)。

[1] 龐 雷, 羅守山, 耿 濤, 等. 保護隱私的逢低買入拍賣協(xié)議及其推廣[J]. 北京郵電大學(xué)學(xué)報, 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] 姬東耀, 王育民. 一個新的分布式安全電子拍賣協(xié)議[J].計算機學(xué)報, 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] 章志明, 鄧建剛, 余 敏. 一種安全有效的多輪電子拍賣協(xié)議[J]. 計算機工程, 2006, 32(10): 157-158, 195.

[10] 章志明, 鄧建剛, 余 敏. 一種基于背包理論的有效多輪電子拍賣協(xié)議[J]. 計算機工程與應(yīng)用, 2006, 42(4): 207-209.

[11] 王繼林, 余斌霄, 王育民. 一類基于BIT 承諾的安全電子拍賣模型[J]. 計算機學(xué)報, 2004, 27(3): 347-351.

[12] 鄭 東, 陳克非, 谷大武, 等. 一種有效的比特承諾方案[J].通信學(xué)報, 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

國家自然科學(xué)基金資助項目(60903216)；安徽省自然科學(xué)基金資助項目(090412048)；安徽省優(yōu)秀青年人才基金資助項目(2012SQRW127)。

劉 玉(1981－)，女，講師、碩士，主研方向：信息安全；薛開平，副教授、博士。

2014-01-16

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

1000-3428(2014)05-0120-04

A

TP309