孫培勇，劉憶寧，李亞軍

桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林 541004

一種公開(kāi)可驗(yàn)證的安全電子彩票協(xié)議

孫培勇，劉憶寧，李亞軍

桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，廣西 桂林 541004

1 引言

由于網(wǎng)絡(luò)方便高效的特點(diǎn)，其應(yīng)用范圍越來(lái)越廣泛，人們也設(shè)想用電子彩票代替?zhèn)鹘y(tǒng)彩票[1-2]，使其具有更廣泛的參與性。1998年，Goldschlag和Stubblebine提出了一種應(yīng)用延遲函數(shù)來(lái)實(shí)現(xiàn)可驗(yàn)證的電子彩票方案[3]，并指出電子彩票方案應(yīng)該滿足以下三個(gè)性質(zhì)：（1）公平性，每一張彩票都有相同的獲獎(jiǎng)機(jī)會(huì)；（2）公開(kāi)可驗(yàn)證，結(jié)束后每個(gè)人都可以計(jì)算獲獎(jiǎng)數(shù)字，并且可以驗(yàn)證彩票的真實(shí)性；（3）封閉性，獲獎(jiǎng)數(shù)字的產(chǎn)生僅依賴于所銷售的彩票數(shù)據(jù)而定，而不依賴可信任第三方所提供的信息。

2009年，Lee與Chang提出了t-out-of-n的電子彩票方案[4]，隨后Gray和Sheedy分析指出Lee-Chang方案存在安全漏洞[5]，但是并沒(méi)有給出一個(gè)系統(tǒng)的解決方案。他們希望能夠有一種可公開(kāi)驗(yàn)證，并且不需要可信任第三方的電子彩票方案。安全多方計(jì)算作為密碼學(xué)上一種重要的方法[6]，應(yīng)用十分廣泛，尤其在密鑰共享方面經(jīng)常使用[7-9]。本文給出的安全電子彩票協(xié)議，基于安全多方計(jì)算的原理實(shí)現(xiàn)對(duì)隨機(jī)函數(shù)及獲獎(jiǎng)數(shù)字公正性的驗(yàn)證，其過(guò)程不需要可信任第三方的參與。

2 Lee-Chang方案

Lee-Chang電子彩票的參與者主要包括：彩票發(fā)行者（LA）、購(gòu)買者（Player）、認(rèn)證中心（CA）和銀行（B）；方案包括準(zhǔn)備階段、銷售階段、搖獎(jiǎng)階段、領(lǐng)獎(jiǎng)階段。

2.1 準(zhǔn)備階段

步驟1LA在公告板上公布n個(gè)彩票數(shù)字，a1，a2，…，an，并選取n個(gè)互素的數(shù)，d1，d2，…，dn，其中di＞ai，i=1，2，…，n。

步驟3LA計(jì)算，其中(e，N)是LA的公鑰，N是兩個(gè)大素?cái)?shù)的乘積，ed=1mod?(N)。LA公布(a1，D1)，(a2，D2)，…，(an，Dn)。

2.2 銷售階段

Alice通過(guò)以下步驟購(gòu)買彩票：

步驟1Alice從(ai，Di)(i=1，2，…，n)中選取t對(duì)，記為(a′j，D′j)，j=1，2，…，t。

步驟2對(duì)于(′)，Alice選取隨機(jī)數(shù)rj，計(jì)算，以及PKLA(α1,α2,…,αt,rA1,rA2,Ecash)，其中PKLA是用LA的公鑰進(jìn)行加密的算法，rA1，rA2是隨機(jī)數(shù)。Alice將PKLA(α1，α2，…，αt，rA1，rA2，Ecash)發(fā)送給LA。

步驟3LA收到Alice的消息后解密，并檢查Ecash是否有效。如果有效，LA對(duì)收到的消息進(jìn)行簽名，即

步驟4LA計(jì)算Countf=Countf-1+rA1mod f，其中f是至今已經(jīng)售出的彩票的張數(shù)。然后，LA在公告板上公布(Countf，f)，并且生成。最后，LA將彩票發(fā)送給Alice。 (kf，Countf，f)保存在LA的數(shù)據(jù)庫(kù)中，Kf是LA和Alice之間的對(duì)稱密鑰。

步驟5Alice收到彩票后解密，并對(duì)比所得到的Countf與公告板上是否一致。

2.3 搖獎(jiǎng)階段

假設(shè)最后結(jié)果得到Countf=Cr，購(gòu)票時(shí)間結(jié)束后，LA按下述步驟搖獎(jiǎng)：

步驟1首先計(jì)算w=Countfmodn，其中n是彩票數(shù)字的個(gè)數(shù)。

步驟2LA然后將種子w輸入隨機(jī)函數(shù)得到CW，Ran(w)=CW={cw1，cw2，…，cwt}。

步驟3LA公布獲獎(jiǎng)號(hào)碼結(jié)果CW。

2.4 領(lǐng)獎(jiǎng)階段

假設(shè)Alice所選取的t個(gè)數(shù)字與CW相等，成為中獎(jiǎng)?wù)?，她需要提交證據(jù)證明自己是獲獎(jiǎng)?wù)摺?/p>

步驟1Alice發(fā)送給LA。

步驟2LA計(jì)算從而得到LTf和，LA根據(jù)(Countf，f)找到密鑰kf，解密LTf。

步驟3LA用解密盲簽名β1,β2,…,βt，得到{d′1,d′2,…,d′t}，并計(jì)算

如果{b1，b2，…，bt}和CW相同，LA確信Alice是獲獎(jiǎng)?wù)摺?/p>

Lee-Chang方案漏洞分析：

（1）由2.3節(jié)搖獎(jiǎng)階段可知，種子w是由Countf模n得到的，因此中獎(jiǎng)號(hào)碼Ran(w)=CW={cw1，cw2，…，cwt}最多有n種可能性，即Ran(0)，Ran(1)，…，Ran(n-1)。而n是彩票數(shù)字的個(gè)數(shù)，所以當(dāng)n比較小時(shí)，購(gòu)買者就可以通過(guò)購(gòu)買所有可能中獎(jiǎng)號(hào)碼Ran(0)，Ran(1)，…，Ran(n-1)，這樣必然有一張會(huì)中獎(jiǎng)。例如當(dāng)n=100時(shí)，購(gòu)買者就可以購(gòu)買100張彩票，數(shù)字分別為Ran(0)，Ran(1)，…，Ran(99)，這樣就保證了自己中獎(jiǎng)。

（2）最后一個(gè)購(gòu)買者E可以與LA合謀預(yù)測(cè)w，從而預(yù)測(cè)中獎(jiǎng)號(hào)碼，然后購(gòu)買。假設(shè)平均購(gòu)買1張票的時(shí)間為t，購(gòu)買終止時(shí)間為Tp。在(Tp-t)時(shí)刻時(shí)（即平均只能夠賣出1張票時(shí)），設(shè)此時(shí)已經(jīng)賣出f-1張票，E和LA進(jìn)行如下攻擊：LA負(fù)責(zé)干預(yù)此時(shí)其他購(gòu)票者不能購(gòu)票成功（例如通過(guò)拖延計(jì)算等手段），E用事前已經(jīng)準(zhǔn)備好的，計(jì)算然后E按照進(jìn)行購(gòu)票，并且在購(gòu)票階段的步驟2中，向LA傳遞的數(shù)據(jù)中令rA1=。從而保證了Countf=， w=′，最終有中獎(jiǎng)號(hào)碼

（3）對(duì)于中獎(jiǎng)?wù)叩暮戏ㄐ?，除了LA之外其他人無(wú)法驗(yàn)證，而且在領(lǐng)獎(jiǎng)階段只有LA與中獎(jiǎng)?wù)邇扇藚⑴c，使得LA有可能與其中一個(gè)購(gòu)票者合謀作弊。假設(shè)LA與購(gòu)買者A合謀，從購(gòu)票階段可知，其他人知道關(guān)于A的信息只有公告板上公布的(CountfA，fA)。而(CountfA，fA)的值與A購(gòu)買彩票時(shí)選擇的數(shù)字無(wú)關(guān)，只與購(gòu)票階段選擇的隨機(jī)數(shù)rA1和購(gòu)票的次序有關(guān)。因此，當(dāng)A原來(lái)購(gòu)買的票沒(méi)有中獎(jiǎng)時(shí)，LA和A可以合謀將A原來(lái)選擇的彩票數(shù)字修改為中獎(jiǎng)號(hào)碼，但是rA1和fA不變，并由LA簽名，此時(shí)其他人不能從公告板上的(CountfA，fA)判斷出A的票已經(jīng)修改。并且中獎(jiǎng)號(hào)碼不會(huì)因?yàn)锳選擇的彩票數(shù)字改變而改變，因?yàn)榉N子w只與A的CountfA有關(guān)，與A選擇的彩票數(shù)字無(wú)關(guān)。

3 具有可驗(yàn)證公平性的n中選t的安全電子彩票方案

本文新的方案仍分四個(gè)階段：準(zhǔn)備階段、銷售階段、搖獎(jiǎng)階段、領(lǐng)獎(jiǎng)階段。Lee-Chang方案中原有的符號(hào)及標(biāo)記在下文中仍沿用，增加新的符號(hào)：計(jì)算中心（CC，僅承擔(dān)計(jì)算功能，不具有可信任第三方的職責(zé)）。

3.1 準(zhǔn)備階段

CC公布彩票數(shù)字所在的范圍域Zp（p為素?cái)?shù)）。

3.2 銷售階段

步驟1Alice選取兩個(gè)大素?cái)?shù)pi和qi，并計(jì)算Ni=piqi，將(ei，Ni)和di分別作為自己的公鑰和私鑰。

步驟2Alice選擇t個(gè)數(shù)bi1，bi2，…，bit∈Zn作為自己所買彩票的數(shù)字，記為Ai={bi1，bi2，…，bit}。

步驟3Alice計(jì)算，并計(jì)算hi=Hash(IDi||Ai)，其中ei和IDi分別是Alice的公鑰和身份信息。

步驟4Alice將(，hi，ei)發(fā)送給計(jì)算中心CC。

步驟5CC收到(，hi，ei)后，進(jìn)行數(shù)字簽名Li= sign(Aeii，hi，ei，mi，Ti)，其中mi為當(dāng)前賣出的彩票數(shù)量，Ti為timestamp。CC然后將Li=sign(，hi，ei，mi，Ti)發(fā)送給Alice，并將(，hi，ei，mi，Ti)在公告板上公布。

步驟6Alice在收到Li=sign(，hi，ei，mi，Ti)后，對(duì)照公告板上的信息，看是否一致，若不一致通過(guò)出示Li= sign(，hi，ei，mi，Ti)要求CC更正。

3.3 搖獎(jiǎng)階段

銷售時(shí)間截止后，假設(shè)最后一共賣出M張票，那么對(duì)于每一張賣出的票都有對(duì)應(yīng)的數(shù)對(duì)(,hi)其中i=1，2，…，M，然后CC按照如下步驟生成隨機(jī)函數(shù)以及獲獎(jiǎng)數(shù)字。

步驟2CC選取W=(a0，a1，…，at-1)作為中獎(jiǎng)數(shù)字，即a0，a1，…，aM-1前t位（注：如果出現(xiàn)t＞M的情況，可將a0，a1，…，aM-1循環(huán)使用，即截取a0，a1，…，aM-1，a0，a1，…，aM-1，…的前t位）。

步驟3CC公布中獎(jiǎng)數(shù)字。

3.4 領(lǐng)獎(jiǎng)階段

假設(shè)Alice贏得了彩票，按以下步驟兌獎(jiǎng)：

步驟1Alice發(fā)送Li=sign(，hi，ei，mi，Ti)，di，?(N)給CC。

步驟2CC在收到Alice發(fā)的信息后，做如下工作：

（1）對(duì)照Li=sign(，hi，ei，mi，Ti)是否與所公布的(，hi，ei，mi，Ti)一致；

（2）計(jì)算Wei看是否等于；

步驟3CC經(jīng)過(guò)以上驗(yàn)證，若都成立，則確信Alice為中獎(jiǎng)?wù)摺?/p>

步驟4CC公布Li，di，?(N)，使所有人都可驗(yàn)證獲獎(jiǎng)?wù)叩恼鎮(zhèn)巍?/p>

步驟5CC給Alice獎(jiǎng)金。

4 本文方案分析

主要分析方案具有的安全性、公平性、可驗(yàn)證性，其他性質(zhì)已經(jīng)在Lee-Chang方案中得到了證明。

（1）安全性

定理1假設(shè)在實(shí)際購(gòu)買者中沒(méi)人中獎(jiǎng)，而此時(shí)攻擊者P試圖偽造獲獎(jiǎng)彩票以獲取獎(jiǎng)金，這種攻擊不可能成功。

證明首先因?yàn)檎麄€(gè)過(guò)程都是公開(kāi)的，所有賣出去的彩票(，hi，ei，mi，Ti)都在公告板上公布，每個(gè)人都可以驗(yàn)證是存在等于；并且在攻擊者P公布自己中獎(jiǎng)之后，所有人都可以驗(yàn)證P的(，hi)是否在多項(xiàng)式上，這樣必然發(fā)現(xiàn)P是偽造者。

定理2假設(shè)攻擊者P冒充獲獎(jiǎng)?wù)逜lice領(lǐng)取獎(jiǎng)金，也必然失敗。

證明因?yàn)楂@獎(jiǎng)數(shù)字公布之后，獲獎(jiǎng)?wù)咝枰l(fā)送（Li，di，φ(N)）給CC，而di是Alice的私鑰，攻擊者P無(wú)法獲知。假設(shè)在Alice發(fā)送自己的信息給CC的過(guò)程中，信息被P截取，Alice最終仍然可以通過(guò)出示IDi以驗(yàn)證hi=Hash(IDi||Ai)，這樣必然能發(fā)現(xiàn)P是冒充者。

（2）公平性

定理3在彩票銷售結(jié)束前，任何人無(wú)法預(yù)測(cè)中獎(jiǎng)數(shù)字。

證明中獎(jiǎng)數(shù)字是由所有賣出的彩票對(duì)應(yīng)的(，hi)來(lái)構(gòu)造Zp上插值多項(xiàng)式得到的，該多項(xiàng)式由全部彩票數(shù)據(jù)決定，所有參與者具有同等的權(quán)值，中獎(jiǎng)號(hào)碼會(huì)根據(jù)購(gòu)買者所選數(shù)字的改變而改變。

定理4賣票結(jié)束后，任何人不能修改所買彩票的數(shù)值。

證明首先，每個(gè)人買過(guò)彩票之后，其對(duì)應(yīng)的數(shù)據(jù)被公布，整個(gè)過(guò)程是公開(kāi)的，而且如果某人改變了自己的彩票值以試圖獲得獎(jiǎng)金，那么其他人可以通過(guò)對(duì)照公告板上的值發(fā)現(xiàn)他的行為，而且在他修改過(guò)之后，其他參與者可以驗(yàn)證插值多項(xiàng)式f(x)是否通過(guò)，hi)，即f()=hi是否成立來(lái)判斷彩票是否被修改。

（3）可驗(yàn)證性

定理5每個(gè)人可以驗(yàn)證隨機(jī)函數(shù)是不是隨機(jī)生成的，從而驗(yàn)證獲獎(jiǎng)數(shù)字生成的隨機(jī)性。

證明買票者可以通過(guò)公告板上的信息獨(dú)立計(jì)算f(x)，并獨(dú)立驗(yàn)證f()=hi是否成立，不需要可信任第三方及其他人的協(xié)議，從而判斷中獎(jiǎng)數(shù)字是否公平公正。

定理6中獎(jiǎng)?wù)呖梢员还婒?yàn)證其中獎(jiǎng)事實(shí)。

證明假設(shè)Alice中獎(jiǎng)，所有人可能通過(guò)檢驗(yàn)是否成立。是Alice買票時(shí)在公告板上公布的信息；并且在CC公布過(guò)Alice的(Li，di，?(N))后，其他人可以通過(guò)Alice的私鑰di驗(yàn)證看是否等于W=(a0，a1，…，at-1)。

5 方案對(duì)比

通過(guò)Lee-Chang方案的漏洞分析和本文方案的安全性分析，可以知道本文新方案克服了Lee-Chang舊方案的不足：

（1）對(duì)于原方案的第一個(gè)漏洞，即種子w是由Countf模n得到的，導(dǎo)致中獎(jiǎng)號(hào)碼Ran(w)=CW={cw1,cw2,…,cwt}最多有n種可能性，當(dāng)n較小時(shí)可以被窮舉攻擊。但是在本文方案中不存在這一問(wèn)題，該方案中的隨機(jī)函數(shù)由每位購(gòu)買者共同生成，每一次的隨機(jī)函數(shù)不一定相同，與每次所有購(gòu)買者的彩票值有關(guān)，從而中獎(jiǎng)號(hào)碼不會(huì)受w范圍和固定的隨機(jī)函數(shù)Ran(*)的影響。

（2）本文方案克服了原方案的第二漏洞，任何人不能預(yù)測(cè)中獎(jiǎng)號(hào)碼，包括最后一個(gè)購(gòu)買者也不能達(dá)到預(yù)測(cè)的目的。假設(shè)最后一名購(gòu)買者E通過(guò)前面購(gòu)買者的信息預(yù)測(cè)中獎(jiǎng)號(hào)碼，也必然失敗。因?yàn)橹歇?jiǎng)號(hào)碼是由所有彩票信息公共構(gòu)造多項(xiàng)式后得到的，當(dāng)E購(gòu)買預(yù)測(cè)的號(hào)碼后，計(jì)算出來(lái)的多項(xiàng)式也隨之改變，從而中獎(jiǎng)號(hào)碼也和預(yù)測(cè)的不同。

6 總結(jié)

本文方案的最大特點(diǎn)就是整個(gè)過(guò)程是公開(kāi)的，并且通過(guò)運(yùn)用安全多方計(jì)算的思想，實(shí)現(xiàn)了相互驗(yàn)證，起到了相互監(jiān)督的作用，以防止某方作弊。由于彩票活動(dòng)涉及金額巨大，所以在公平公開(kāi)的同時(shí)，其安全性至關(guān)重要。本文方案在支付購(gòu)買彩票資金和獎(jiǎng)金的發(fā)送方面沒(méi)有進(jìn)行闡述，今后有待于進(jìn)一步完善。

[1]Chaum D.Untraceable electronic mail，return addresses and digital pseudonyms[J].Communications of the ACM，1981，24（2）：84-88.

[2]Cramer R，F(xiàn)ranklin M，Schoenmakers B.Multi-authority secretballotelectionswithlinearwork[C]//Proceedingsofthe EUROCRYPT’96.Berlin：Springer-Verlag，1996，1070：72-83.

[3]Goldschlag D M，Stubblebine S G.Publicly variable lotteries：applicationsofdelayingfunctions[C]//Proceedingsofthe Financial Crypto 98，1998，1465：214-226.

[4]Lee J S，Chang C C.Design of electronic t-out-of-n lotteries on the Internet[J].Computer Standards and Interfaces，2009，31（2）：395-400.

[5]Gray D，Sheedy G.The security of Lee and Chang’s t-out-of-n lottery protocol[EB/OL].[2011-10-01].http：//www.computing.dcu. ie/wpapers/2009/0109.pdf.

[6]Du W，Atallah M J.Secure multi-party computation problems andtheirapplications：areviewandopenproblems[C]// Proceedings of the 2001 Workshop on New Security Paradigms，Cloudcroft，New Mexico，September 10-13，2001.

[7]Harn L，Lin C.Authenticated group key transfer protocol based on secret sharing[J].IEEE Transactions on Computers，2010，59（6）：842-846.

[8]Tzeng W G.A secure fault-tolerant conference-key agreement protocol[J].IEEE Transactions on Computers，2002，51（4）.

[9]Kim W H，Ryu E K，Im J Y，et al.New conference key agreementprotocolwithuseranonymity[J].ComputerStandards and Interfaces，2005，27（2）：185-190.

SUN Peiyong,LIU Yining,LI Yajun

School of Mathematics and Computing Science,Guilin University of Electronic Technology,Guilin,Guangxi 541004,China

In 2009,based on Chinese remainder theorem and blind signature,Lee and Chang proposed a electronic lottery protocol,but this protocol does not satisfy the requirement of fairness and verification.This paper proposes a electronic lottery protocol based on multi-party computation,and the winning numbers is generated by all the players.The improvement prevents dishonest participant from forging lottery ticket and makes the scheme public verification.

electronic lottery;multi-party computation;random function;public verification

2009年，Lee和Chang提出了基于中國(guó)剩余定理和盲簽名的電子彩票方案，但其方案不滿足公平性和公開(kāi)可驗(yàn)證性。給出了一種基于安全多方計(jì)算的電子彩票協(xié)議，中獎(jiǎng)號(hào)碼由所有參與者共同產(chǎn)生，可防止合謀造假，并滿足廣泛的可驗(yàn)證性。

電子彩票；安全多方計(jì)算；隨機(jī)函數(shù)；公開(kāi)可驗(yàn)證性

A

TP309

10.3778/j.issn.1002-8331.1111-0023

SUN Peiyong,LIU Yining,LI Yajun.Public verifiable security electronic lottery protocol.Computer Engineering and Applications,2013,49（13）：68-70.

廣西教育廳基金重點(diǎn)項(xiàng)目（No.201012MS081）；桂林電子科技大學(xué)科研基金（No.UF08014Y）。

孫培勇（1986—），男，碩士生，研究方向：信息安全；劉憶寧（1973—），男，博士，副教授，研究方向：應(yīng)用密碼學(xué)與信息安全；李亞軍（1989—），女，碩士生。E-mail：ynliu@guet.edu.cn

2011-11-07

2012-01-02

1002-8331（2013）13-0068-03

CNKI出版日期：2012-04-25http://www.cnki.net/kcms/detail/11.2127.TP.20120425.1723.096.html