本文研究了英式電子拍賣的安全協議，給出一個安全電子拍賣方案。該方案實現了競拍者身份的匿名性、獲勝競拍者的不可否認性、可公開驗證性、競拍者不可偽裝性、可跟蹤同一拍賣中某競拍者的投標以及某個競拍者在不同拍賣中不可關聯性等問題。本文的工作重點是引入了可信第三方并利用知識證實簽名來解決其它協議中撤消競拍者的問題，可簡單地撤消某個競拍者并保證拍賣的高效率。

1 引 言
拍賣是起源于對古董珍品等沒有固定價格的商品而進行一種交易活動。隨著互聯網的迅速發展，網上電子商務活動的日益增多，電子拍賣交易也在Internet網上快速地開展起來，也出現了Yahoo 拍賣[1]等電子拍賣系統。目前電子拍賣主要有以下三種形式：（1）英式拍賣，是最普遍的一種交易形式。用戶競出他們樂意出的最高價，交易期限一到，交易也同時停止，物品將賣給出價最高者。（2）最高價秘密投標，買主在競拍開始后將標書密封形式投標，在賣家公布投標結束后打開標書，由出價最高者成交。（3）最二高價秘密投標，也是一種密封投標方式，不同之處在于最高出價者是以第二最高出價者所出價格買走交易品。

電子拍賣系統的發展也提出許多安全方面的問題，本文研究了英式電子拍賣協議的安全問題，給出一個電子拍賣的安全協議，工作重點是引入了可信第三方的并利用知識證實簽名解決了撤消競拍者和效率低的問題。本文方案可簡單有效地撤消競拍者，從而保證了拍賣的高效率。

本文的結構安排如下：第 2節簡要介紹了電子拍賣的基本協議、應有特性以及已有的相關工作；第 3節通過可信第三方的引入基于知識證實簽名設計了一個高效地可撤消競拍者的英式電子拍賣方案；第 4節分析了我們方案的安全性和性能分析；第5節作為本文的結束語；

2 電子拍賣的背景及其相關方案

1. 電子拍賣的基本協議：

   電子拍賣協議由以下幾個基本部分組成：

   1. 初始化：拍賣治理者(簡稱AM)選擇系統參數并公布這些參數及有關拍賣品的信息（如拍賣品編號、拍賣時間等）；
   2. 競拍者注冊：每個競拍者發送他的公鑰給AM進行注冊；
   3. 拍賣預計算：AM為此次拍賣計算協議中所需數據，競拍者可以下載這些公開數據；
   4. 拍賣：競拍者計算他的拍賣密鑰并且投標出價；
   5. 拍賣結束：公開獲勝競拍者，AM通過計算得到贏家的身份及他的出價，而其它出價保密，任何人都能公開地驗證贏家的投標出價。
2. 電子拍賣系統應具有的特性：

   在電子拍賣過程中要保護競拍者的匿名性及競拍者的投標信息，任何人包括權威機構都無法單獨地獲得競拍者的身份及其投標信息。拍賣結束后只公開贏家的身份及最高出價，任何人都能驗證拍賣結果的有效性。電子拍賣系統應有特性：

   1. 競拍者的匿名性：即使在拍賣結果公開后，包括可信權威機構的任何人都不能獲知競拍失敗人的身份及其投標出價;
   2. 不可抵賴性：獲勝競拍者不能否認其已經提交的最高出價，而且可以確切地獲得的獲勝競拍者身份。
   3. 公開驗證性：任何人都能公開驗證獲勝競勝者有效性，并能驗證獲得獲勝競拍者是所有競拍者中的最高出價方。
   4. 不可欺騙性：任何人都不能偽裝某個已注冊的競拍者進行競價；
   5. 協議健壯性：即使競拍者提交一個無效的投標，拍賣過程也不會受到影響；
   6. 拍賣的效率：在英式電子拍賣中拍賣的效率是非常重要的，因為競拍者不斷地實時地出價，因此英式電子拍賣協議主要是提高拍賣的效率，拍賣過程的驗證投標書及撤消競拍者的計算量和通信量應適合實際使用。
3. 相關電子拍賣方案

   目前大部分的電子拍賣方案是基于群簽名方案[2-4]構造的，K . Nguyen和J. Traore所設計的英式電子拍賣方案[5]（簡稱NT拍賣方案）就是這樣的一個典型方案，這個方案主要實現了競拍者的匿名性。但NT拍賣方案同時具有了與群簽名方案相似的缺陷，首先是群簽名是一個復雜簽名生成和簽名驗證的過程，需要大量的模乘運算，同樣NT拍賣過程經常需要生成簽名、驗證簽名和驗證投標書的有效性，這是嚴重的效率問題。其次NT方案的第二缺陷是很難撤消一個競拍者，拍賣初始化時競拍者的成員證書已經被分發，而在拍賣過程中撤消競拍者是較頻繁的，如競拍者想要撤出拍賣或拍賣治理者想要取消某個競拍者的競拍資格，那么所有競拍者的證書不得不重新分發，將嚴重影響拍賣的進行。文獻[8，9]實現了一個可撤消成員的群簽名方案，然而在英式電子拍賣協議中頻繁撤消競拍人的情況下使用這兩個方案的效率是極低的。針對基于群簽名現有方案的缺點，我們引入可信第三方來構造一個新的英式電子拍賣方案，該方案有著簡單的拍賣過程和驗證過程，大大地減少了拍賣過程及投標書驗證所需的計算量和通信量，提高了拍賣效率。而且撤消競拍者是輕易且高效地。

3 高效地可撤消競拍者的英式電子拍賣方案
我們基于離散對數的知識證實簽名設計了高效地可撤消競拍者的英式電子拍賣方案，方案的要害點是引入可信第三方（簡稱CA），而不是象現有方案使用組簽名方案。本節將具體介紹此方案：

1. 基于離散對數的知識證實簽名

   本方案是基于離散對數密碼技術來描述的，其安全性依靠于離散對數問題（Discrete Logarithm PRoblem）的難解性，離散對數問題定義如下：

   定義1 給定大素數 p 且滿足 p>2⁵¹²，有限域 Zp^* 的生成元 g ，已知 y ∈ Zp*^* ，很難求得整數 x ,使得 g^x =y (mod p)。

   在我們的方案中所使用的盲簽名方案是Camenish和Michels[4]所提出的知識證實的簽名方案。這個知識證實簽名是基于Schnorr簽名方案[10]，若證實者想向驗證者證實他知道h關于底ｇ的離散對數(即ｘ=log _g h)的知識，并用這個離散對數對消息ｍ∈ { 0, 1}^*做簽名，他可以通過以下的協議來實現：

   證實者：隨機選取ｓ∈_RＺq ,計算ｈ₁=ｇ^s,ｃ=Ｈ(ｍ‖ｇ‖ｈ‖ｈ₁)和ｒ=ｓ-ｃｘ modｑ (這里"‖"表示串的連接操作，Ｈ表示無碰撞單向散列函數)，傳送(ｃ,ｒ)給驗證者。

   驗證者：檢驗ｃＨ( ｍ‖ｇ‖ｈ‖ｇ^rｈ^c ) 。

   
   定義2　滿足ｃ=Ｈ( ｍ‖ｇ‖ｈ‖^rｈ^c )的二元組 (ｃ,ｒ)稱為是ｈ關于底ｇ的離散對數的知識，對于消息ｍ∈{ 0, 1}^* 的簽名，記為：ＳＰＫ{αｈ =ｇ^a } (ｍ)。

2. 電子拍賣方案
   1. CA初始化：選擇兩個大素數p、q ，且滿足q > 2¹⁶⁰，p>2⁵¹²，q (p-1) 。定義乘法群Zq^*上的階為ｑ的子群Gq以及Gq的生成元。
   2. 競拍者B_i注冊：
      1. 競拍者B_i 選擇私鑰 ，并計算公鑰為 ；
      2. B_i 發送y_i 給CA，利用知識證實簽名（這里的m_C 是CA公布的消息）向CA證實其知道以g為底的 y_i 的離散對數 x_i，并登記其身份信息；
      3. CA驗證 B_i 所發送的公鑰 y_i 有效的并公開 y_i ；
   3. 拍賣預計算：設有 I 個已注冊競拍者參加拍賣。
      1. 在拍賣開始前CA隨機選取一個隨機數并計算 (mod p) (i=1,…,I) 和g^r ;
      2. 可信第三方CA公開如下參數：{p, q, g}，g^r ，競拍者B_i的公鑰和混亂后的 { } ( i=1,…,I )，而競拍者的身份信息保密。
      3. 競拍者B_i通過驗證 來確認自己是當前拍賣的合法競拍者。因為CA每次拍賣都會重新選擇一個隨機數r，這樣在每次拍賣中每個競拍者都有不同的公開密鑰 。
      4. AM隨機選取一個隨機數 并利用已知的 計算 (mod p)；
      5. AM為每個競拍者B_i 計算拍賣密鑰T_i = ，公布混亂后的{T_i}(i=1,…,I) ， 和當前拍賣物品信息。
      6. 競拍者B_i利用AM公開的 計算T_i = ，并且核實該T_i 是否已經存在于AM所公開的{T_i}(i=1,…,I)中。

      由于每次拍賣都會重新選取隨機數s，每個用戶在每次拍賣中有不同的Ti = （mod p）。除了AM沒有人能知道 和T_i 對應關系，因為 被AM所選取的保密隨機數s隱藏。但AM并不知道y_i 與T_i 的對應關系，因為y_i 被CA所知道的保密隨機數 r 隱藏。所以CA及AM都無法單獨從已經公開的信息中獲得競拍者的身份。由于在每次拍賣都將重新隨機選擇r及s ，所以可以保證在多次拍賣中競拍者身份的不可關聯性。

   4. 拍賣

      當競拍者B_i出價時，他發送如下投標信息( ) 給AM，其中 是T_i 的標識號，m_i 為拍賣品編號與出價； ，V_2i 是競拍者B_i 利用知道的 x_i 的知識對m_i 的簽名， 并由此證實自己是一個合法的競拍者。

      
      AM驗證投標書的知識證實簽名V_2i 來確認標書有效，而且由于{ }(i=1,…,I)的公開，任何人都能夠驗證該投標書。假如驗證不通過，AM 丟掉該非法的投標書。通過驗證知識證實簽名V_2i的有效性，可確認該投標書的發送者B_i 確實擁有私鑰x_i并由此證實自己是一個合法的競拍者。

   5. 拍賣結束：

      假設競拍者 B_k 是拍賣的最終獲勝者，其投標書為( )。為了揭示該獲勝者的身份，AM必須公開證實T_k 與 是相關聯的，以便CA能夠揭示獲勝者身份。AM生成如下的知識證實簽名來證實T_k 與 是相關聯的：

      

      其中m_c 是CA發布的消息。AM公開( )及V_3k ，利用V_2k 和 T_k 可以驗證獲勝投標書的有效性，利用m_k 可知該拍賣品的最高出價。任何人都可以通過驗證V_3k 的有效性來確認T_k 與 是相關聯。可信權威機構CA驗證知識證實簽名V_3k有效性后，CA就能確認T_k 與 是相關聯，并能揭示獲勝者的身份。

   6. 公開獲勝者： CA公開的獲勝者身份，為了向AM證實獲勝者身份屬實，需證實 和 y_k 相關聯的。于是CA生成知識證實簽名V_4k ： ，其中m_a 是AM公布的信息。CA公開 V_4k 、 和 y_k ，那么任何人都能通過驗證簽名 V_4k 的有效性來確認獲勝者身份。拍賣方案示意圖見圖1。

      

4 方案的安全性及性能分析

1. 安全性分析：
   1. 競拍者身份匿名性。包括AM在內的任何人在沒有CA的幫助下都無法從已公開的信息中獲得競拍者的身份信息。即使競拍獲勝者的身份在以前的拍賣中被揭示，他也能匿名地競拍以后的其他拍賣活動。
   2. 不可否認性：CA驗證AM提供的信息有效，并根據這些信息來揭示競拍獲勝者身份。而競拍獲勝者無法否認其已經提交過的獲勝投標。
   3. 公開驗證性：任何人都能驗證投標書的簽名 V_2i , 而且任何人都能通過驗證拍賣密鑰確認一個競拍者是否是有效競拍者。任何人通過檢驗簽名 V_3k 、_V4k 來公開地驗證公開的獲勝者_Bk 身份信息。
   4. 健壯性：AM通過驗證簽名_V2i 不合法性，則拒絕接受該投標書，當然也要拒絕低于當前出價的投標書。
   5. 在多次拍賣中的不可關聯性：由于CA和AM在每次拍賣中選取的隨機數 r 和 s 不同，一個競拍者在每次拍賣中所使用的密鑰也不同，沒有人能將這個競拍者在不同拍賣中的投標書聯系起來。
   6. 同一拍賣中的關聯性：在一次拍賣中任何人能通過某個競拍者在拍賣中簽名所使用相同的 知道他投標次數及出價，但仍不知該競拍者身份。
   7. 不可偽造性：在拍賣中，CA和AM都不能偽造某個競拍者的投標書來出價。假設他們能偽造競拍者 B_i 對進行知識證實簽名 V_2i，那就意味著他們知道以 為底 的離散對數，也就是知道了 x_i ,這相當于求解離散對數問題，因此即使CA和AM共謀也不能偽裝成某個競拍者進行競拍，其他競拍者更無法偽裝成另一個競拍者來投標。
2. 協議性能分析
   1. 一次注冊

      任何競拍者能夠僅一次注冊參加多個拍賣，即使是獲勝競拍者在參與下一輪的拍賣活動時也無需重新注冊，拍賣過程中他的身份匿名性仍能得到保護。

   2. 簡單的可撤消性

      在英式電子拍賣過程中，撤消競拍者是頻繁發生的，如競拍者想要撤出拍賣過程或CA撤消某個欺詐的競拍者。所以要求撤消競拍者是簡單而輕易的，而且當某個競拍者被取消競拍資格后，他的拍賣記錄仍應該是保密的。在我們的方案中，CA只需要刪除該競拍者的相關信息：競拍者的身份信息及其公鑰。而文獻[8，9]所提出的方案在英式電子拍賣協議中頻繁撤消競拍者的情況下的效率是極低的，我們的方案撤消競拍者是很輕易而且高效地。

   3. 計算量與通信量

      
      若用文獻[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