一種新的基于ＥＣＣ的電子拍賣(mài)協(xié)議

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

關(guān)鍵詞：M＋1價(jià)拍賣(mài)； 比特承諾； 可驗(yàn)證秘密共享； 橢圓曲線

中圖分類(lèi)號(hào)：TP309

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2007）09-0115-03

隨著Internet的迅速發(fā)展，各種電子商務(wù)在網(wǎng)絡(luò)中不斷涌現(xiàn)，電子拍賣(mài)作為一種特殊的現(xiàn)貨交易方式，它在網(wǎng)絡(luò)中的實(shí)現(xiàn)有著重要的實(shí)際意義，近年來(lái)得到廣泛的研究[1~6]。

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

M+1價(jià)位拍賣(mài)是一種推廣了的Vickrey拍賣(mài)形式，即要拍賣(mài)M個(gè)單位的同一種物品，M個(gè)出高價(jià)者中標(biāo)，每個(gè)中標(biāo)者購(gòu)買(mǎi)一個(gè)單位，但統(tǒng)一按照未中標(biāo)者中出的最高價(jià)位(M+1價(jià)位)付款。如果令M=1，則為Vickrey拍賣(mài)(出最高價(jià)位者中標(biāo)，中標(biāo)者按次高價(jià)付款)。Wurman等人證明了(M+1)價(jià)拍賣(mài)同Vickrey拍賣(mài)一樣滿(mǎn)足激勵(lì)競(jìng)爭(zhēng)機(jī)制，即投標(biāo)者的最優(yōu)策略為其愿意出的真實(shí)價(jià)。由于中標(biāo)價(jià)是第M+1價(jià)位，即所有未中標(biāo)者的最高價(jià)，每一個(gè)投標(biāo)者按其愿意出的最高價(jià)投標(biāo)增大了其中標(biāo)的機(jī)會(huì)而不必?fù)?dān)心其是否出價(jià)太高。

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

1相關(guān)技術(shù)

1.1基于橢圓曲線密碼體制的可驗(yàn)證門(mén)限秘密共享方案

橢圓曲線密碼的相關(guān)數(shù)學(xué)背景及其原理這里不過(guò)多闡述， 有關(guān)這方面的更詳細(xì)的敘述見(jiàn)文獻(xiàn)[6，7]。

3安全性及效率分析

本方案把投標(biāo)者的身份分為，競(jìng)買(mǎi)者身份和其真實(shí)身份。協(xié)議中，競(jìng)買(mǎi)者身份Bi（可為隨機(jī)數(shù)）是針對(duì)某次拍賣(mài)從注冊(cè)中心獲得的；而投標(biāo)者的真實(shí)身份則一直保密。贏家產(chǎn)生后可從注冊(cè)中心獲得中標(biāo)者的身份描述。公鑰系統(tǒng)和拉格朗日門(mén)限秘密共享體制保證未中標(biāo)者的信息是不會(huì)泄露的，除非作弊的服務(wù)器個(gè)數(shù)大于等于ｔ。方案中成交價(jià)的宣布不會(huì)導(dǎo)致任何投標(biāo)者的個(gè)人信息的泄露，包括M＋1價(jià)位的投標(biāo)人身份。

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

投標(biāo)者投標(biāo)后的不可否認(rèn)性、投標(biāo)價(jià)的保密性以及可公開(kāi)驗(yàn)證性主要依靠承諾打開(kāi)且僅打開(kāi)了ｎ位中的log2n位實(shí)現(xiàn)的。Bit承諾最后僅打開(kāi)了承諾向量中的部分分量而不是整個(gè)承諾向量，既減少了通信量，又保證了中標(biāo)者中標(biāo)的可公開(kāi)驗(yàn)證性以及投標(biāo)者個(gè)人的投標(biāo)信息不被泄露。

參考文獻(xiàn)：

［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]王繼林，高虎明，王育明.一個(gè)安全的M+1 價(jià)位電子拍賣(mài)方案 [Ｊ] .西安電子科技大學(xué)學(xué)報(bào)，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]鄭東，陳克非，谷大武，等. 一種有效的比特承諾方案[Ｊ]. 通信學(xué)報(bào)， 2000， 21(2):78-81.

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

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”