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

孫培勇，劉憶寧，李亞軍

桂林電子科技大學 數學與計算科學學院，廣西 桂林 541004

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

孫培勇，劉憶寧，李亞軍

桂林電子科技大學 數學與計算科學學院，廣西 桂林 541004

1 引言

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

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

2 Lee-Chang方案

Lee-Chang電子彩票的參與者主要包括：彩票發行者（LA）、購買者（Player）、認證中心（CA）和銀行（B）；方案包括準備階段、銷售階段、搖獎階段、領獎階段。

2.1 準備階段

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

步驟3LA計算，其中(e，N)是LA的公鑰，N是兩個大素數的乘積，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選取隨機數rj，計算，以及PKLA(α1,α2,…,αt,rA1,rA2,Ecash)，其中PKLA是用LA的公鑰進行加密的算法，rA1，rA2是隨機數。Alice將PKLA(α1，α2，…，αt，rA1，rA2，Ecash)發送給LA。

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

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

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

2.3 搖獎階段

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

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

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

步驟3LA公布獲獎號碼結果CW。

2.4 領獎階段

假設Alice所選取的t個數字與CW相等，成為中獎者，她需要提交證據證明自己是獲獎者。

步驟1Alice發送給LA。

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

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

如果{b1，b2，…，bt}和CW相同，LA確信Alice是獲獎者。

Lee-Chang方案漏洞分析：

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

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

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

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

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

3.1 準備階段

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

3.2 銷售階段

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

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

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

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

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

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

3.3 搖獎階段

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

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

步驟3CC公布中獎數字。

3.4 領獎階段

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

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

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

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

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

步驟3CC經過以上驗證，若都成立，則確信Alice為中獎者。

步驟4CC公布Li，di，?(N)，使所有人都可驗證獲獎者的真偽。

步驟5CC給Alice獎金。

4 本文方案分析

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

（1）安全性

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

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

定理2假設攻擊者P冒充獲獎者Alice領取獎金，也必然失敗。

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

（2）公平性

定理3在彩票銷售結束前，任何人無法預測中獎數字。

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

定理4賣票結束后，任何人不能修改所買彩票的數值。

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

（3）可驗證性

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

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

定理6中獎者可以被公眾驗證其中獎事實。

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

5 方案對比

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

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

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

6 總結

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

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

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

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

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）；桂林電子科技大學科研基金（No.UF08014Y）。

孫培勇（1986—），男，碩士生，研究方向：信息安全；劉憶寧（1973—），男，博士，副教授，研究方向：應用密碼學與信息安全；李亞軍（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