一個基于環簽名的安全密封電子拍賣協議

摘 要：在拍賣過程中如何保護投標者隱私和身份以及防止中標者反悔是設計安全電子拍賣系統的關鍵技術。基于環簽名思想的類群簽名方案及同態公鑰加密體制，設計了一個新的密封投標的電子拍賣協議。所給協議具有如下特點：安全性好，能夠滿足投標者匿名、投標價保密、不可否認性以及不可偽造等密封電子拍賣的所有安全性要求；對可信賴第三方的依賴小；安全性高、步驟簡略。

關鍵詞：密封式電子拍賣；環簽名；同態加密；-隱藏假設

中圖分類號：TP309 文獻標志碼：A 文章編號：1001-3695(2008)08-2441-03

Sealed-bid electronic auction protocol based on ring signature

XIONG Hu，QIN Zhi-guang，LAN Tian

(College of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu610054， China )

Abstract: Electronic auction is one of the basic businesses in electronic commerce. The protection of bidder anonymity and the prevention of bidder default are the keys in the designing of secure electronic auction scheme.This paper proposed fair electronic auction protocol， which was based on the combination of an efficient group signature scheme relying on the ring signature idea and a public-key cryptosystem of the homomorphic encryption. This scheme has the following advantages:It has high quality of security and can satisfy all the secure requirements of sealed-bid auction，namely，bidder anonymity，bid undeniability，bid unforgeability，bid secrecy and bid confidentiality. It requires almost no participation of TTP.It is more efficient and safer than others.

Key words: sealed auction; ring signature; homomorphic encryption;-hiding assumption

電子拍賣是電子商務的一項基本業務，是現實拍賣的電子化。電子拍賣系統按標價是否公開可分為公開式拍賣系統和密封式拍賣系統。開放式拍賣允許多次競標，標價公開。而密封式拍賣要求在規定時間前，每個投標者秘密地提交一個投標價，在規定時間后才能打開投標并按一定的確定性規則選出中標者。目前，網上拍賣系統由于缺乏必要的安全機制等原因，降低了這些系統的可信性。安全的電子拍賣系統應滿足下列安全性需求：a）匿名性。投標參與者不想泄漏自己的身份。b）不可否認性，投標者投標后不能否認其投標。c）不可偽造性。投標者的投標不能被偽造。d）投標價保密。投標者的投標價保密。e）不可跟蹤性。其他參與者無法斷定哪些投標是同一個投標者投的。f）公平性。指投標者地位一樣。

本文的主要貢獻是保證投標者匿名性的密封拍賣。它能夠在任何勾結的情況下保證投標者標價的秘密性，并在注冊服務器和拍賣服務器不合謀的情況下保證投標者身份的匿名性。同時可通過注冊服務器和拍賣服務器聯合對投標者身份進行追蹤，從而防止投標者抵賴。

1 預備知識

1.1 環簽名及其安全性

環簽名的定義由Rivest等人在文獻[1]中給出：某數字簽名的簽名者來自于一個指定的簽名者集合，但驗證人不能指出誰是具體的簽名人。環簽名沒有管理者，沒有相互間的配合。簽名者選取的成員數目越多，則環簽名的匿名性就越好。假定有n個投標者，每一個投標者Bi擁有一個公鑰yi和與之對應的私鑰si。簽名是一個能實現簽名者無條件匿名的簽名方案，它由下述算法組成：

a）簽名sign(·)。一個概率算法在輸入消息m0和n個環成員的公鑰L={y1，y2，…，yn}以及其中的一個成員的私鑰si后，對消息m0產生一個簽名σ=（m0，L，c1，e1…，en）。其中：ci(i=1，2，…，n)作為初始值和結果值根據一定的規則首尾相接呈環狀。

b)驗證verify（·）。一個確定性算法，在輸入（m0，σ）后，若σ為m0的環簽名，則返回true；否則為1。

在文獻[2]中，通過讓管理員和簽名接收者分別產生一個秘密數匿名傳送給簽名者，簽名者利用這些秘密數和自己的一個秘密數產生環簽名的方式實現了環簽名和群簽名思想的折中：環簽名被改造為可控制的匿名簽名，若簽名者進行抵賴，則其身份會被管理員和簽名接收方共同揭示，但管理員權限也受到了限制，他必須與簽名接收方合作才能追蹤簽名者身份。

1.2 同態公鑰加密體制與-隱藏假設

定義1 同態公鑰加密體制。設S為公鑰密碼體制，k為其安全參數，M為消息空間，Ek：{0，1}k×X→C為公開加密函數，Ek(u，x)∈C，u∈{0，1}k為隨機串，C為密文空間；Dk：C→X為秘密的解密函數。其中：X為交換加群；C為交換乘群。對任意的消息x0，x1∈X及隨機串u0，u1∈{0，1}k，存在u使得

Ek(u，x0+x1)=Ek(u1，x1)×Ek(u0，x0)

則稱S為語義安全的同態公鑰加密體制。

定義2 -隱藏假設(-HA)。設p，q是兩個大素數，m=pq，p0是一個較小的素數，m隱藏了p0，即p0｜(m)。

定義3 單向映射λ。{0，1}k′→Z，λ把一個k′比特的數映射到一個k′比特的素數。

2 基于環簽名的安全密封電子拍賣方案

2.1 系統參數

考慮一個基于離散對數的密碼系統，設p、q是兩個大素數，〈g〉為一個生成元為g的Zp的q階子群，假定有n個投標者，第i個用戶Bi的私鑰為si，對應的公鑰yi=gsimod p，Public為一個發布公鑰的公告牌，所有的用戶公鑰都在其上發布。

設RM為注冊服務器，管理上述的密碼系統和公告牌Public，其私鑰為sRM，對應的公鑰為yRM，RM生成并在公告牌上發布同態加密公私密鑰對（ERM，DRM）中的公鑰ERM。設AM為拍賣服務器，它管理每場拍賣的報價是否有效，與RM一起對密封的競價進行比較，并在投標者抵賴時與RM一起揭示投標者的身份。其私鑰為sRM，對應的公鑰為yAM。用{x}yi表示使用yi對消息x進行公鑰加密，用{x}si表示使用si對消息x進行簽名，L={y1，y2，…，yn}為n個環成員的公鑰，SEk()表示某種對稱加密，encode(x，L)=ex=[{x}y1，{x}y2，…，{x}yd]，decode(ex，sk，L)=x={exi}sk。

2.2 方案設計

1）注冊 投標者Bi選擇并記住一個ri，計算pi=grimod p，向AM提交（yi，pi），并向AM證明他知道對應的si和ri。AM在其公告牌上發布以下參數：p、q、g，成員Bi及其對應的（yi，pi）；對稱的加密方案SEk()；一個可公開獲得的hash函數：H：{0，1}→Zq。投標者Bi首先在RM發布的公鑰中任選一些(包括他自己的)公鑰，構成本次簽名的匿名群L={y1，y2…，yd}，與AM建立一個匿名連接(匿名連接的建立可采用mix、洋蔥路由等技術)，然后為對稱加密方案SEk()任選一個密鑰h，將{h，L}yAM發送給AM。AM解密h和L后將{h，L}yRM發送給RM。RM解密h和L，為本次拍賣隨機生成rRM∈Zq，并記錄(h，rRM)，把SEh[{encode(rRM，L)}SRM，{prRM1，prRM2，…，prRMd}SRM]發送給AM；AM為本次拍賣隨機生成rRM∈Zq并記錄(h，rRM)，將SEh［{encode(rAM，L)}SRM，{encode(rRM，L)}SRM]發送給Bi，Bi分別用decode(erAM，sK，L)和分別用decode(erRM，sK，L)解密出rAM和rRM。

2）投標者對投標價進行同態加密 RM生成并發布Δ-通用hash函數H和它的密鑰κ(H：κ×{0，1}→{0，1}k′）。設投標者Bi的競價ai的二進制表示為ai，l，ai，l-l…ai，0。

AM隨機選取ki∈κ、tAi∈{0，1}k′、xi， j，xi，l，vi，j∈X，及v1，j＝v2，j＝…vn，j，生成k′-比特的素數pAi，使λ(tAi)=pAi，并確定mAi∈{0，1}k″。其中:mAi隱藏了pAi，計算δAi，j=Hk(κi，xi，j+vi， j)tAi，并通過匿名連接將該數據發送給Bi。Bi計算yAi，j=ERM(ui，j，xi，j-xi，j+1+ai，jvi，j)，yBi，j=ERM(u′i，j，-ai，jvi，j)。

3）投標者進行匿名簽名以及AM驗證簽名 投標者Bi使用在步驟1)中生成的pi以及分別從AM和RM處獲得的rAM和rRM對消息m0=yAi，j‖yBi，j進行簽名，簽名過程sign(Bi，pi，rAM，rRM)如下所示：

（a）αRZq，ck+1=H(m0，gαk mod p)；（b）for j=k+1，…，d，l，…，k-1，do ejRZq ，and cj+1H(m0，gejj(prAMrRMiyj)cj mod p)；(c)ekα-(rirAMrRM+si)ci mod q；(d)return σ=(h，m0，L，pirAMrRM，c1，e1，…， ed)

投標者Bi將簽名σ和m0=yAi，j‖yBi，j發送給AM。AM通過以下算法計算cj是否構成一個環狀結構判斷簽名是否合法。

a）pirAMrRM檢查。對RM給出的SEh[{encode(rRM，L)}srRM，{p1rRM，p2rRM，…pdrRM}sRM]，找出{p1rRM，p2rRM，…，pdrRM}，計算其中每一項的rAM次方，檢查pirAMrRM是否在其中，如在，執行下一步；否則，拒絕；

b)環檢查。for j=1，2，…，d，cj+1H(m0，gejj(prAMrRMiyj)cj mod p)，ifcd+1=c1 then return “accept” else return “reject”。

4)拍賣結果的計算 AM選擇n個隨機置換π1，π2，…，πn，令imax=1，fori=2，…，n，AM計算zπi，πimax，j=yAπi，j×yBπimax，j，zπimax，πi， j=yAπimax， j×yBπi， j。其中：j∈[0，l-1]，并將kπil、kπimaxl、xπi，l、xπimaxl、zπi，πimax， j、zπimax，πi， j、δAπimax， j、δAπi， j、mAπi、mAπimax發送給RM。

RM令xπi，l=dπi，l，xπimax，l=dπimax，l隨機選取gAπi和gAπimax，對j∈[0，l-1]，計算：(a)dπi j=dπij+l+DRM(zπi，πimax， j)，dπimaxj=dπimaxj+1+DRM(zπimax，πi， j)；(b)qAπi，j=λ(Hk(κπi，dπi， j)δAπi， j)，gAπi， j=CgAπi， j+1)qAπi，j mod mAπi；（c）qAπimax，j=λ(Hk(kπimax，dπimax)δAπimax，j)，gAπimax，j=(gAπimax，j+1)qAπimax， j modmAπimax。

RM選擇rAπi∈ZAmπi，rAπimax∈ZAmπimax，計算hAπi=(gAπi，0)rAπi mod mAπi，hAπimax=(gAπimax，0)rAπimax mod mAπimax，并將它們發送給AM。AM檢驗hAπi是否含有PAπi次方根，(hAπi)φ(mAπi)/pAπi=1 mod mAπi若成立，則aπi>aπimax，令imax=i，i=i+1；否則，AM檢驗hAπimax是否含有pAπimax次方根，若成立，則aπimax>aπi，imax不變，令i=i+1。最后的獲勝方為Bπimax。

3 安全性分析

a）競價的正確性 協議要反復比較Bπi和Bπimax的競價。若aπi＞aπimax，設j是aπi和aπimax由高位起第一個不相等的比特位(即aπi，j=1，aπimaxj=0)，注意到vπi， j=vπimaxj，則當j=l，…，j+1時，有dπi， j，對j，RM得到dπi， j=xπij+vπij及qAπi，j=pAπi，而當j=j-1，…，0時，又有dπij=vπij*+xπij+j*-1j′=j πij′v(aπ”i，j-aπimax，j′)。因此，gAπi，j*必含有pAπi次方，此時hAπi必含有pAπi次方。同理可證aπi＜aπimax的情形。

若RM進行欺騙，他只能從δAπi，j，δAπimax，j處獲得xπi，j、xπimax，j、vπi，j的相關信息，這與H無碰撞性矛盾；而從hAπi，hAπimax獲得信息要知道pAπi，pAπimax，由mAπi、mAπimax得到pAπi、pAπimax與-隱藏假設矛盾，所以RM不能獲得競價信息。若AM進行欺騙，AM只能從yAi，j、yBi，j，獲得競價信息，這與同態公鑰的語義安全性矛盾。

2）投標者不能否認簽名是其所為 RM和AM可以根據h分別提供rRM和rAM，然后可以通過計算L中每個用戶Bi對應的pi的rRMrAM次冪，找出對應pirRMrAM的pi，從而可有RM和AM合作的情況下確定投標者的身份。

3）在無法建立prAMrRMi和pi對應的情況下，上述拍賣方案滿足競價的無條件匿名性 在方案中除了投標者Bi的ei外，其他的ek都是在Zq上隨機選取的。對于固定的m0和PrAMrRMi，e1，e2，…，ed有qd種等可能的取值，而c1完全由m0和e1，e2，…，ed惟一確定。因此，從(c1，e1，e2，…，ed)本身判斷出具體是哪個投標者的簽名是不可能的。在無法建立pirAMrRM和pi對應的情況下，由于簽名呈環狀，即便所有人的私鑰泄露也無法確定具體投標者。

4）pirAMrRM和pi對應關系的建立 只有靠拍賣服務器AM和注冊服務器RM合作才能實現。由于rAM和rRM的隨機性，在不知道rAM和rRM的前提下，直接通過pirAMrRM找到對應的pi是不可能的，因為這必須求解離散對數問題。在尋找prAMrRMi對應的pi上，AM和RM任何一人無法單獨建立prAMrRMi和pi的對應。在RM和AM不勾結的情況下，上述方案可以保證投標者的匿名性。

5）在AM不與偽造者串通的情況下，本拍賣協議方案滿足競價的不可偽造性 一個攻擊者要偽造上述標價，他必須要獲取rAM和rRM，但AM和RM傳送的rAM和rRM只有L中成員才能解密， 而L中的內部攻擊者Bi要偽造Bk的標價，他必須使用Bk對應的pk來簽名。為使簽名中的ci按照規則構成環狀結構，他最終需要知道pk對應的rAM，但在AM不與偽造者串通的情況下，這也是不可能的。

4 結束語

本文在現有電子拍賣方案的基礎上，結合環簽名思想和同態公鑰加密體制設計了保護標價的秘密性和投標者匿名性的第1價位拍賣，并防止了中標者進行抵賴的情況，在重大的商業拍賣中具有重要的應用價值。本方案具有以下特點：a）在任何情況下保證標價的秘密性；b）在注冊服務器(茫然第三方)和拍賣服務器不相互勾結的情況下保證投標者的匿名性；c）而投標價格使用環簽名進行簽名可以保證協議的不可否認性、不可偽造性，且其他投標者具有不可跟蹤性。本方案先使用同態加密對投標價進行加密，然后利用環簽名對投標價進行簽名，思想簡單，用戶易于接受，有較好的應用前景。

參考文獻:

[1] RONALD L R， ADI S， YAEL T. How to leak a secret[C]//Proc of Asiacrypt 2001. [S.l.]: Springer-Verlag， 2001:552-565.

[2] 王繼林， 張鍵紅， 王育民. 基于環簽名思想的一種類群簽名方案[J]. 電子學報， 2004，32(3): 408-410.

[3] 秦靜， 張振峰， 馮登國. 無信息泄漏的比較協議[J]. 軟件學報， 2004，15(3):421-427.

[4]吳可力. 一個基于環簽名的英式電子拍賣協議[J]. 計算機工程與應用， 2006，42(31):219-222.

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

[6] NAOR M，PINKAS B，SUMNER R. Privacy preserving auctions and mechanism design[C]//Proc of ACM Conference on Electronic Commerce.1999:120-127.

[7] HELGER L， ASOKAN N， VALTTERI N. Secure vickrey auctions without threshold trust[C]//Proc of 6th Annual Conf Financial Cryptography. [S.l.]: Springer-Verlag， 2002:87-101.

[8] DAVID H， BURKHARD S.PEER M.The technology for a distributed:auction-based market for peer-to-peer services[C]//Proc of the 40th IEEE International Conference on Communications (ICC 2005). 2005: 1583-1587.

[9]BRANDT F.How to obtain full privacy in auctions[J]. International Journal of Information Security， 2006，5(4):201-216.

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