一種簡單高效的密封式電子拍賣方案

程文娟，董瑩瑩，韓俊光

?

一種簡單高效的密封式電子拍賣方案

程文娟，董瑩瑩，韓俊光

(合肥工業大學計算機與信息學院，合肥 230009)

針對目前大多數的電子拍賣方案都是假設存在一個可信第三方，使得電子拍賣的安全性有所降低的問題，提出一個基于不可信第三方的密封式電子拍賣方案。采用數字簽名技術對競拍者的身份進行驗證，確保競拍者身份的隱私性。在計算成交價時，基于離散對數求解的困難性，對競拍價的二進制長度進行加密封裝，保證競拍價的秘密性以及結果的正確性。分析結果證明，該方案設計簡單，安全性較高，在計算效率上相對于現有多數電子拍賣方案有較大的提高。

電子商務；密封拍賣；匿名性；競拍價保密；數字簽名；離散對數問題

1 概述

電子商務的發展使得電子拍賣成為電子商務中一個重要組成部分，近年來得到廣泛的研究。電子拍賣是指利用Internet，在網站上公開有關待出售物品或服務的信息，通過競爭投標的方式將它出售給競拍價最高的競拍者。電子拍賣按獲勝價位可分為：第一價位拍賣[1]，第二價位拍賣[2]和+1價位拍賣[3]。按競拍價是否公開可分密封式和開放式拍賣，密封式拍賣要求在規定時間前，每個投標者秘密地提交一個投標價，在規定時間后才能打開投標并按一定的確定性規則選出中標者。本文討論的方案屬于第一價位密封式拍賣。

一個實用的密封式電子拍賣方案必須滿足以下要求[4]：(1)正確性：能正確產生最高價的競拍者；(2)競拍者的匿名性：即使在拍賣結果公開后，所有參與者都不能獲知其他競拍失敗人的身份及其競拍價；(3)不可抵賴性：獲勝競拍者不能否認其已經提交的最高競拍價，而且可以確切地獲得的獲勝者身份；(4)不可欺騙性：任何人都不能偽裝某個已注冊的競拍者進行競價；(5)競拍價的保密性：競拍者的競拍價保密；(6)高效性：協議的計算量要盡可能的少。

本文設計了一種密封式電子拍賣方案，該方案基于一個不可信第三方即拍賣中心參與成交價的計算，拍賣中心最后僅知道成交價而不知道其他競拍價，滿足密封式拍賣對安全性的要求，并對本文設計的密封式電子拍賣方案與其他密封式電子拍賣協議進行分析比較。

2 密封式電子拍賣的研究現狀

現有的大多數電子拍賣方案都是基于一個可信或半可信的第三方，約定第三方不能與競拍者勾結。然而，這一假設是不現實的，很難確保其安全性[5]。在實際拍賣中，沒有競拍者愿意泄漏自己的競拍價，甚至不愿意泄漏競拍價之間的非平凡關系(如大小關系)，防止產生拍賣過程中的作弊行為[6]。因此，拍賣過程中競拍者的匿名性和競拍價的秘密性尤為重要，同時使拍賣的效率盡可能的高。研究密封式電子拍賣的方案較多，如加密體制[7]、零知識證明[8]、位承諾[9]、環簽名技術[10]、Hash函數[11]、多方的秘密計算等。

文獻[1]給出了一種利用矩陣和分布式ElGamal公鑰密碼體制來實現的第一價位電子拍賣方案，方案可實現完全隱私性，但是并不能排除賣方和某些投標者合謀的可能性，且計算量大、效率低。文獻[8]設計的方案主要運用了ElGamal加密體制和零知識證明，與文獻[1]方案相比，通信量相當，但計算量明顯減少。文獻[9]通過改造Bit承諾協議，將盲簽名技術應用于Bit承諾協議的生成階段，設計一種密封式的電子拍賣方案。該方案實現了密封式電子拍賣方案的所有安全要求，同時可以抵御多種合謀攻擊行為。但在拍賣結束后，中標者的所有信息都是由中標者自己公布，存在一定程度的不可信性。

本文利用數字簽名技術和離散對數問題求解困難性，設計一個密封式第一價位電子拍賣方案，當拍賣結果公開時，只有獲勝競拍者的競拍價會公開，其余競拍價都是保密的。本文設計的方案方法簡單，安全性較高，在效率上相對于現存的大多數電子拍賣方案有較大的改進。

3 密封式電子拍賣方案設計

3.1 電子拍賣模型設計

本文方案包括4個實體，即競拍者、注冊中心、拍賣中心和賣方。

(1)競拍者：想購買拍賣的物品并參加競價活動的參 與者。

(2)注冊中心：負責競拍者參與競拍活動前的注冊并分配注冊序號給競拍者，并選擇一種函數作為拍賣規則發送給各競拍者。當競拍結果公布后，注冊中心根據獲勝者的注冊序號公布獲勝者的身份。

(3)拍賣中心：一個不可信的第三方，驗證競拍者的身份是否合法，當拍賣時間結束后，與競拍者交互計算出成交價，公布成交價及獲勝者的注冊序號，通知注冊中心公布獲勝者身份信息。

(4)賣家：出售物品的人。

這些實體所組建一個電子拍賣模型如圖1所示。

圖1 電子拍賣模型

在模型中，首先競拍者要向注冊中心注冊，注冊中心給競拍者分配一個序號用來參加后來的競拍；拍賣中心驗證競拍者身份，并在計算成交價時與競拍者之間存在著交互的過程；當結果產生后，拍賣中心通知注冊中心公布獲勝者的身份并告知賣家拍賣的結果。值得一提的是，拍賣中心與注冊中心之間只存在一個單向通信通道，注冊中心不能給拍賣中心發送任何信息，以防止注冊中心泄露拍賣規則和競拍者的身份。

3.2 方案基本思想

密封式電子拍賣事實上是推廣了百萬富翁問題，百萬富翁問題是指2個百萬富翁Alice和Bob想知道他們2個誰更富有，但他們都不想讓對方知道自己財富的任何信息，其實質就是在不泄露雙方信息的條件下比較2個數的大小。在本文設計中，有個參與者1,2,…,P，各有一個秘密輸入1,2,…,m，在拍賣中心參與下，安全計算出最高競拍價。基本思想如下：競拍價最高的競拍者將勝出，如果多個競拍者出了同樣的最高價，那么只有先注冊的競拍者勝出，這種解決方法是合理的，因為注冊越早表明其得到商品意愿更強烈，注意拍賣的最終意愿是在競拍價最大化的基礎上，把商品分配給最需要的競拍者，實現社會資源的最優分配。本文采用姚氏百萬富翁問題的高效解決方案[12]中任意2個數比較方法的基本思想，把每個競拍者的競拍價m轉化成二進制數F(m)，再通過一定的函數()對其進行封裝，其中，()為一個在第一象限內的單調遞增函數，最終比較的是(F(m))的大小，淘汰(F(m))較小的P，被淘汰的P終止比較，以此類推，直到最后的優勝者即為獲勝者。

3.3 方案具體執行步驟

密封式電子拍賣方案具體執行步驟如下：

(1)初始化：假設協議中涉及的通信都是采用多方計算標準的安全廣播信道模型，所有安全參數都已經由正確的程序產生，關于拍賣商品的信息、拍賣時間、拍賣規則和交易規則都已經公布在公告牌上。

(2)注冊：競拍者P向注冊中心提交一個競拍申請，注冊中心按注冊的先后順序分配注冊序號給競拍者，并發送拍賣規則的函數()給各競拍者，本文方案中，選擇()=，為大于1的正小數。

(3)身份驗證：競拍者用ElGamal數字簽名技術來證明自己的身份的合法性[13]。令、是大素數，滿足|?1，表示Z*的階子群，是<>上的階生成元，P選擇一個隨機數作為私鑰，計算公鑰=gmod。具體步驟如下：

1)產生簽名

P選擇一個隨機數(<且與?1互素)，計算=gmod，解同余方程g=yrmod，得到，則(,)為的簽名，將(,,)發送給拍賣中心。

2)驗證簽名

拍賣中心計算g=yrmod，若式g成立，則簽名有效，說明競拍者身份合法，允許參加競拍活動；若式g不成立，則置該注冊序號為無效注冊號，不允許無效注冊號參與競拍活動。

(4)競拍：驗證完競拍者的身份后，合法的競拍者P選擇一個競拍價m，并以m二進制表示的位數F(m)作為自變量計算出U=(F(m))(或點擊客戶端自動生成)，把它作為自己的秘密輸入發送給拍賣中心。

(5)計算成交價：當規定的拍賣時間結束后，拍賣中心開始計算最高競拍價，產生拍賣活動的獲勝者及成交價，為此本文設計了一個簡單高效的密封式電子拍賣協議來進行計算，協議具體如下：

一個簡單高效的密封式電子拍賣協議步驟如下：

Step1競拍者P(=1,2,…,)將各自的私有輸入U發送給拍賣中心；

Step2拍賣中心比較每個競拍者私有輸入U的大小，選出U的最大值，記()為U=的個數：

(1)若()=1，則U=的這個競拍者P獲勝，轉Step5；

Step3拍賣中心通知U=的P計算m=m?2－1，回到Step1繼續比較；

Step4若拍賣中心在Step3中一直循環比較，最后()2，則可斷定出同樣的最高價的競拍者不止一個人，比較這些出最高價的競拍者的注冊序號的大小，選出其中注冊序號最小的競拍者勝出，即為獲勝者；

Step5拍賣中心不斷讓獲勝者P輸入F(m)，其中，m=m?2－1，直到F(m)=0為止，那么拍賣中心即可計算出獲勝者的競拍價，即成交價；

Step6拍賣中心公布獲勝者的競拍價及其注冊序號并通知注冊中心，注冊中心公布注冊序號為的競拍者身份信息。

3.4 方案說明

由于每個競拍者在參與競拍前都通過數字簽名技術進行身份驗證，使得競拍者不能否認自己的競拍活動，惡意競拍者也不能偽造競拍價和發送的數據，整個協議都是在安全的信道下進行。協議在執行過程中，都是把競拍價轉化為以正小數為底數，競拍價的二進制位數F(m)為指數的單調遞增函數，使得拍賣中心很難通過這個信息了解到競拍者的競拍價，由于注冊中心和拍賣中心之間的信道是單向的，拍賣中心不知道注冊中心發送拍賣規則()，即使有惡意的競拍者和拍賣中心勾結，透露給拍賣中心()，在本文方案的函數也是基于離散對數求解問題，拍賣中心很難通過該函數來破解競拍者的競拍價，除非F(m)=1,2時，才容易猜到競拍價，這樣的小數目在電子拍賣中很少出現。

4 密封式電子拍賣方案分析

4.1 安全性能分析

下面從設計安全電子拍賣方案的角度分析該方案能否實現前面敘述的安全電子拍賣的要求。

(1)正確性：根據協議描述，最終由出價最高的競拍者勝出(在協議中已有詳細的描述，這里就不再贅述)。

(2)競拍者的匿名性：每一個競拍者都是以注冊中心分配的序號參與拍賣活動的，拍賣中心和其他競拍者不知道競拍者的真實身份，實現競拍者身份的匿名性。

(3)不可抵賴性：拍賣中心和獲勝者交互計算成交價時，獲勝者并不知道此時自己勝出，所以拍賣中心公布成交價后，獲勝者不能抵賴或篡改自己的競拍價。

(4)不可欺騙性：競拍者在競拍前都通過數字簽名技術來進行身份認證，由于數字簽名技術具有能夠核實簽名者的作用，因此任何人都不能偽裝成已注冊的競拍者來參加競拍活動。

(5)競拍價的保密性：拍賣中心和所有競拍者除了知道成交價以外，并不知道其他競拍者的競拍價，因此實現了競拍價的保密性。

4.2 效率分析

本文協議的效率主要是看拍賣中心的計算量，拍賣中心在第一次比較出值時進行了?1次比較，由文獻[12]可知，F(m)與F(m)不同的概率為99%，基本上在Step2中即可確定獲勝者，而計算成交價時拍賣中心與獲勝者之間的交互次數小于或等于，本身就是一個較小的數，在效率計算時可以忽略，所以該方案的計算復雜度()比一般協議的效率高。

下面給出本文協議與其他協議效率和安全性的比較情況。

文獻[1]設計的方案計算復雜度為(2)(表示其他方案中給定的競拍價空間的長度，表示競拍者的數目)，與其他方案相比效率低。至于安全性方面，方案中的標價信息在競拍者之間共享，獲勝者和成交價由競拍者聯合決定，而不依賴于第三方，最后的成交價只有獲勝者和賣方知道，能夠在任何勾結的情況下保證獲勝者競拍價的秘密性。雖然該方案在安全性較高，但是效率低下。

文獻[8]設計的可達到完全隱私的密封電子拍賣方案的計算復雜度為()(表示其他方案中給定的競拍價空間的長度，表示競拍者的數目)，效率較低。安全性類似于Brandt方案，獲勝者和成交價由競拍者聯合決定，最后成交價只有獲勝者和賣方知道，每個競拍者僅知道自己是否獲勝，達到保護競拍者隱私的目的。

文獻[9]設計的基于不可信第三方的電子拍賣方案的計算復雜度為()(表示競拍者的數目)，效率較前2種方案高。該方案中結合Bit承諾與盲簽名技術，實現了密封式電子拍賣的安全性要求，并可抵御多種合謀攻擊行為。該方案能滿足密封式拍賣的要求，但是在拍賣過程中，競拍者可能需要多次出價，違背了競拍者的本意，而在拍賣結束后，中標者的所有信息都是由中標者自己公布，存在一定程度的不可信性，方案中用到了Bit承諾與盲簽名技術等技術，協議較復雜。

本文設計的密封式電子拍賣方案的計算復雜度為() (表示競拍者的數目)，方案中利用不可信的拍賣中心進行成交價的計算，競拍結束后，只有成交價公開，其余競拍價在任何勾結下都是保密的，滿足密封式拍賣對安全性的要求。本文方案設計思想簡單，而且效率較高。同時，本文設計的電子拍賣方案不僅適用于第一價位的電子拍賣，也同時適用于其他方式的電子拍賣。例如，如果是第二價位的電子拍賣，只需在協議的第2步中選出U排序后的僅次于最大值的第二大值作為，再按協議的順序進行，同樣可產生出成交價及獲勝者。綜上所述，綜合協議的效率、安全性和同一性，本文方案可以適用于各類電子拍賣。

5 結束語

本文設計了一個簡單高效的第一價位密封式電子拍賣方案，該方案是基于一個不可信的第三方，其安全性體現在競拍者身份的隱私性、競拍價的秘密性以及結果的正確性。結果證明，在拍賣結束后，只有成交價公開，其余競拍價都未泄露，競拍者注冊后可使用數字簽名技術保證協議的不可偽造性、抗重放攻擊性和不可否認性，該方案還滿足匿名性、保密性和高效性，并且其效率較一般電子拍賣方案的效率要高，但其不能公開驗證成交價，而是由拍賣中心計算和公布，后續工作將從可公開驗證成交價這個方面進行研究。

[1] Brandt F. Fully Private Auctions in a Constant Number of Rounds[C]//Proc. of the 7th Annual Conference on Financial Cryptography. Munich, Germany: [s. n.], 2003: 223-238.

[2] 陳曉峰, 張方國, 王育民. 一種改進的密封式標價電子拍賣協議[J]. 電子與信息學報, 2002, 24(7): 997-999.

[3] 楊加喜, 王育民. 一種安全高效的M+1電子拍賣[J]. 網絡安全技術與應用, 2006, (11): 87-88.

[4] 王曉敏. 基于環簽名的電子拍賣方案[J]. 電腦知識與技術, 2011, 7(14): 3422-3423.

[5] 秦 波, 秦 慧, 王尚平. 一種保護標價安全的電子拍賣方案[J]. 計算機研究與發展, 2006, 43(1): 28-32.

[6] 伍前紅, 姜正濤, 袁素春. 一個具有最小泄漏的可公開驗證M+1電子拍賣[J]. 通信學報, 2005, 26(1): 12-16.

[7] 周 然, 黃根勛, 魏福山, 等. 基于ElGamal公鑰密碼體制的電子拍賣協議[J]. 計算機工程, 2007, 33(4): 121-124.

[8] 張京良, 馬麗珍, 王育民, 等. 可達到完全隱私的密封電子拍賣方案[J]. 通信學報, 2007, 28(11A): 186-189.

[9] 曹 剛. 基于不可信第三方的電子拍賣方案[J]. 計算機工程, 2010, 36(20): 140-141, 144.

[10] Lee Cheng-Chi, Ho Pi-Fang, Hwang Min-Shiang. A Secure E-auction Scheme Based on Group Signatures[J]. Information Systems Frontiers, 2009, 11(3): 335-343.

[11] 楊加喜, 李用江, 王育民. 一種新的基于Hash鏈的電子拍賣[J]. 計算機工程, 2007, 33(19): 99-100.

[12] 李順東, 戴一奇, 游啟友. 姚氏百萬富翁問題的高效解決方案[J]. 電子學報, 2005, 33(5): 769-773.

[13] 曲 娜, 杜洪軍, 顏 達, 等. ElGamal數字簽名算法的一種變形[J]. 吉林大學學報: 信息科學版, 2009, 27(6): 590- 594.

編輯 陸燕菲

A Simple and Efficient Sealed-bid Electronic Auction Scheme

CHENG Wen-juan, DONG Ying-ying, HAN Jun-guang

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

Most of the electronic auction schemes are assumed the existence of a trusted third party, which makes the security of the electronic auction decreased. Aiming at the problem, this paper proposes a sealed-bid electronic auction scheme based on an untrusted third party. It uses the digital signature technique to verify the identity of the bidder and ensure the privacy of the bidder’s identification. In calculating the transaction price, based on the intractability of the discrete logarithm, it encrypts and packages the binary length of the auction price to ensure the secrecy and accuracy of the results of auction price. Analysis results show that the scheme is simple and has high security, and the computational efficiency relative to most of the existing electronic auction scheme has greatly improved.

e-commerce; sealed auction; anonymity; bid price confidentiality; digital signature; discrete logarithm problem

1000-3428(2014)03-0171-04

A

TP309.07

國家自然科學基金資助項目(51274078)；教育部人文社會科學科研基金資助項目“基于SMC的電子商務安全性研究”(09YJA630029)。

程文娟(1970－)，女，副教授，主研方向：信息安全，電子商務；董瑩瑩、韓俊光，碩士研究生。

2013-02-28

2013-04-22 E-mail：cheng@ah.edu.cn

10.3969/j.issn.1000-3428.2014.03.035