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

劉 玉，薛開平

(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