一種公開可驗證的安全電子彩票協(xié)議

孫培勇，劉憶寧，李亞軍

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

一種公開可驗證的安全電子彩票協(xié)議

孫培勇，劉憶寧，李亞軍

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

1 引言

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

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

2 Lee-Chang方案

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

2.1 準(zhǔn)備階段

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

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

2.2 銷售階段

Alice通過以下步驟購買彩票：

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

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

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

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

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

2.3 搖獎階段

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

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

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

步驟3LA公布獲獎號碼結(jié)果CW。

2.4 領(lǐng)獎階段

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

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

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

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

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

Lee-Chang方案漏洞分析：

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

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

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

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

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

3.1 準(zhǔn)備階段

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

3.2 銷售階段

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

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

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

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

步驟5CC收到(，hi，ei)后，進行數(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)后，對照公告板上的信息，看是否一致，若不一致通過出示Li= sign(，hi，ei，mi，Ti)要求CC更正。

3.3 搖獎階段

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

步驟2CC選取W=(a0，a1，…，at-1)作為中獎數(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公布中獎數(shù)字。

3.4 領(lǐng)獎階段

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

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

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

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

（2）計算Wei看是否等于；

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

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

步驟5CC給Alice獎金。

4 本文方案分析

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

（1）安全性

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

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

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

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

（2）公平性

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

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

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

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

（3）可驗證性

定理5每個人可以驗證隨機函數(shù)是不是隨機生成的，從而驗證獲獎數(shù)字生成的隨機性。

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

定理6中獎?wù)呖梢员还婒炞C其中獎事實。

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

5 方案對比

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

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

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

6 總結(jié)

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

[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提出了基于中國剩余定理和盲簽名的電子彩票方案，但其方案不滿足公平性和公開可驗證性。給出了一種基于安全多方計算的電子彩票協(xié)議，中獎號碼由所有參與者共同產(chǎn)生，可防止合謀造假，并滿足廣泛的可驗證性。

電子彩票；安全多方計算；隨機函數(shù)；公開可驗證性

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.

廣西教育廳基金重點項目（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