專利名稱：一種隱藏得票數(shù)的電子投票方法
技術(shù)領(lǐng)域：
本發(fā)明涉及電子投票領(lǐng)域，特別涉及安全性要求更高的適合小規(guī)模應(yīng)用的電子投票選舉。
背景技術(shù)：
Endo等人在2008年指出在小規(guī)模投票選舉中如果每個候選人的最終得票數(shù)公開的話，會泄露集團內(nèi)部及中立投票人的投票意愿。考慮這樣一種情況如果Alice是一個董事會成員，而董事會決定舉行一次投票選舉來選出下一屆的董事會主席。現(xiàn)任的董事會主席和副主席宣布所有符合資格的投票候選人名單，而且他們都竭盡全力地爭取他們集團內(nèi)的選票以及其他投票人的選票。Alice是一個中立投票人，不屬于任何一個集團。Alice希望保持自己的投票意向不被其他人知曉，以避免和任何一個集團發(fā)生沖突。但是如果中立投票人的數(shù)量比較少，從每個候選人的最終得票情況來看，即使Alice加密形式的選票未被解密，他的投票意愿也很容易被推測出來，而這違背了投票人的隱私性，從而破壞了選舉的自由。
在一定程度上，投票方案對投票人隱私性的保護程度取決于敵手對誠實投票人選票的不確定性了解。舉個例子如果有兩個候選人Alice和Bob，而每個投票人都希望投給 Alice，此時敵手強迫一個投票人投票給Bob。當最終投票結(jié)果揭曉時，如果最終Bob的得票數(shù)為0則敵手可以確定投票人未按他的意愿去投票，這種情況也違背了投票人的隱私性。
由于參加小規(guī)模投票的人數(shù)比較少，敵手能掌控的選票數(shù)在小規(guī)模投票選舉中比重較大，而誠實投票人的比重較小，誠實投票人的投票意愿很容易由其他人的選票被推測出來，故在小規(guī)模投票中隱私性的保護考慮應(yīng)該比效率更重要。Endo等指出公開所有投票候選人的票數(shù)會降低誠實中立投票人的不確定性，而且參與投票的總?cè)藬?shù)越少，降低的不確定性越大。
在小規(guī)模電子投票中買賣選票和強迫選舉的威脅更大，所以隱藏所有候選人的最終票數(shù)顯得尤為重要，在安全性上小規(guī)模電子投票要求比大規(guī)模電子投票更高，一個小規(guī)模投票應(yīng)該保持所有候選人的得票數(shù)保密。
遺憾的是，幾乎所有的電子投票都直接給出了每位候選人的選票票數(shù)，但卻很少有隱藏選票票數(shù)要求的電子投票方案被提出。
Saisho等利用EWamal密碼體制提出了一個可以隱藏投票人數(shù)量的電子投票方案，但是該方案不是為小規(guī)模電子投票設(shè)計的而且需要特別的計票方法。Endo等利用最高價格拍賣協(xié)議提出了一個可以隱藏投票候選人票數(shù)的投票方案，但方案不能隱藏獲勝方的選票，而且過程不能完全被公開驗證。2001年Cramer等人以及2006年khoenmakers和 Tuyls給出了安全多方計算的相關(guān)協(xié)議，2006年Adida和Neff給出了一個投票保證技術(shù)， 這些都為本發(fā)明的隱藏候選人得票數(shù)的電子投票方案提供了基礎(chǔ)。發(fā)明內(nèi)容
本發(fā)明所要解決的技術(shù)問題是針對小規(guī)模電子投票的安全性、保密性，提出一種隱藏得票數(shù)的電子投票方法。
本發(fā)明為解決上述技術(shù)問題采用以下技術(shù)方案
一種隱藏得票數(shù)的電子投票方法，包括如下步驟
步驟(1)，設(shè)置公開的系統(tǒng)參數(shù)，包括計票機構(gòu)總數(shù)1 ；選票定制機的挑戰(zhàn)比特位數(shù)L ；投票候選人集合C1, ...，Cm，合法投票人集合V1, ...，Vd，其中cn代表候選人總數(shù)，d 代表投票人總數(shù)；
步驟⑵，設(shè)置相關(guān)的公鑰和私鑰，具體步驟如下
步驟001)，由可信機構(gòu)密鑰管理中心(KMC)選擇整數(shù)n，其中η是強素數(shù)p，q的乘積，滿足 P = 2p' +1, q = 2q' +1，gcd( ,爐(《)) = 1 ；
步驟002)，令m = p' q'，由可信機構(gòu)密鑰管理中心(KMC)隨機選擇々e Z:, (a,d)GZ g= (l+n)abn mod η2 ；
步驟(203)，由可信機構(gòu)密鑰管理中心(KMC)計算私鑰SK = β m,并采用Siamir 的(t，n)門限模式共享，具體如下令= β m，由可信機構(gòu)密鑰管理中心(KMC)隨機選擇 t個屮e {0，...，皿-1}，令/的=^=^分，計算計票機構(gòu)Pi的秘密份額Si = f(i)mod mn 并通過安全信道發(fā)給計票機構(gòu)Pi, i e {1，...，t}，t e {1，...，n}；
步驟(204)，公開公鑰I3K = (g,n, θ = am β mod η)、驗證密鑰VK、子驗證密鑰VKi, 其中VK = v是由Z/中的平方數(shù)構(gòu)成的循環(huán)子群的一個元素，=V1 =Vas‘ mod η2，其中Δ=1 ??；
步驟( ，響應(yīng)于合法投票人集合V中的合法投票者輸入的投票選擇，將投票選擇轉(zhuǎn)換成加密的電子選票，產(chǎn)生電子選票的選票定制機，并公開相關(guān)信息以供投票者檢驗；其中選票定制機與合法投票人交互的步驟包括
步驟(301)由選票定制機隨機選擇一個L位的01比特串 Λ并把ρ*告訴投票人； 然后投票人選擇候選人；比特串P*用完以后被銷毀；
步驟(302)根據(jù)投票人\輸入的投票選擇j，其中j表示投票人Vi投票給候選人 Cj, i e {1，...，d}，j e {1，...，cn}，選票定制機打印出 2Lcn 個!Sillier 加密=PEi(I),...， PEi(Cn)；其中每個PEiO都為2L個I^illier加密，每個PEiO分為左右兩部分PEi 和 PEi () E, PEi () L和PEi 0 κ分別對應(yīng)L個I^i 11 ier加密，其中每個hi 11 ier加密的明文為0 或1 ；其中PEi 對應(yīng)的明文與PEi (t)K對應(yīng)的明文相同，PEi 對應(yīng)的明文為p*，PEi (j) κ對應(yīng)的明文與P*相反；
步驟(303)投票人Vi隨機選擇一個L位長的挑戰(zhàn)比特串c告訴選票定制機，其中挑戰(zhàn)比特串c由L位置和R位置組成，L位置和R位置分別用0和1來表示；
步驟(304)根據(jù)挑戰(zhàn)比特串c，由選票定制機計算出cn個對應(yīng)的值Pli，P2i，..., Pcni =Pji = V ,Pu, =PE1(^)l 十C，其中，U e {1，· · ·，cn}，U 乒 j ；并將 Pli，p2i，· · ·，pcni 告訴投票人Vi ；投票人Vi驗證P"是否等于P*，若不相等則投票人提出異議；
步驟(305)根據(jù)挑戰(zhàn)比特串c，由選票定制機公開PEi(I),... ,PEi(Cn)對應(yīng)的明文和加密時用到的隨機值以供檢驗對應(yīng)的加密是否正確形成，驗證Pli，P2i，... ,Pcni與公開的加密所對應(yīng)的R位置上的比特位是否全相反；
步驟(306)選票定制機隨機選擇一個t e {1，2，...，L}，將 PE1(UE1H)llt,…,PEXcnX,^及PEi(Cn)1^留作為選票;
步驟，進行相關(guān)安全多方計算；具體步驟如下
步驟(401)計算
EVn = PE1 ( Θ PE1 ( = PE1 (2\ Θ PE1 ，…，E^= PE1 (cn\ Θ PE1 (οη\， 其中 i e {1，· · ·，ν}，其中用到的原理為:PE(\t PE0Rt =PEQlt +PE(\ -2PE()LPE()Rt， 利用I^illier加密的同態(tài)性，候選AC1最終得票數(shù)的加密形式為￡^ =IXl1G1 ；類似地，對其他候選人C2, ...，Ccn也可以求出相應(yīng)加密的得票數(shù)42，+++，￡& ；
步驟002)對仏^+，^‘中的任意兩個進行明文相同測試，將得票數(shù)相同的歸為一類；
步驟003)設(shè)經(jīng)過步驟(402)處理后變?yōu)?amp;(，...，Gli，其中cn ；對每個C' 1 個機構(gòu)P1,. . . ,P1利用BITREP門將 變?yōu)閷?yīng)的二進制比特位加密表示[[〔。]]，...，[[。；_,_」]， j e {1，···，M}；
步驟(404)對一對[[^^,...,[[CL]]和[[q。]]”..,[[qj]，其中i，j e {1, ... , Μ},i乒j，1個機構(gòu)P1, ...，P1利用[χ > y]比對環(huán)求出[^c/ ；如果[^c/ > ^cj ] = 1成立，貝丨J 說明候選人C' i的最終得票數(shù)大于候選人C'彳的票數(shù)，將C' i繼續(xù)與剩下的其他候選人進行類似比較；
步驟(5)，經(jīng)過安全多方計算后，得到票數(shù)最多的候選人集，公布投票的最終結(jié)果。
進一步的，本發(fā)明的一種隱藏得票數(shù)的電子投票方法，前面所述安全多方計算涉及以下模塊
①乘法門定義[[χ]] =gxrn為一個I^illier加密，其中g(shù)，n為公鑰，r為隨機值， X為消息值；給定[[χ]]和[[y]]，l個機構(gòu)P1,... ,P1通過合作來安全地計算出[[Xy]]，其中 1 > 2 ；
②明文相同測試給定[[χ]]和[[y]]，1個機構(gòu)P1, ...，P1通過合作來安全地進行相關(guān)計算，以判斷對應(yīng)的明文X和y是否相等，其中13 2;
③加法環(huán)或減法環(huán)對于給定的關(guān)于X，y的二進制比特位加密表示[[&]]，...， [[V -J ]和[[y。] ]，···，[ [yffl' -J ]，即χ = Σ ο xJ2^y = O3，加法環(huán)或減法環(huán)計算關(guān)于x+y或x-y的二進制比特位加密表示[[X。]]，...，[[zffl, _J]；利用的原理如下
C— = O, Ci = XiYi+XiCi^+yiCi^^XiyiCi^, Zi = XjyjcHjci ；其中 O 彡 i 彡 m' _1 ；
④[χ > y]比對環(huán)對于給定的關(guān)于X，y的二進制比特位加密表示[[&]]，...， [[ν -J ]和[[y0] ]，···，[ [ym, -J ]，計算[χ > y]，其中若 χ > y 成立則[χ > y]的值為 1，否則[x>y]為 O ；推導過程如下:t0 = 0,ti+1= (1-(Xi-Yi) ^ti+x-x^ ；其中 O 彡 i 彡 m' -1， [x > y]的值為tm,；
⑤隨機比特門對于i = 1，...，1，機構(gòu)Pi隨機生成一個比特h e {0，1}，對、加密形成[[bj]，并廣播[[bj]及相關(guān)的非交互零知識證明，證明h e {0,1}確實是一個比特；對所有的[[bj]，計算出[[b]]，其中δ = !，,;利用的原理如下對于i，j e {1，...，lM 十辦,
⑥BITREP門給定一個I^illier加密[[x]]，機構(gòu)P1, ...,P1合作計算出[[χ]] 中的X對應(yīng)的二進制比特位加密表示[[XJ]，...，[[Xffli -J]，其中1彡2。
進一步的，本發(fā)明的一種隱藏得票數(shù)的電子投票方法，前面所述乘法門計算的相關(guān)步驟包括
步驟Al 假設(shè)1個機構(gòu)產(chǎn)生關(guān)于χ的秘密
Al-a 每個機構(gòu)Pi選擇一個隨機值Cli，對(Ii加密形成[[dj并廣播[[dj以及相關(guān)的非交互零知識證明，證明Pi確實知曉di，令d表示；
Al-b:計算出[[X]][[dJ]... [[Cl1]] = [[x+d]]，t 個機構(gòu)合作門限解密得到 x+d;
Al-c 由 P1 求出 X1 = (x+d)-Cl1，其他機構(gòu) Pi 求出 Xi = - ,,χ = ^^ ；
步驟Α2 每個機構(gòu)？1廣撒Ly]r =[Ky]]和[[Xi]]，以及相關(guān)的非交互零知識證明， 以證明[[Xiy]]確實對應(yīng)于[[Xi]]中的\和[[y]]中的y ；
步驟A3 假設(shè)H為通過以上步驟的機構(gòu)集合，C為其他的機構(gòu)集合；計算x^Jki]]，并門限解密得到&=乙^成，由&和[[y]]計算得到[[xcy]]；因此，由 {[[Xiy]]|i e H}和[kcy]]，所有的機構(gòu)計算(Xi eH[[Xiy]]) X [kcy]]，即得到關(guān)于 xy 的 [[xy]]。
進一步的，本發(fā)明的一種隱藏得票數(shù)的電子投票方法，前面所述明文相同測試計算的相關(guān)步驟包括
步驟Bl 計算出[[y]]—1 = [[_y]]；
步驟B2 計算出[[χ] ] [ [y] Γ1 = [ [x-y]]；
步驟B3 每個機構(gòu)Pi選擇一個隨機值屯，廣播肽-_)；]]4和[Wi]]以及相關(guān)的非交互零知識證明，令d表示Σ!1=Α ；
步驟Β4 計算出[[x-_y]f [[x-_y]]d2...[[x-_y]]d" =[[x__y]]d，n 個機構(gòu)合作門限解密[[x-y]]d，若對應(yīng)的明文為0，則χ和y相等，否則對應(yīng)的明文不為0，χ和y不相等。
進一步的，本發(fā)明的一種隱藏得票數(shù)的電子投票方法，前面所述隨機比特門采用相關(guān)的非交互零知識證明步驟為對[[bj]計算[[bj]2= [[bJHEbJLi個機構(gòu)P1,...， &對[[bj]和[[bj]2進行明文相同測試，若最后結(jié)果兩者明文相同則成立，即證明h等于 0或1 ；否則不成立。
進一步的，本發(fā)明的一種隱藏得票數(shù)的電子投票方法，前面所述BITREP門計算的相關(guān)步驟包括
步驟Fl 設(shè)N為I^illier加密中的模數(shù)公鑰，產(chǎn)生一個隨機值r e E
Fl-a 機構(gòu)P1, ...，P1利用隨機比特門產(chǎn)生m'個隨機比特位加密值[[rj]，..., [[rm, -J]；
Fl-b:假設(shè) N 的二進制比特表示為 Ntl，···，Nm, <，對[[rQ]]，···，[[rm, _J]和 N0, . . . , Nffl,—，利用[x>y]比對環(huán)計算出[[例>1~]]]，其中廠=1；1—>^;
Fl-c 門限解密[[[N > r]]]得到[N > r]，如果[N > r] = 1成立則繼續(xù)；否則跳轉(zhuǎn)到步驟Fl-a ；
步驟F2 計算[Ly]] = [[x]]n二叱]產(chǎn)，1個機構(gòu)P1,…，P1門限解密[W]得到y(tǒng)=x+r mod N,0 ^ y < N ；
步驟F3 對y0,... , Yffl^1和[[rQ] ]，···，[ [rm_J ]，利用減法環(huán)求出對應(yīng)的比特位加密表示[[Z。]]，···，[[Zm]]，其中Z = X或者Z = X-N，其中^表示符號位；
步驟F4 根據(jù)符號位Zm決定ζ = χ或者ζ = χ-Ν ；若ζ = χ-Ν,則對[[ζ0] ]，···， [[ZmJ ]和 NQ，· · ·，Nm^1 利用加法環(huán)求出 χ 對應(yīng)的[[xQ] ]，···，[ [Xm-J ]。
進一步的，本發(fā)明的一種隱藏得票數(shù)的電子投票方法，前面所述步驟Al-a中所述相關(guān)的非交互零知識證明方法為對給定的[[a]] = gasn bmod n2，證明人P證明其確實知道α的值，包括以下步驟
al，由證明人P隨機選取χ e Zn，μ G ZJ，計算B = gV mod η2 ；
a2,由證明人P利用安全無碰撞哈希函數(shù)H {0，1}* — Zn計算挑戰(zhàn)值e = H(n，g， [[α]],B)；
a3，令 w = x+e α mod η，由證明人 P 計算 ζ = usV mod n2，其中 t 滿足 x+e α = w+tn，然后由證明人P公布(B，e，w，z)；
驗證時計算孖(《，Α[[α]]，5)，Κζ":5[[α]]βιη0(1 2。
進一步的，本發(fā)明的一種隱藏得票數(shù)的電子投票方法，前面所述步驟Α2所述相關(guān)的非交互零知識證明方法為對給定的[[a]] = garn mod η2, [[α]] = gasn mod η2和D = [[a]]a Yn mod n2，由證明人P證明D= [[aa]]成立，包括以下步驟
bl，由證明人 P 隨機選取 χ e Ζη，ν,MeZ/，計算 A = [[a]] V mod η2, B = gxun mod η2 ；
b2，由證明人P利用安全無碰撞哈希函數(shù)H {0，1}* — Zn計算挑戰(zhàn)值e = H(n，g， [[a]], [[a]]，D，A，B)；
b3，令 w = x+e α mod n，由證明人 P 計算 ζ = usY mod n2，y = ν [ [a] ]1 γ e mod n2,其中 t 滿足 x+e α = w+tn, P 公布(A, B, e, w, z, y)；
驗證計算孖(《，孓[[ ]]，[[ ]]，D,mod 2，[[α]]>":JDe mod 2。
進一步的，本發(fā)明的一種隱藏得票數(shù)的電子投票方法，前面所述步驟B3所述相關(guān)的非交互零知識證明方法為對給定的[[a]] = garn mod η2, [[α]] = gasn mod η2和D = [[a]]a Yn mod n2，由證明人P證明D= [[aa]]成立，包括以下步驟
!^，由證明人？隨機選取叉曰三…乂，？^之/，計算八=[[a]]V mod η2, B = gxun mod η2 ；
b2，由證明人P利用安全無碰撞哈希函數(shù)H {0，1}* — Zn計算挑戰(zhàn)值e = H(n，g， [[a]], [[a]]，D，A，B)；
b3，令 w = x+e α mod n，由證明人 P 計算 ζ = usY mod n2，y = ν [ [a] ]1 γ e mod n2,其中 t 滿足 x+e α = w+tn, P 公布(A, B, e, w, z, y)；
驗證計算孖(《，孓[[ ]]，[[ ]]，D,mod 2，[[α]]>":JDe mod 2。
進一步的，本發(fā)明的一種隱藏得票數(shù)的電子投票方法，前面所述門限解密計算的相關(guān)步驟包括
步驟001 計票機構(gòu)Pi計算=C2Mmodw2，其中i e {1，2，...，1}，并公布相關(guān)的非交互零知識證明loge ^2=IogyA ^，其中Δ =1 ！，具體證明方法為對于 = xSiA =gs'、= (u,ν)，由證明人P證明比=IogxWi，具體包括如下步驟
首先，由證明人P隨機選取w e Zmn，計算出(xw，gw) = (a,b)；其次，由證明人P利用安全無碰撞哈希函數(shù)H {0，1}* — Zmn計算挑戰(zhàn)值e = H(a，b，u, ν)；然后，由證明人P計算 r = w+Sie，公布(a，b，e，r)；最終,驗證時計算孖(α>，Μ，v)，x^aMe，壙；
步驟002 如果少于t個正確通過上個步驟的非交互零知識證明，則停止；否則令S是通過上述步驟t+Ι個秘密共享的集合，計算M = 產(chǎn)modn2)^modn，其中< =aTL轉(zhuǎn)e z，丄㈨=t。J -Jη
本發(fā)明采用以上技術(shù)方案與現(xiàn)有技術(shù)相比，具有以下技術(shù)效果
本發(fā)明基于安全多方計算和投票保證技術(shù)，提出了一個新的適合小規(guī)模應(yīng)用的電子投票方案以及隱藏候選人的得票數(shù)的方法，可以真正使得所有候選人的最終得票數(shù)都是隱藏的。


圖1是本發(fā)明的方法流程圖。
具體實施方式
下面結(jié)合附圖對本發(fā)明的技術(shù)方案做進一步的詳細說明
結(jié)合圖1所示，下面以一個簡單例子來說明本方案的具體實施。
設(shè)置公開的系統(tǒng)參數(shù)假設(shè)計票機構(gòu)總數(shù)1 = 4，共4個計票機構(gòu)=P1A2U4 ；投票候選人為 C1, C2, C3, C4, cn = 4 ；合法投票人名單 V1, V2, V3, V4, V5, d = 5 ;L = 3。
設(shè)置相關(guān)的公鑰和私鑰假設(shè)ρ = 11，q = 17，η = pq = 187，m = 5X8 = 40，β =6, a = 7, b = 8,
g = (1+187) 78187modl872 = 166 45，t = 2, SK = a0 = 240，B1 = 11, a2 = 10,
f (x) = 240+1 lx+10x2，S1 = f (1) = 261, S2 = f (2) = 302，S3 = f (3) = 363，S4 =f (4) = 444，
PK = (16645，187，184)，VK = ν = 4, Δ = 24, VK1 = V1 = 1378, VK2 = v2 = 33185，
VK3 = V3 = 511, VK4 = V4 = 1038。
投票人V1與選票定制機的交互過程如下
步驟A 選票定制機隨機選擇一個3位的01比特串假設(shè)為101)，并把ρ* = 101 告訴投票人Vi。然后V1選擇候選人(假設(shè)V1選擇候選人C3)。P*將會在晚些時候被銷毀。
步驟B 選票定制機打印出共 M 個 I^ai 11 ier 加密=PE1(I), PE1 (2)，PE1 (3)，PE1 (4)， 其中每個PE1 (·)都為6個Paillier加密，分為左右兩部分=PE1 ( · ) L和PE1 ( · ) K，PE1 ( ·) L和PE1 ( · )κ分別對應(yīng)3個I^illier加密，每個I^aillier加密的明文為O或1。PE1 (t)， (t e {1，... ,4}, t ^ 3)對應(yīng)的明文為隨機的6位01比特串，其中PE1 (t)L對應(yīng)的明文12與PE1 (t) E對應(yīng)的明文相同例如取加密隨機值為2，3，4，5，6，7，PE1 (1) L和PE1 (1) κ為3個 Paillier加密，對應(yīng)的明文為001，對應(yīng)的密文分別為/^、1)11:乂21871110(134969 = 14兄0， PE1(I)12 g-°3187 mod34969 = 28686，
PE1(I)li :g-M187 mod34969 = 13694 ( :g°5187 mod34969 = 21057 ,
PE1(I)ri : ^6187 mod34969 = 33393 ,PEl(V)li3 : ^7187 mod34969 = 20428 ；
類似地，PE1 和PE^h為3個I^illier加密，對應(yīng)的明文為110 ；PE1 (4)L ^P PE1(A)k* 3個I^illier加密，對應(yīng)的明文為100。而PE1 (3)l對應(yīng)的明文為P* = 101， PE1 (3) E對應(yīng)的明文與ρ*相反為010。
步驟C:投票人V1隨機選擇一個3位長的挑戰(zhàn)比特串c (c由L(左)和R(右)組成，分別用O和1來表示，在此令C = 011)告訴選票定制機。
步驟D 根據(jù)挑戰(zhàn)值C，選票定制機計算對應(yīng)的值P11, P21，P31，P41 =P31 = P*= 101，
; =尸五!(I)i = 001 十 011 = 010，; 21 =尸五?、埔沂?c = 110 十 011 = 101,
= 十 011 = 111 并將 Pll，p21, p31, p41 告訴投票人力。投票人 V1 驗證P31是否等于P*，若不相等投票人可以提出異議。
步驟E 根據(jù)挑戰(zhàn)值c，選票定制機公開PE1(I), PE1 (2), PE1(S), PE1 (4)對應(yīng)的明文和加密時用到的隨機值以供檢驗對應(yīng)的加密是否正確形成。驗證P11, P21，P31，P41與公開的加密所對應(yīng)的R位置上的比特位是否全相反。例如C = 011，左右右，故選票定制機給出；⑴Α，Ρ￡；(I)ivPE1(I)A對應(yīng)的明文001和加密用到的隨機值2，6，7以供檢驗對應(yīng)的加密是否正確形成。檢驗c中的所有1對應(yīng)的位置上，P11 (對應(yīng)為10)與公開的明文(對應(yīng)為01)是否全相反。同理對戶爲口夂，戶爲口；^，；^；口；^， PE人3\，PE1(T)ri,PE1(T)rmr PEl(A)h,PE1(A)ri,PEl(A)lii。
步驟F 選票定制機隨機選擇一個t = 2
PE1 (S)i2，PE1 (3)R2，PE1 ，PE1 (4\保留作為選票。
同理，投票人V2，V3, V4, V5與選票定制機的交互過程與步驟A-F類似。
對形成的選票進行相關(guān)安全多方計算
步驟Al 機構(gòu) P1, P2, P3, P4 合作計算得到 A1 =ΡΕΧ% θ^( ,^2 =PE1(I)^ 十尸年(2)代，=PE1^, PEi^Rt, 4 =PEi(A)l, PEi(A)ri (i 曰{1，···，(!})，其中用到的原理為PE(\ PEQRt =PEQli +PEQRt -2ΡΕ(\ΡΕ(\。利用 ^mier加密的同態(tài)性，候選AC1最終得票數(shù)的加密形式可表示為=Hil1i^1 。例如， EVn = PE1 (I)i2 十 PE1 ( )Κ2 = [
] = [
], EVi2 = [[1 十 1]] = [
], Ev^ = [
] = [[1]],￡κ14=[[οθο]] = [[Ο]]。同理可求出 ，K11，Εν ，EV24 ‘ ΕΥ ，eV32，EV ，EV,4 ‘ EV ，五K42，EV4,，EV44 和EVii,EVii,E ,EV54。假設(shè)投票人V2選擇候選人C2，V3選擇候選人C3，V4選擇候選人C1, V5選擇候選人C4,則此時候選人C1的最終得票數(shù)的加密形式為 eC1 = Evn χEvii χEv^ χEvh χi F5i =[
] = [[1]]，C2 的最終得票數(shù)的加密形式為 eC1 = Evii χ Ε、χ Ε、X^42 X^52 =[
] = [[1]]，投票候選人 C3 的最終得票數(shù)的加密形式43可表示為 K3 = Eyu X EVn X Er33 X EVa X i F53 =[[1 + 0 + 1 + 0 + 0]] = [[2]]，C4 的最終得票數(shù)的加密形式為 K4 = Evu χ Evu χ EVm xEVuxEVm=[
] = [[1]]。
步驟B1 對，Eci，Ecy，E04中的任意兩個進行明文相同測試，將得票數(shù)相同的歸為一類。故此時\，42，44為一類￡^，Ec溈一類Ec;，M = 2。
步驟Cl 經(jīng)過步驟Bl后變?yōu)镋c;，Eci。對每個C' j, j e {1，2}，機構(gòu)P1, P2, P3, P4 利用BITREP門將 變?yōu)閷?yīng)的二進制比特位加密表示[[C)。]]，...，[[C;j]。
步驟Di 對[x>y]比對環(huán)求出>、]。解密[ >、]得到明文0，說明候選人C' i = (C1,C2,C4I的得票數(shù)小于候選人C' 2= {C3}的票數(shù)，故投票候選人C3的票數(shù)最多，C3為最終的投票獲勝者。
步驟Al 求 Evii 的步驟為PE戰(zhàn) +PE1(I)ri = 28686 χ 33393 mod34969 = 5781,參考權(quán)利要求2，禾Ij用乘法門求出PE戰(zhàn)PE1(V)r2 ，再禾Ij用 ΡΕ(\ Φ PEOnt = PE(\ + PEOri - 2ΡΕ(\ PEQRt即可求出。參考權(quán)利要求2，其中求 PE1(I)i2PE1(I)ii2的步驟如下
步驟A2 機構(gòu)P1, P2, P3, P4產(chǎn)生關(guān)于PE1(I)I^秘密
A2a 機構(gòu) P1 選擇一個隨機值(I1 = 2，對(I1 加密形成[[dj] = 1664528187mod34969 =14407，P2 選擇一個隨機值(12 = 3，對(12加密形成[[d2]] = 1664535187mod34969 = 6514， P3 選擇一個隨機值(13 = 4，對(13加密形成[[d3]] = 1664546187mod34969 = 30884，P4 選擇一個隨機值d4 = 5，對d4加密形成[[dj] = 1664557187mod34969 = 2似82，廣播[[dj以及相關(guān)的非交互零知識證明，證明Pi確實知曉屯。令
權(quán)利要求
1. 一種隱藏得票數(shù)的電子投票方法，其特征在于，包括如下步驟 步驟(1)，設(shè)置公開的系統(tǒng)參數(shù)，包括計票機構(gòu)總數(shù)1 ；選票定制機的挑戰(zhàn)比特位數(shù)L ； 投票候選人集合C1, Cm，合法投票人集合V1, . . .，Vd，其中cn代表候選人總數(shù)，d代表投票人總數(shù)；步驟O)，設(shè)置相關(guān)的公鑰和私鑰，具體步驟如下步驟001)，由可信機構(gòu)密鑰管理中心(KMC)選擇整數(shù)n，其中η是強素數(shù)p，q的乘積， 滿足 P = 2p' +1, q = 2q' +1，gcd( ,爐(《)) = 1 ；步驟002)，令m = p' q'，由可信機構(gòu)密鑰管理中心(KMC)隨機選擇々eZ:, (a,b)&Z*xZ* ,^g= (l+n)abn mod η2 ；步驟(203)，由可信機構(gòu)密鑰管理中心(KMC)計算私鑰SK = β m，并采用Smmir的(t， η)門限模式共享，具體如下令如=β m，由可信機構(gòu)密鑰管理中心(KMC)隨機選擇t個 Bi e {O, ... , mn-l}，令/(χ) = Σ|=?！鼎?，計算計票機構(gòu)Pi的秘密份額Si = f(i)modmn并通過安全信道發(fā)給計票機構(gòu)Pi, i e {1，...，t}，t e {Ι,.,.,η}；步驟(204)，公開公鑰I3K = (g，η, θ = am β mod η)、驗證密鑰VK、子驗證密鑰VKi,其中VK = v是由Z/中的平方數(shù)構(gòu)成的循環(huán)子群的一個元素，f^.=K=v^m0d 2，其中Δ =1 ??；步驟( ，響應(yīng)于合法投票人集合V中的合法投票者輸入的投票選擇，將投票選擇轉(zhuǎn)換成加密的電子選票，產(chǎn)生電子選票的選票定制機，并公開相關(guān)信息以供投票者檢驗；其中選票定制機與合法投票人交互的步驟包括步驟(301)由選票定制機隨機選擇一個L位的01比特串 Λ并把ρ*告訴投票人；然后投票人選擇候選人；比特串P*用完以后被銷毀；步驟(302)根據(jù)投票人\輸入的投票選擇j，其中j表示投票人Vi投票給候選人Cj, i e {1，...，d}，j e {1,. . .，cn}，選票定制機打印出 2Lcn 個 I^aillier 加密=PEi(I),...， PEi (cn)；其中每個PEiO都為2L個I^illier加密，每個PEiO分為左右兩部分PEi 和 PEi () E, PEi () L和PEi 0 κ分別對應(yīng)L個I^i 11 ier加密，其中每個hi 11 ier加密的明文為0 或1 ；其中PEi 對應(yīng)的明文與PEi (t)K對應(yīng)的明文相同，PEi 對應(yīng)的明文為p*，PEi (j) κ對應(yīng)的明文與P*相反；步驟(303)投票人Vi隨機選擇一個L位長的挑戰(zhàn)比特串c告訴選票定制機，其中挑戰(zhàn)比特串c由L位置和R位置組成，L位置和R位置分別用0和1來表示；步驟(304)根據(jù)挑戰(zhàn)比特串c，由選票定制機計算出cn個對應(yīng)的值Pli，P2i，...，Pcni Pji = Pm =PE1(U)l 十 c，其中，uG {1，· · ·，cn}，u 乒 j ；并將 Pli，p2i，... , pcni 告訴投票人Vi ；投票人Vi驗證ρ"是否等于p*，若不相等則投票人提出異議；步驟(305)根據(jù)挑戰(zhàn)比特串c，由選票定制機公開PEi(I),... ,PEi(Cn)對應(yīng)的明文和加密時用到的隨機值以供檢驗對應(yīng)的加密是否正確形成，驗證Pli，P2i，... ,Pcni與公開的加密所對應(yīng)的R位置上的比特位是否全相反；步驟(306)選票定制機隨機選擇一個t e {1，2，…，L}，將 PEA)、,PEi(^)lit,...,PEXcnX,以及PEi(Cn)li保留作為選票;步驟G)，進行相關(guān)安全多方計算；具體步驟如下步驟(401)計算Evn =PmLt PE1(I)lit, Evn =PEi(I)li PEi(I)Rt, Ev^ = PEi(Cn)lt PEi(Cn)Rt，其中 i e {!,..., ν}，其中用到的原理為·ΡΕ(\ PEQRt =PE()Li +ΡΕ(\ -2ΡΕ(\ΡΕ(\，利用 I^illier加密的同態(tài)性，候選AC1最終得票數(shù)的加密形式為￡^ =IXl1G1 ；類似地，對其他候選人C2, ...，Ccn也可以求出相應(yīng)加密的得票數(shù)^02，+ ++，￡& ；步驟(402)對仏^+，^‘中的任意兩個進行明文相同測試，將得票數(shù)相同的歸為一類； 步驟G03)設(shè)經(jīng)過步驟(40 處理后變?yōu)椋?..，￡。，其中M < cn ；對每個C'」，1個機構(gòu)P1, ...，P1利用BITREP門將 變?yōu)閷?yīng)的二進制比特位加密表示[[ 。]],...,[[CU， j e {1，···，M}；步驟(404)對一對[[q^.+.iqj]和[[c;。]]”..,[[c;j]，其中 i，j e {1，· · ·，M}，i 乒 j，1個機構(gòu)P1, ...，P1利用[X > y]比對環(huán)求出>化]；如果[^C/ > ]=1成立，則說明候選人C' i的最終得票數(shù)大于候選人C'彳的票數(shù)，將C' i繼續(xù)與剩下的其他候選人進行類似比較；步驟(5)，經(jīng)過安全多方計算后，得到票數(shù)最多的候選人集，公布投票的最終結(jié)果。
2.如權(quán)利要求1的一種隱藏得票數(shù)的電子投票方法，其特征在于，所述安全多方計算涉及以下模塊①乘法門定義[[χ]]=gxrn為一個I^illier加密，其中g(shù)，η為公鑰，r為隨機值，χ 為消息值；給定[[χ]]和[[y]]，1個機構(gòu)P1, ...，P1通過合作來安全地計算出[[xy]]，其中 1 > 2 ；②明文相同測試給定[[χ]]和[[y]]，1個機構(gòu)P1,...,P1通過合作來安全地進行相關(guān)計算，以判斷對應(yīng)的明文χ和y是否相等，其中1彡2 ；③加法環(huán)或減法環(huán)對于給定的關(guān)于χ，y的二進制比特位加密表示[[xj]，...，[[V -J ]和[[y。] ]，···，[ [yffl' -J ]，即χ = Σ ο ^ 2;，少=O3，加法環(huán)或減法環(huán)計算關(guān)于x+y或x-y的二進制比特位加密表示[[zj]，...，[[zffl, _J]；利用的原理如下C-! = O, Ci = XiYi+XiCi^+yiCi^^XiyiC^!, Zi = XjyjcH-Zci ；其中 O < i < m' _1 ；④[x>y]比對環(huán)對于給定的關(guān)于χ，y的二進制比特位加密表示[[&]]，...， [[ν -J ]和[[y0] ]，···，[ [ym, -J ]，計算[χ > y]，其中若 χ > y 成立則[χ > y]的值為 1，否則[x>y]為 O ；推導過程如下:t0 = 0,ti+1= (1-(Xi-Yi) ^ti+x-x^ ；其中 O 彡 i 彡 m' -1， [x > y]的值為tm,；⑤隨機比特門對于i= 1，...，1，機構(gòu)Pi隨機生成一個比特bi e {0，1}，對、加密形成[[bj]，并廣播[[bj]及相關(guān)的非交互零知識證明，證明h e {0,1}確實是一個比特； 對所有的[[bj]，計算出[[b]]，其中“θ^.;利用的原理如下對于i，j e {1，···，1}，h θ b, =b, +b,-2b,b,；‘J ‘ J‘ J⑥BITREP門給定一個I^illier加密[[χ]]，機構(gòu)P1,...,P1合作計算出[[χ]]中的 χ對應(yīng)的二進制比特位加密表示[[χ。]]，...，[[Xffl- —J]，其中1彡2。
3.根據(jù)權(quán)利要求2所述的一種隱藏得票數(shù)的電子投票方法，其特征在于，所述乘法門計算的相關(guān)步驟包括步驟Al 假設(shè)1個機構(gòu)產(chǎn)生關(guān)于χ的秘密Al-a:每個機構(gòu)？1選擇一個隨機值屯，對屯加密形成[⑷]并廣播[⑷]以及相關(guān)的非交互零知識證明，證明Pi確實知曉屯，令d表示；Al-b:計算出[[X]][[dJ]··· [[dj] = [[x+d]]，t個機構(gòu)合作門限解密得到x+d;Al-c 由 P1 求出 Xi = (x+d)-Cl1，其他機構(gòu) Pi 求出 Xi = -^,X = YjIiX1 ；步驟A2 每個機構(gòu)？1廣撒Ly]r =[Ky]]和[[Xi]]，以及相關(guān)的非交互零知識證明，以證明[[XiY]]確實對應(yīng)于[[Xi]]中的XjP [[y]]中的y ；步驟A3 假設(shè)H為通過以上步驟的機構(gòu)集合，C為其他的機構(gòu)集合；計算X i e e [ [xj ]， 并門限解密得到&=乙^而，由&和[[y]]計算得到[[xcy]]；因此，由{[[Xiy]] Ii e H} 和[[xey]]，所有的機構(gòu)計算(※“!^^…^※[[^^，即得到關(guān)于”的[砂]]。
4.根據(jù)權(quán)利要求2所述的一種隱藏得票數(shù)的電子投票方法，其特征在于，所述明文相同測試計算的相關(guān)步驟包括步驟 Bl 計算出[[y]]—1 = [[-y]]；步驟B2:計算出關(guān)關(guān)-1= [[x-y]]；步驟B3:每個機構(gòu)？1選擇一個隨機值屯，廣播[[x-_y]]4和[Wi]]以及相關(guān)的非交互零知識證明，令d表示；步驟 Β4 計算出[[χ-[[χ-...[[X-= [[X-乂]"，η 個機構(gòu)合作門限解密 [[x-y]]d，若對應(yīng)的明文為0，則χ和y相等，否則對應(yīng)的明文不為0，χ和y不相等。
5.根據(jù)權(quán)利要求2所述的一種隱藏得票數(shù)的電子投票方法，其特征在于，所述隨機比特門采用相關(guān)的非交互零知識證明步驟為對[[bj]計算[[bj]2 = [[bJHftJ]，ι個機構(gòu)P1,... ,P1對[[bj]和[[bj]2進行明文相同測試，若最后結(jié)果兩者明文相同則成立，即證明bi等于0或1;否則不成立。
6.根據(jù)權(quán)利要求2所述的一種隱藏得票數(shù)的電子投票方法，其特征在于，所述BITREP 門計算的相關(guān)步驟包括步驟Fl 設(shè)N為I^illier加密中的模數(shù)公鑰，產(chǎn)生一個隨機值r e E
]，..., [[rm, -J]；Fl-b 假設(shè) N 的二進制比特表示為 N。，· · ·，Nm,—，對[[rQ] ]，···，[ [rm, ]和 NQ，· · ·， Nm, ，利用[x>y]比對環(huán)計算出[[例>1~]]]，其中” =[；1—>^;Fl-c 門限解密[[[N>r]]]得到[N>r]，如果[N > r] = 1成立則繼續(xù)；否則跳轉(zhuǎn)到步驟Fl-a ；步驟F2 計算[Ly]] = [M]n 二叱]產(chǎn)，1個機構(gòu)P1, ...，P1門限解密[[y]]得到y(tǒng) = x+rmod N, 0 彡 y < N ；步驟F3 對％，...，Yffl^1和[[rj]，[[rm_J]，利用減法環(huán)求出對應(yīng)的比特位加密表示[[z0]],..., [[Zm]]，其中ζ = χ或者ζ = x-N，其中Zm表示符號位；步驟F4 根據(jù)符號位決定ζ = χ或者ζ = x-N ；若ζ = x-N,則對[[zQ] ]，···，[ [ZmJ ]和N。，· · ·，Nm^1利用加法環(huán)求出χ對應(yīng)的[[xj ]，···，[ [Xm-J ]。
7.根據(jù)權(quán)利要求3所述的一種隱藏得票數(shù)的電子投票方法，其特征在于，步驟Al-a中所述相關(guān)的非交互零知識證明方法為對給定的[[α ]] = gasn mod n2，證明人P證明其確實知道α的值，包括以下步驟al，由證明人P隨機選取χ e Ζη，μ e Zj，計算B = gxun mod η2 ；a2,由證明人P利用安全無碰撞哈希函數(shù)H: {0，1}* —&計算挑戰(zhàn)值e = H (n, g， [[α]],B)；a3,令 w = x+ea mod η,由證明人 P 計算 ζ = usY mod η2,其中 t 滿足 x+ea = w+tn, 然后由證明人P公布(B，e，w，z)；驗證時計算e 二孖(《，孓[[a]], B),gwzn =B[[a]]e mod η2。
8.根據(jù)權(quán)利要求3所述的一種隱藏得票數(shù)的電子投票方法，其特征在于，步驟Α2所述相關(guān)的非交互零知識證明方法為對給定的[[a]] = garn mod η2, [[α]] = gasn mod η2和 D = [[a]]a Yn mod n2，由證明人P證明D= [[aa]]成立，包括以下步驟bl，由證明人 P 隨機選取 χ e Ζη，ν,μ G Z/，計算 A = [[a]] V mod η2, B = gV modη2；匕2，由證明人？禾1傭安全無碰撞哈希函數(shù)!1:{0，1}* — 4計算挑戰(zhàn)值6 = !1(1^，[[3]]， [[a]]，D，A，B)；b3,令 w = x+e α mod η,由證明人 P 計算 ζ = usY mod η2, y = vtta]]' γ e mod η2, 其中 t 滿足 x+e α = w+tn, P 公布(A, B, e, w, ζ, y)；驗證計算孖O,孓[[到],[[ ]],/),冼5),^^":萬[[ ]『modn\[[a]]wyn = ADe mod 2。
9.根據(jù)權(quán)利要求4所述的一種隱藏得票數(shù)的電子投票方法，其特征在于，步驟B3所述相關(guān)的非交互零知識證明方法為對給定的[[a]] = garn mod η2, [[α]] = gasn mod η2和 D = [[a]]a Yn mod n2，由證明人P證明D= [[aa]]成立，包括以下步驟bl,由證明人 P 隨機選取 χ e Ζη，ν,μ G Z/，計算 A = [[a]] V mod η2, B = gV modη2；匕2，由證明人？禾1傭安全無碰撞哈希函數(shù)!1:{0，1}* — 4計算挑戰(zhàn)值6 = !1(1^，[[3]]， [[a]]，D，A，B)；b3,令 w = x+e α mod η,由證明人 P 計算 ζ = usY mod η2, y = vtta]]' γ e mod η2, 其中 t 滿足 x+e α = w+tn, P 公布(A, B, e, w, ζ, y)；驗證計算孖O,孓[[到],[[ ]],/),冼5),^^":萬[[ ]『modn\[[a]]wyn = ADe mod 2。
10.根據(jù)權(quán)利要求3或4或6所述的一種隱藏得票數(shù)的電子投票方法，其特征在于所述門限解密計算的相關(guān)步驟包括步驟001:計票機構(gòu)？1計算q=C2Mmod 2，其中i e {1,2, ... , 1}，并公布相關(guān)的非交互零知識證明log, ￥ =IogyA\，其中Δ = 1 ！，具體證明方法為對于 = xSiA =gs'、= (u,ν)，由證明人P證明Iogghi = IogxWi，具體包括如下步驟 首先，由證明人P隨機選取we Zmn，計算出(xw，gw) = (a,b)；其次，由證明人P利用安全無碰撞哈希函數(shù)H {0，1}* — Zmn計算挑戰(zhàn)值e = H(a，b，u，ν)；然后，由證明人P計算r= w+Sie，公布(a，b，e，r)；最終，驗證時計算
全文摘要
本發(fā)明公開了一種隱藏得票數(shù)的電子投票方法，首先設(shè)置公開的系統(tǒng)參數(shù)，以及相關(guān)的公鑰和私鑰；接著響應(yīng)于投票者的投票選擇輸入，產(chǎn)生電子加密選票的電子選票定制機；然后根據(jù)形成的電子加密選票進行相關(guān)的安全多方計算，最終得到隱藏所有候選人得票數(shù)的投票結(jié)果。本發(fā)明采用安全多方計算，結(jié)合投票保證技術(shù)給出了可以隱藏所有候選人得票數(shù)的電子投票方法，解決了現(xiàn)有技術(shù)中公開候選人得票數(shù)的投票選舉中存在的問題，確保了電子投票選舉中所有投票候選人的最終得票數(shù)都是保密的，可以保證電子投票、尤其是小規(guī)模投票選舉中投票人的隱私性。
文檔編號G07C13/00GK102521910SQ20111042566
公開日2012年6月27日 申請日期2011年12月16日 優(yōu)先權(quán)日2011年12月16日
發(fā)明者張亦辰, 李繼國, 羅翀 申請人:河海大學