一種新的基于ＥＣＣ的電子拍賣協議

摘要：利用橢圓曲線離散對數問題的難解性， 給出了基于橢圓曲線密碼體制(elliptic curve cryptosystems)的可驗證、安全、高效、密封的M+1價位電子拍賣方案。除了滿足所有投標者身份匿名、所有投標者的標價保密、所有未中標者的個人信息不會被泄露等安全要求外，還能抗擊惡意投標者對正常拍賣進行的破壞。

關鍵詞：M＋1價拍賣； 比特承諾； 可驗證秘密共享； 橢圓曲線

中圖分類號：TP309

文獻標志碼：A

文章編號：1001-3695（2007）09-0115-03

隨著Internet的迅速發展，各種電子商務在網絡中不斷涌現，電子拍賣作為一種特殊的現貨交易方式，它在網絡中的實現有著重要的實際意義，近年來得到廣泛的研究[1~6]。

常見的拍賣方式大致有四種類型：英式拍賣、荷蘭式拍賣（亦稱減價拍賣）、密封式拍賣、第二價位拍賣(也叫做Vickrey 拍賣)。經濟學家Vickrey 結合英式拍賣與密封式標價拍賣的優點，設計出一種新的拍賣方式——二級價格拍賣[2] 。像密封式最高價拍賣一樣，投標者將標價送給拍賣行，出最高價格者中標，但中標者按出次高價者的價位付款。 第二價位原理支持商品分配最優化，且降低了出價人串通的可能，Vickrey 因此獲得1996 年Nobel 經濟學獎。

M+1價位拍賣是一種推廣了的Vickrey拍賣形式，即要拍賣M個單位的同一種物品，M個出高價者中標，每個中標者購買一個單位，但統一按照未中標者中出的最高價位(M+1價位)付款。如果令M=1，則為Vickrey拍賣(出最高價位者中標，中標者按次高價付款)。Wurman等人證明了(M+1)價拍賣同Vickrey拍賣一樣滿足激勵競爭機制，即投標者的最優策略為其愿意出的真實價。由于中標價是第M+1價位，即所有未中標者的最高價，每一個投標者按其愿意出的最高價投標增大了其中標的機會而不必擔心其是否出價太高。

Kikuchi[3]利用秘密共享技術提出了一個(M+1)價密封電子拍賣方案。該方案中投標者的投標價被表示成一個多項式的次數，但它允許的投標價比拍賣服務器的個數少，因而限制了投標價的取值。另外，任何人均可以提交不正確的標價匿名地破壞拍賣的進行。Suzuki[4]利用同態加密Mix和匹配技術提出了一個(M+1)價密封電子拍賣方案。該方案實現了中標人和中標價的可公開驗證性。但每一個投標者在投標中需要進行k+1次零知識證明，k為允許的投標價取值的個數，因而計算量很大。王繼林等人[5]利用多項式的秘密分享和Ｂｉｔ承諾技術，給出了一個M+1價位電子拍賣方案，但改進方案無法抗擊不按規定方法選取和分發多項式常數項的惡意投標者對拍賣正常進行的破壞。本文在王繼林等人提出的方案基礎上，利用基于橢圓曲線密碼體制的門限秘密共享方案和Ｂｉｔ承諾位，提出了一種可驗證的安全、高效、密封的M＋1價位電子拍賣協議。

1相關技術

1.1基于橢圓曲線密碼體制的可驗證門限秘密共享方案

橢圓曲線密碼的相關數學背景及其原理這里不過多闡述， 有關這方面的更詳細的敘述見文獻[6，7]。

3安全性及效率分析

本方案把投標者的身份分為，競買者身份和其真實身份。協議中，競買者身份Bi（可為隨機數）是針對某次拍賣從注冊中心獲得的；而投標者的真實身份則一直保密。贏家產生后可從注冊中心獲得中標者的身份描述。公鑰系統和拉格朗日門限秘密共享體制保證未中標者的信息是不會泄露的，除非作弊的服務器個數大于等于ｔ。方案中成交價的宣布不會導致任何投標者的個人信息的泄露，包括M＋1價位的投標人身份。

方案中使用了基于橢圓曲線密碼體制的可驗證門限秘密共享體制，可檢驗每個投標者是否正確地進行秘密分享，可檢驗每個投標者是否分享了正確的秘密信息，即被分享的秘密是0 或者是1，而不是其他的元素。從而可抗擊惡意投標者匿名的破壞拍賣的進行。

投標者投標后的不可否認性、投標價的保密性以及可公開驗證性主要依靠承諾打開且僅打開了ｎ位中的log2n位實現的。Bit承諾最后僅打開了承諾向量中的部分分量而不是整個承諾向量，既減少了通信量，又保證了中標者中標的可公開驗證性以及投標者個人的投標信息不被泄露。

參考文獻：

［1］CACHIN C. Efficient private bidding and auctions with an oblivious third party[C]//Proc of the 6th ACM Conference on Computer and Communications Security(CCS)[C].New York:ACM Press， 1999:120-127.

[2]VICKREY W. Counterspeculation， auctions， and competitive sealed tenders [J ]. Journal of Finance，1961，16 (1):8-37.

[3]KIKUCHI H. M+1stprice auction protocol[C]//Proc of the 5th International Conference on Financial Cyrptography. Berlin:SpringerVerlag， 2002:291-298.

[4] ABE M， SUZUKIK. M+1 stprice auction using homomorphic encryption[C]//Porc of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems. London:SpringerVerlag，2002:115-124.

[5]王繼林，高虎明，王育明.一個安全的M+1 價位電子拍賣方案 [Ｊ] .西安電子科技大學學報，2003，30(5):669-672.

[6]MILLER V S. Use of elliptic curve in cryptography[C]//Proc of CRRPTD’85. New York:SpringVerlag， 1986:417-426.

[7]KOBLITZ N. A course in number theory and cryptography[M ]. 2nd ed. Berlin:SpringVerlag， 1994:129-131.

[8]鄭東，陳克非，谷大武，等. 一種有效的比特承諾方案[Ｊ]. 通信學報， 2000， 21(2):78-81.

[9]SCHNEIER B. 應用密碼學[M]. 吳世忠，祝世雄，張文政，等譯.北京:機械工業出版社，2000:21-56.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”