An Incoercible E-Voting Scheme Based on Revised Simplified Verifiable Re-encryption Mix-nets

Shinsuke Tamura, Hazim A. Haddad, Nazmul Islam, Kazi Md. Rokibul Alam

Information Security and Computer Fraud

An Incoercible E-Voting Scheme Based on Revised Simplified Verifiable Re-encryption Mix-nets

Shinsuke Tamura1,, Hazim A. Haddad1, Nazmul Islam2, Kazi Md. Rokibul Alam2

1Graduate School of Engineering, University of Fukui, Japan

2Department of Computer Science and Engineering, Khulna University of Engineering and Technology, Bangladesh


Simplified verifiable re-encryption mix-net (SVRM) is revised and a scheme for e-voting systems is developed based on it. The developed scheme enables e-voting systems to satisfy all essential requirements of elections. Namely, they satisfy requirements about privacy, verifiability, fairness and robustness. It also successfully protects voters from coercers except cases where the coercers force voters to abstain from elections. In detail, voters can conceal correspondences between them and their votes, anyone can verify the accuracy of election results, and interim election results are concealed from any entity. About incoercibility, provided that erasable-state voting booths which disable voters to memorize complete information exchanged between them and election authorities for constructing votes are available, coercer C cannot know candidates that voters coerced by C had chosen even if the candidates are unique to the voters. In addition, elections can be completed without reelections even when votes were handled illegitimately.

Cite this article:

  • Shinsuke Tamura, Hazim A. Haddad, Nazmul Islam, Kazi Md. Rokibul Alam. An Incoercible E-Voting Scheme Based on Revised Simplified Verifiable Re-encryption Mix-nets. Information Security and Computer Fraud. Vol. 3, No. 2, 2015, pp 32-38.
  • Tamura, Shinsuke, et al. "An Incoercible E-Voting Scheme Based on Revised Simplified Verifiable Re-encryption Mix-nets." Information Security and Computer Fraud 3.2 (2015): 32-38.
  • Tamura, S. , Haddad, H. A. , Islam, N. , & Alam, K. M. R. (2015). An Incoercible E-Voting Scheme Based on Revised Simplified Verifiable Re-encryption Mix-nets. Information Security and Computer Fraud, 3(2), 32-38.
  • Tamura, Shinsuke, Hazim A. Haddad, Nazmul Islam, and Kazi Md. Rokibul Alam. "An Incoercible E-Voting Scheme Based on Revised Simplified Verifiable Re-encryption Mix-nets." Information Security and Computer Fraud 3, no. 2 (2015): 32-38.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

At a glance: Figures

1. Introduction

E-voting systems are expected to make elections efficient, accurate and economical, but when elections are computerized, voters are faced with serious threats. For example, simple computerization enables election authorities to know correspondences between voters and their votes. Also, entity C that is coercing voter V becomes able to confirm whether V had chosen C’s designating candidate or not. E-voting systems applicable to real elections must satisfy the following requirements.

1. Privacy Correspondences between voters and their votes must be concealed from others including election authorities. It is preferable that voters can conceal also their abstentions from others.

2. Verifiability Anyone including voters and third parties must be able to verify the accuracy of elections, i.e. e-voting schemes must be able to convince anyone that only and all votes from eligible voters had been counted.

3. Fairness Interim election results influence ways voters choose candidates; therefore interim election results must be concealed from anyone including election authorities.

4. Incoercibility To disable entity C that is coercing voter V to confirm that V actually had chosen C’s designating candidate S, e-voting schemes must disable even V itself to identify its vote in election results. Here, C must be disabled to know whether V had chosen S or not even if S is unique to V.

5. Robustness To conduct elections fairly even when relevant entities behave dishonestly, voting schemes must be able to complete elections without reelections or any help of dishonest voters. Here if helps from dishonest voters are required, the schemes cannot complete the election when they disappear.

However, despite that many schemes had been developed, they cannot satisfy all of the above requirements completely [2, 4, 6, 8, 10, 11, 12]. For example, although many schemes satisfy receipt freeness, if entity C that is coercing voter V asks V to choose candidate S that is unique to V, C can easily know whether V had actually chosen S or not. Here, receipt freeness is the base of incoercibility, i.e. it disables C to force V to show its receipt that includes the candidate V had chosen.

This paper modifies simplified verifiable re-encryption mix-net (SVRM) [14] to revised-SVRM, and develops an e-voting scheme that satisfies all the above requirements based on it together with anonymous tag based credentials [13, 15, 16]. An anonymous credential enables voter V to convince others that it is eligible without revealing its identity, and provided that erasable-state voting booths are available, the verifiable feature of revised-SVRM ensures election authorities’ legitimate handling of votes while concealing correspondences between voters and their votes from entities including voters themselves. In addition, the scheme regards votes for candidates that could not obtain enough supports as inferior votes and does not count them in the tallying phase [13]. Then, entity C that is coercing V cannot confirm whether V had chosen C’s designating candidate or not even when the candidate is unique to V. About fairness and robustness, it is easy to satisfy them as same as in other schemes.

In the above, an erasable-state voting booth is a one that disables voters to memorize complete information exchanged between them and election authorities during they are constructing their votes.

2. Security Components

2.1. Simplified Verifiable Re-encryption Mix-net (SVRM)

Re-encryption mix-net M consists of multiple mutually independent mix-servers M1, M2, ---, MQ and MQ, MQ-1, ---, M1 that are arrayed in encryption and decryption stages respectively as shown in Figure 1. Then, M enables entities V1, V2, ---, VN that put their attribute values D1, D2, ---, DN in it to conceal correspondences between them and D1, D2, ---, DN from others including mix-servers [2-7][2].

To conceal the above correspondences, firstly each Vj encrypts its attribute value Dj to {gajmod p, Djy*ajmod p} while using its secret integer aj, and M1, M2, ---, MQ in the encryption stage repeatedly encrypt {gajmod p, Djy*ajmod p} to {gkj*(Q)mod p, Djy*kj*(Q)mod p} by using their secret integers kj(1), kj(2), ---, kj(Q) to be decrypted in the decryption stage. Here, provided that g and p are publicly known appropriate integers (p is a prime number), {x(q), y(q) = gx(q)mod p} is mix-server Mq’s secret decryption and public encryption key pair of an ElGamal encryption function, and <x* = {x(1)+x(2)+ --- +x(Q)}mod p, y* = y(1)y(2)---y(Q)mod p = gx*mod p> is a common secret decryption and public encryption key pair. Also, kj*(q) = aj+kj(1)+kj(2)+ --- +kj(q), and in the remainder, notation mod p is omitted when confusions can be avoided.

In detail, each Mq in the encryption stage calculates {gkj*(q-1)gkj(q) = gkj*(q), Djy*kj*(q-1)y*kj(q) = Djy*kj*(q)} from {gkj*(q-1), Djy*kj*(q-1)} received from Mq-1. After that Mq shuffles its calculation results, and forwards them to Mq+1. In the decryption stage, MQ, MQ-1, ---, M1 decrypt each {gkj*(Q), Djy*kj*(Q) = Djgkj*(Q)∙x*} to {gkj*(Q), Dj}. Namely, each Mq decrypts {gkj*(Q), Djgkj*(Q)∙x*(q)} received from Mq+1 to {gkj*(Q), Djgkj*(Q)∙x*(q)/gkj*(Q)∙x(q) = Djgkj*(Q)∙x*(q-1)}} by using its secret key x(q), and forwards it to Mq-1. Here x*(q) = x(1)+x(2)+ --- +x(q).

Then, no one except Vj can know Vj’s attribute value Dj unless all mix-servers conspire because any one cannot know all integers kj(1), kj(2), ---, kj(Q) or all decryption keys x(1), x(2), ---, x(Q). Entities other than Vj cannot know integer aj either.

However, because integers k1(q), k2(q), ---, kN(q) and decryption key x(q) are known only to Mq and Mq in the encryption stage shuffles its encryption results, no one can notice even when mix-servers encrypt or decrypt attribute values dishonestly. SVRM M* shown in Figure 2 enables any entity E to verify behaviors of mix-servers by preparing the unknown number generation stage [14]. In the following it is assumed that all information sent from each entity Vj and mix-server Mq is publicly disclosed.

Firstly, provided that bj, cj are integers secrets of entity Vj and rj(q) and sj(q) are integers secrets of each mix server Mq, Vj calculates {gbj, cjy*bj} and {gcj, (Djy*)cj}, and forwards them to M1 in the unknown number generation stage. After that each Mq calculates <{gsj*(q-1)gsj(q) = gsj*(q), Rj(q-1)rj(q)y*sj*(q-1)y*sj(q) = Rj(q)y*sj*(q)}, {gRj(q-1)∙rj(q) = gRj(q), (Djy*)Rj(q-1)∙rj(q) = (Djy*)Rj(q)}> from <{gsj*(q-1), Rj(q-1)y*sj*(q-1)}, {gRj(q-1), (Djy*)Rj(q-1)}> calculated by Mq-1. As a result, finally MQ calculates <{gsj*(Q), Rjy*sj*(Q)}, {gRj, (Djy*)Rj}> to forward it to Vj, and Vj constructs triplet E0(Dj) = <{gaj, Djy*aj}, {gsj*(Q), Rjy*sj*(Q)}, {gRj, DjΛDjRjy*Rj = DjRj+Λy*Rj}> to put in mix-net M*. Where, Λ is a publicly known constant integer, sj*(q) = bj+sj(1)+sj(2)+ --- +sj(q), Rj(q) = cjrj(1)rj(2) --- rj(q) and Rj = Rj(Q).

About mix-servers M1, M2, ---, MQ in the encryption stage, they repeatedly encrypt E0(Dj) to triplet EQ(Dj) = <{gkj*(Q), Djy*kj*(Q)}, {guj*(Q), Rjy*uj*(Q)}, {gvj*(Q), DjRj+Λy*vj*(Q)}> while shuffling its all encryption results as same as in Figure 1, and MQ, MQ-1, ---, M1 in the decryption stage decrypt it to F0(Dj) = <{gkj*(Q), Dj}, {guj*(Q), Rj}, {gvj*(Q), DjRj+Λ}>. Namely, Mq in the encryption stage calculates Eq(Dj) = <{gkj*(q), Djy*kj*(q)}, {guj*(q), Rjy*uj*(q)}, {gvj*(q), DjRj+Λy*vj*(q)}> from Eq-1(Dj) = <{gkj*(q-1), Djy*kj*(q-1)}, {guj*(q-1), Rjy*uj*(q-1)}, {gvj*(q-1), DjRj+Λy*vj*(q-1)}> calculated by Mq-1, and Mq in the decryption stage calculates Fq-1(Dj) = <{gkj*(Q), Djgkj*(Q)∙x*(q-1)}, {guj*(Q), Rjguj*(Q)∙x*(q-1)}, {gvj*(Q), DjRj+Λgvj*(Q)∙x*(q-1)}> from Fq(Dj) = <{gkj*(Q), Djgkj*(Q)∙x*(q)}, {guj*(Q), Rjguj*(Q)∙x*(q)}, {gvj*(Q), DjRj+Λgvj*(Q)∙x*(q)}> calculated by Mq+1. Where, uj(q) and vj(q) are secret integers of Mq and uj*(q) = sj*(Q) +uj(1) +uj(2)+ --- +uj(q) and vj*(q) = Rj+vj(1)+vj(2)+ --- +vj(q).

Then, the final decryption results enable M* to convince any verifier E of its legitimate encryptions, decryptions and shuffling. Namely, because each attribute value Dj is finally decrypted to F0(Dj) = <{gkj*(Q), Dj = αj}, {guj*(Q), Rj = βj}, {gvj*(Q), DjRj+Λ = γj}>, at least one mix-server is dishonest when relation αjβj = γj does not hold for some j.

However, each Mq that knows public encryption keys y(1), y(2), ---, y(Q) can easily forge encryption and decryption forms Eq(Dj) and Fq-1(Dj) so that their final decryption result <{gkj*(Q), αj}, {guj*(Q), βj}, {gvj*(Q), γj}> satisfies relation αjβj = γj. M* removes this possibility as below.

Firstly each Mq discloses κq = k1(q)+k2(q)+ --- +kN(q), and verifier E convinces itself that the product of Eq(D1), Eq(D2), ---, Eq(DN) calculated by Mq and that of Eq-1(D1), Eq-1(D2), ---, Eq-1(DN) calculated by Mq-1 are consistent. In detail, E examines relations Gk1(q) = gκqGk1(q-1) and Gk2(q) = y*κqGk2(q-1), and requests Mq to iterate the encryption stage until the relations hold. Where {Gk1(q), Gk2(q)} is a product pair {Gk1(q) = gk1*(q)gk2*(q) -- gkN*(q) = gκ1+κ2+ --- +κq, Gk2(q) = D1y*k1*(q)D2y*k2*(q) --- DNy*kN*(q) = D1D2 --- DNy*κ1+κ2+ --- +κq}. Therefore Gk1(q) = gκqGk1(q-1) and Gk2(q) = y*κqGk2(q-1) necessarily hold if Eq(D1), Eq(D2), ---, Eq(DN) are correct. But if encryption from Eq(Dj) is incorrect, because solving discrete logarithm problems is difficult, Mq that does not know x* cannot find value κq so that Gk1(q) = gκqGk1(q-1) and Gk2(q) = y*κqGk2(q-1) hold [3, 4]. On the other hand, although Mq discloses κq, it can maintain each kj(q) as its secret.

Here, actually Mq can find integer κq even if Eq(Dj) is incorrect when Eq(Dj) is calculated in a specific way, but in this case final decryption result <{gkj*(Q), αj}, {guj*(Q), βj}, {gvj*(Q), γj}> does not satisfy relation αjβj = γj. For example, if Mq encrypts {gkj*(q-1), Djy*kj*(q-1)} in Eq-1(Dj) and {gkh*(q-1), Dhy*kh*(q-1)} in Eq-1(Dh) to {gkj*(q), λDjy*kj*(q)} and {gkh*(q), (1/λ)Dhy*kh*(q)} instead of {gkj*(q), Djy*kj*(q)} and {gkh*(q), Dhy*kh*(q)} (λ is an arbitrarily integer), value κq = k1(q)+k2(q)+ --- +kN(q) still satisfies Gk1(q) = gκqGk1(q-1) and Gk2(q) = y*κqGk2(q-1). However, Mq that does not know Dj, Rj, Dh or Rh cannot calculate {guj*(q), βjy*uj*(q)}, {gvj*(q), γjy*vj*(q)} in Eq(Dj) or {guh*(q), βhy*uh*(q)}, {gvh*(q), γhy*vh*(q)} in Eq(Dh) so that relations γi = (λDj)βj+Λ and γh = (Dh/λ)βj hold.

Secondly to ensure legitimate behaviors of mix-servers in the decryption stage, after M1 having decrypted all attribute values, verifier E calculates products D1D2 --- DN and y*a1+a2+ --- +aN from {gk1*(Q), D1}, ---, {gkN*(Q), DN} in final decryption results F0(D1), ---, F0(DN) and {ga1, D1y*a1}, ---, {gaN, DNy*aN} in initial encryption forms E0(D1), ---, E0(DN), where E can calculate y*a1+a2+ --- +aN as y*a1+a2+ --- +aN = D1y*a1D2y*a2 --- DNy*aN/(D1D2 --- DN). E calculates also Gd from encryption forms EQ(D1), EQ(D2), ---, EQ(DN) as Gd = (D1y*k1*(Q)D2y*k2*(Q) --- DNy*kN*(Q))/(D1D2 --- DN).

Under these settings, E determines mix-servers in the decryption stage are dishonest when relation Gd = y*a1+a2+ --- +aN+κ1+κ2+ --- +κQ does not hold. Namely, apparently Gd must be equal to y*a1+a2+ --- +aN+κ1+κ2+ --- +κQ if EQ(D1), ---, EQ(DN) are correctly decrypted. On the other hand, it is computationally infeasible to find different values that satisfy relation Gd = y*a1+a2+ --- +aN+κ1+κ2+ --- +κQ as the decryption forms. In detail, although Mq can forge Fq-1(Dj) while satisfying Gd = y*a1+a2+ --- +aN+κ1+κ2+ --- +κQ as Mq in the encryption stage calculates {gkj*(q), λDjy*kj*(q)}, it cannot make final decryption form <{gkj*(Q), αj}, {guj*(Q), βj}, {gvj*(Q), γj}> satisfy relation αjβj = γj because each Mq (q > 1) does not know value Dj at a time when it decrypts Fq(Dj). Also, anyone can examine relation Gd = y*a1+a2+ --- +aN+κ1+κ2+ --- +κQ because y* and κ1, κ2, ---, κQ are publicly known.

In the above, mix-server M1 in the decryption stage which calculates final decryption forms can know D1, ---, DN as an exception. But verifier E can detect dishonesties easily if the liable mix-server is M1. Namely, when mix-servers ML, ML-1, ---, M1 (L < Q) disclose their decryption keys x(L), x(L-1), ---, x(1) after all attribute values were decrypted, verification of M1’s behavior is trivial. Nevertheless, correspondences between entities and their attribute values can be concealed because x(L+1), x(L+2), ---, x(Q) are still secrets of ML+1, ML+2, ---, MQ.

Then, encryption and decryption forms Eq(D1), Eq(D2), ---, Eq(DN) and Fq-1(D1), Fq-1(D2), ---, Fq-1(DN) calculated by Mq necessarily satisfy Gk1(q) = gκqGk1(q-1) and Gk2(q) = y*κqGk2(q-1) for each q and Gd = y*a1+a2+ --- +aN+κ1+κ2+ --- +κQ, and E becomes able to detect illegitimately calculated F0(Dj) = <{gkj*(Q), αj}, {gtj*(Q), βj}, {gvj*(Q), γj}> as the violation of relation αjβj = γj.

About entities that are liable for inconsistent decryption results, verifier E identifies them by tracing inconsistent decryption results back to initial encryption forms individually. In detail, provided that F0(Dj) is inconsistent, firstly E asks M1 in the decryption stage to show F1(Dj) from which it had calculated F0(Dj) and to prove correct calculation of F0(Dj). In the same way, E asks each Mq to show Fq(Dj) from which it calculated Fq-1(Dj) and to prove correct calculation of Fq-1(Dj), and determines Mq that cannot show consistent pair {Fq(Dj), Fq-1(Dj)} is dishonest. E asks each Mq also in the encryption stage to show Eq-1(Dj) from which it had calculated Eq(Dj) and to prove correct calculation of Eq(Dj). Then it determines Mq is dishonest when Mq cannot show consistent pair {Eq-1(Dj), Eq(Dj)}.

Here, E can verify the consistency of {Fq(Dj), Fq-1(Dj)}, i.e. consistency between {gkj*(Q), Djgkj*(Q)∙x*(q)} and {gkj*(Q), Djgkj*(Q)∙x*(q-1)} without knowing secret key x(q) by exploiting the scheme of Diffie and Hellman. Firstly, E generates secret integer Ψ, and calculates gkj*(Q)∙Ψ = G* and {Djgkj*(Q)∙x*(q)/Djgkj*(Q)∙x*(q-1)}Ψ = {gkj*(Q)∙x(q)}Ψ. After that it asks Mq to calculate G*x(q) by showing G*, and determines Mq is dishonest when G*x(q) is not equal to {Djgkj*(Q)∙x*(q)/Djgkj*(Q)∙x*(q-1)}Ψ.

Verification of {Eq-1(Dj), Eq(Dj)} is trivial, i.e. Mq can disclose integer kj(q), because its value is changed at every encryption different from secret key x(q). Also, although E must verify behaviors of mix-servers in the unknown number generation stage if mix-servers in the encryption and decryption stages are honest, these verifications are trivial. As same as in the encryption stage each Mq can disclose its secret integers sj(q) and rj(q).

Provided that a dishonest mix-server is not M1 in the encryption stage or a mix-server in the unknown number generation stage, it is also straightforward to recalculate consistent final decryption result F0(Dj) without knowing corresponding entity Vj. But, when M1 in the encryption stage or a mix-server in the unknown number generation stage is dishonest, entities other than Vj may know the correspondence between Vj and Dj, i.e. EQ(Dj) was decrypted already and the above procedure for identifying dishonest mix-servers reaches E0(Dj) that was put by Vj. By the same reason, Vj cannot maintain Dj as its secret when it put Dj illegitimately. M* removes these threats by making Vj anonymous. In addition about the latter threat, Vj itself is responsible for the disclosure of its secrets.

Finally, it must be noted that because y*, ga1+ --- +aN and κ1, κ2, ---, κQ are publicly known, any entity can confirm correct behaviors of SVRM without communicating with mix-servers. Therefore, although Diffie and Hellman scheme that requires interactions between a verifier and mix-servers is necessary to identify dishonest mix-servers, actual efficiency of SVRM is not degraded. Usually mix-servers are honest, i.e. they cannot continue their businesses once their dishonesties are detected.

2.2. Anonymous Tag Based Credential

Provided that A is an authority that issues credentials and Z is a secret integer of entity V, anonymous tag based credential T(A, V, Z) enables V to show its eligibility to any entity E without revealing its identity. In addition, E can force V to calculate used seal UZmod B from given integer U by using integer Z in T(A, V, Z) honestly without knowing Z itself (B is a publicly known appropriate integer associated with T(A, V, Z), and notation mod B is omitted in the following). Then, E can use UZ as an evidence that V had shown T(A, V, Z) to it. Here, actually V shows T(A, V, Z) to E in form T(A, V, Z)W while generating secret integer W. Also, to maintain uniqueness of used seal UZ, V calculates a set of values U1Z, U2Z, ---, UTZ from multiple integers U1, U2, ---, UT.

In conclusion, together with used seal UZ anonymous credential T(A, V, Z) satisfies unforgeability, soundness, anonymity, unlinkability, revocability and verifiability as below [13, 15, 16].

Unforgeability no one other than A can generate valid credentials,

Soundness entities that do not know Z in T(A, V, Z) cannot prove the ownership of T(A, V, Z) to other entity E. In addition, when E illegitimately accepts T(A, V, Z) shown by other entity V* possibly while conspiring with it, A can detect that and identify liable entities,

Anonymity anyone except V cannot identify V from T(A, V, Z)W shown by V,

Unlinkability even if V shows T(A, V, Z) n-times in forms T(A, V, Z)W1, T(A, V, Z)W2, ---, T(A, V, Z)Wn while generating different secret integers W1, W2, ---, Wn, no one except V can know links between them,

Revocability A can invalidate T(A, V, Z) without knowing secrets of honest entities, when its holder V behaved dishonestly while showing T(A, V, Z)W or when A reissued new credential to V as a replacement of T(A, V, Z), and

Verifiability anyone can verify the validity of T(A, V, Z), in other words, entities can verify the validity without knowing any secret of A.

3. Revised-SVRM

To adapt SVRM to e-voting systems this section modifies it to revised-SVRM. Provided that Vj and Dj in Figure 2 are a voter and its vote respectively, SVRM cannot protect Vj from coercer C, who is forcing Vj to choose C’s designating candidate S. Namely, Vj must disclose integers bj, cj and pair <{gbj, cjy*bj}, {gcj, (Djy*)cj}> that it had put in the unknown number generation stage in Figure 2 when C requests. Then, C can know whether Vj actually had chosen S or not by examining the consistency between <{gbj, cjy*bj}, {gcj, (Djy*)cj}> and S. In the same way, C can confirm Vj’s choice also from {gaj, Djy*aj} in E0(Dj).

3.1. Modified Unknown Number Generation Stage

To disable entities to force Vj to reveal attribute value Dj, revised-SVRM modifies the unknown number generation stage as shown in Figure 3. Here, as same as in Figure 2, although there is an exception information sent from mix-servers and each entity Vj is publicly disclosed also in revised-SVRM. The modified unknown number generation stage proceeds as follow.

Figure 3. Modified unknown random number generation stage

1. Each mix-server Mq in the unknown number generation stage generates its secret integers sj(q), uj(q) and rj(q).

2. Each entity Vj generates its secret integers δj1, δj2, δj3, calculates {gδj1, y*δj2, (gy*)δj3}, and sends them to M1. At the same time Vj decomposes its attribute value Dj into a set of values {Dj(1), Dj(2), ---, Dj(Q)} so that product Dj(1)Dj(2) --- Dj(Q) becomes equal to Dj, and sends each Dj(q) to Mq. Here as an exception Vj discloses Dj(q) only to Mq. About δj1, δj2, δj3, no one except Vj can know them from gδj1, y*δj2, (gy*)δj3.

3. M1 calculates pairs {gsj(1), Dj(1)y*sj(1)} and {guj(1), rj(1)y*uj(1)} and triplet {gδj1∙sj(1), y*δj2∙sj(1), (gy*)δj3∙sj(1)}, and sends them to M2.

4. Mq (q > 1) that receives {gsj*(q-1), Dj*(q-1)y*sj*(q-1)}, {guj*(q-1), rj*(q-1)y*uj*(q-1)} and {gδj1sj*(q-1), y*δj2sj*(q-1), (gy*)δj3sj*(q-1)} from Mq-1 calculates pairs {gsj*(q), Dj*(q)y*sj*(q)}, {guj*(q), rj*(q)y*uj*(q)} and triplet {gδj1sj*(q), y*δj2sj*(q), (gy*)δj3sj*(q)}, and forwards them to Mq+1. Where, sj*(q) = sj(1)+ --- +sj(q), uj*(q) = uj(1)+ --- +uj(q), Dj*(q) = Dj(1)Dj(2) --- Dj(q), rj*(q) = rj(1)rj(2) --- rj(q) and Dj*(Q) = Dj, rj*(Q) = Rj.

5. MQ that calculates pairs {gsj*(Q), Djy*sj*(Q)}, {guj*(Q), Rjy*uj*(Q)} and triplet {gδj1sj*(Q) = μj1, y*δj2sj*(Q) = μj2, (gy*)δj3sj*(Q) = μj3} in the previous step forwards the pairs to Vj and M1. MQ sends also {μj1, μj2, μj3} to Vj.

6. Vj which receives {gsj*(Q), Djy*sj*(Q)}, {guj*(Q), Rjy*uj*(Q)} and {μj1, μj2, μj3} confirms that {gsj*(Q), Djy*sj*(Q)} is a correct encryption form of Dj, i.e. gsj*(Q) and y*sj*(Q) (= Djy*sj*(Q)/Dj) in it are calculated as g and y* to the power of same unknown integer sj*(Q).

7. If encryption form {gsj*(Q), Djy*sj*(Q)} is successfully verified, provided that Λ is a publicly known integer and Dj(q) = Dj(q)2, Dj*(q) = (Dj(1)Dj(2) --- Dj(q))2 and Dj = Dj2, each Mq calculates {guj*(Q)Dj*(q), (Rjy*uj*(Q))Dj*(q)} and {guj*(Q)∙Λ∙Dj*(q), (Rjy*uj*(Q))Λ∙Dj*(q)} from {guj*(Q)Dj*(q-1), (Rjy*uj*(Q))Dj*(q-1)} and {guj*(Q)∙Λ∙Dj*(q-1), (Rjy*uj*(Q))Λ∙Dj*(q-1)} calculated by Mq-1 to forward them to Mq+1.

8. Vj calculates {guj*(Q)∙Dj∙(Dj+Λ)}, (Rjy*uj*(Q))Dj∙(Dj+Λ)} from {guj*(Q)Dj*(Q), (Rjy*uj*(Q))Dj*(Q)} and {guj*(Q)∙Λ∙Dj*(Q), (Rjy*uj*(Q))Λ∙Dj*(Q)} sent by MQ.

9. Vj verifies legitimate calculation of {guj*(Q)∙Dj∙(Dj+Λ), (Rjy*uj*(Q))Dj∙(Dj+Λ)} and constructs initial encryption form E0*(Dj) = <{gsj*(Q), Djy*sj*(Q)}, {guj*(Q), Rjy*uj*(Q)}, {guj*(Q)∙Dj∙(Dj+Λ), (Rjy*uj*(Q))Dj∙(Dj+Λ)}> to put in the encryption stage.

Then, no one can know integer uj*(Q) or Rj unless all mix-servers conspire. Therefore, entities cannot calculate Dj from pair {guj*(Q), guj*(Q)∙Dj∙(Dj+Λ)} or {Rjy*uj*(Q), (Rjy*uj*(Q))Dj∙(Dj+Λ)} even if they examine every possible value of Dj. In addition, each Dj(q) sent to Mq is a secret of Vj and Mq, and as a result, Vj can conceal Dj even from entity C that is coercing it if erasable-state voting booths are available. Namely, at a time when C asks Vj to disclose Dj, Vj can convince C that any value S is consistent with E0*(Dj). Here, an erasable-state voting booth is a one of which memory states are initialized after an entity in it exits. It also disables entities to record the information that they had received and generated in it. This means Vj does not need to reply with the correct value when it is asked about Dj by others.

Nevertheless both Vj and mix-servers can confirm that E0*(Dj) finally generated by Vj is legitimate, i.e. Vj verifies them as below and components of E0*(Dj) put by Vj were calculated by mix-servers themselves. Although Vj and Mq can construct inconsistent E0*(Dj) if they conspire, this dishonesty can be disabled by making Vj anonymous, i.e. among attribute values of other anonymous entities Mq cannot identify Vj’s one.

About the verification of {gsj*(Q), Djy*sj*(Q)} at step 6, Vj can verify it by confirming relations gsj*(Q)∙δj1 = μj1, y*sj*(Q)∙δj2 = μj2 and (gsj*(Q)y*sj*(Q))δj3 = μj3 through the scheme of Diffie and Hellman. Namely, because discrete logarithm problems are difficult to solve mix-servers that do not know δj1, δj2 or δj3 must calculate gsj*(Q) and y*sj*(Q) by using same sj*(Q) to satisfy the above relations. Verification of {guj*(Q)∙Dj∙(Dj+Λ), (Rjy*uj*(Q))Dj∙(Dj+Λ)} at step 9 is easy; for Vj that knows Dj and Λ it is trivial to confirm that guj*(Q)∙Dj∙(Dj+Λ) and (Rjy*uj*(Q))Dj∙(Dj+Λ) in it are calculated as guj*(Q) and Rjy*uj*(Q) to the power of Dj(Dj+Λ), i.e. {guj*(Q)∙Dj∙(Dj+Λ), (Rjy*uj*(Q))Dj∙(Dj+Λ)} is a consistent encryption form of RjDj∙(Dj+Λ).

3.2. Encryption and Decryption Stages

Mix-servers in the encryption and decryption stages behave in the same way as in Figure 1. Namely, each Mq in the encryption stage encrypts Eq-1*(Dj) = <{gkj*(q-1), Djy*kj*(q-1)}, {gvj*(q-1), Rjy*vj*(q-1)}, {gwj*(q-1), RjDj∙(Dj+Λ)y*wj*(q-1)}> received from Mq-1 to Eq*(Dj) = <{gkj*(q), Djy*kj*(q)}, {gvj*(q), Rjy*vj*(q)}, {gwj*(q), RjDj∙(Dj+Λ)y*wj*(q)}>. And Mq in the decryption stage receives Fq*(Dj) = <{gkj*(Q), Djgkj*(Q)∙x*(q)}, {gvj*(Q), Rjgvj*(Q)∙x*(q)}, {gwj*(Q), RjDj∙(Dj+Λ)g*wj*(q)∙x*(q)}> from Mq+1, and while using decryption key x(q) decrypts it to Fq-1*(Dj) = <{gkj*(Q), Djgkj*(Q)∙x*(q-1)}, {gvj*(Q), Rjgvj*(Q)∙x*(q-1)}, {gwj*(Q), RjDj∙(Dj+Λ)g*wj*(q)∙x*(q-1)}>. Then, M1 finally decrypts F1*(Dj) to F0*(Dj) = <{gkj*(Q), Dj}, {gvj*(Q), Rj}, {gwj*(Q), RjDj∙(Dj+Λ)}>, and convinces others that F0*(Dj) is legitimate by pair {Rj, RjDj∙(Dj+Λ)}. Here, kj(q), vj(q) and wj(q) are secret integers of Mq, kj*(q) = sj*(Q)+kj(1)+kj(2)+ --- +kj(q), vj*(q) = uj*(Q)+vj(1)+vj(2)+ --- +vj(q), wj*(q) = uj*(Q)Dj(Dj+Λ)+wj(1)+wj(2)+ --- +wj(q) and x*(q) = x(1)+x(2)+ ---+x(q).

3.3. Verifying Behaviors of Revised-SVRM

About illegitimate behaviors in the revised-SVRM, RjDj∙(Dj+Λ) in the 3rd term in Eq*(Dj) means that final decryption result F0*(Dj) = <{gk*(Q), α}, {gv*(Q), β}, {gw*(Q), γ}> must satisfy relation γ = βα∙(α+Λ). By using this relation, although each encryption form Eq*(Dj) differs from Eq(Dj), illegitimate behaviors of revised-SVRM can be detected and liable entities can be identified as same as in the original SVRM. But to verify behaviors in the decryption stage, Mq must disclose also σq = s1(q)+s2(q)+ --- +sN(q) in addition to κq = k1(q)+k2(q)+ --- +kN(q) because Gd in Sec. 3 is calculated as y*k1*(Q)+ --- +KN*(Q).

When compared with the original SVRM, identification of dishonest entities becomes simpler. Namely, because Vj and mix-servers in the unknown number generation stage had mutually confirmed their legitimate behaviors already, examination of behaviors in the unknown number generation stage is not necessary.

4. Revised-SVRM Based Voting Scheme

This section develops a voting scheme while exploiting revised-SVRM, anonymous tag based credentials and erasable-state voting booths. The scheme consists of voters V1, V2, ---, VN, election authority A and mix-servers M1, M2, ---, MQ in the encryption, decryption and unknown number generation stages. Elections proceed through the voter registration, voting, pre-tallying and tallying phases as below.

4.1 Voter Registration

Firstly, each voter Vj shows its identity to election authority A at an entrance of an election site. After that, A gives credential T(A, Vj, Zj) to Vj if it is eligible, and in exchange for the credential Vj issues a receipt to A.

Then, because A knows who is Vj, Vj cannot obtain multiple credentials. On the other hand, the receipt ensures that Vj certainly can obtain its credential, i.e. A must show the receipt issued by Vj to reject Vj’s request.

4.2. Voting
4.2.1. Entering a Voting Booth

Each voter Vj shows its credential T(A, Vj, Zj) to authority A and calculates used seal U0Zj of the credential from publicly known integer U0 defined by A, and if T(A, Vj, Zj) is legitimate and U0Zj was not calculated before, Vj is allowed to enter its choosing voting booth. Then features of credentials and used seals allow only eligible voters to enter voting booths only once.

4.2.2. Vote Construction

In the voting booth, Vj constructs pair E0*(Dj) = <{gsj*(Q), Djy*sj*(Q)}, {guj*(Q), Rjy*uj*(Q)}, {guj*(Q)∙Dj∙(Dj+Λ), (Rjy*uj*(Q))Dj∙(Dj+Λ)}> and E0*(Dj, Ω) = <{gsj*(Q), Γjy*sj*(Q)}, {guj*(Q), Rjy*uj*(Q)}, {guj*(Q)Γj∙(Γj+Λ), (Rjy*uj*(Q))Γj∙(Γj+Λ)}> as an initial encryption form of its vote, and forwards it to mix-server M1 in the encryption stage. Where, Λ is a publicly known constant integer, Rj is an integer no one knows and Dj represents a candidate Vj chooses. Also, provided that each sj(q), uj(q), sj(q) and Ω(q) are Mq’s secret integers, sj*(Q) = sj(1)+ --- +sj(Q), uj*(Q) = uj(1)+ --- +uj(Q), sj*(Q) = sj(1)+ --- +sj(Q), Ω = Ω(1)Ω(2) --- Ω(Q) and Γj = DjΩ.

In detail, Vj decomposes Dj into {Dj(1), Dj(2), ---, Dj(Q)} so that Dj = Dj(1)Dj(2) --- Dj(Q) holds, and informs each mix-server Mq in the unknown number generation stage of Dj(q). After that, jointly with the mix-servers Vj calculates E0*(Dj) as in Sec. 3. About E0*(Dj, Ω), firstly each Mq generates its secret integer Ω(q) and calculates Dj(q)Ω(q) to forward it to Mq+1. Then, Mq* that receives Dj(q)Ω(q)Ω(q+1) ---Ω(q*-1) from Mq*-1 calculates Dj(q)Ω(q)Ω(q+1) ---Ω(q*-1)Ω(q*), and sends it to Mq*+1 (M1 is regarded as MQ+1). As a result, Mq receives Dj(q)Ω = Γj(q) from Mq-1, and Vj and mix-servers can calculate E0*(Dj, Ω) from values Γj(1), Γj(2), ---, Γj(Q) as they calculated E0*(Dj).

In the above, it must be noted that no one knows the value of Ω because only Mq knows Ω(q). Also, Vj can verify legitimate calculation of each Γj(q) through the scheme of Diffie and Hellman by asking mix-servers to calculate Dj(q)ΦΩ from Dj(q)Φ (Φ is Vj’s secret integer).

4.2.3. Vote Approval

Before exiting the voting booth, Vj approves that pair {E0*(Dj), E0*(Dj, Ω)} put in the encryption stage is legitimate. Namely, after confirming that the pair disclosed by M1 is correct, Vj calculates another used seal U1Zj of T(A, Vj, Zj) from publicly known integer U1 defined by A, and A discloses it publicly with U0Zj. Here, used seal U1Zj is Vj’s approval of pair {E0*(Dj), E0*(Dj, Ω)}, i.e. Vj can replace it with new ones until it discloses U1Zj. On the other hand, because only Vj can calculate U1Zj, A can reject Vj’s requests about replacements of the pair after U1Zj is disclosed.

4.2.4. Vote Encryption

Once, {E0*(Dj), E0*(Dj, Ω)} is approved, mix-servers in the encryption stage encrypt it to EQ*(Dj) = <{gkj*(Q), Djy*kj*(Q)}, {gvj*(Q), Rjy*vj*(Q)}, {gwj*(Q), Rj Dj∙(Dj+Λ)y*wj*(Q)}> and EQ*(Dj, Ω) = <{gkj*(Q), Γjy*kj*(Q)}, {gvj*(Q), Rjy*vj*(Q)}, {gwj*(Q), RjΓj∙(Γj+Λ)y*wj*(Q)}> while shuffling their encryption results. Where, provided that kj(q), vj(q), wj(q), kj(q), vj(q) and wj(q) are Mq’s secret integers, kj*(q) = sj*(Q)+kj(1)+ --- +kj(q), vj*(q) = uj*(Q)+vj(1)+ --- +vj(q), wj*(q) = uj*(Q)Dj(Dj+Λ)+wj(1)+ --- +wj(q), kj*(q) = sj*(Q)+kj(1)+ --- +kj(q), vj*(q) = uj*(Q)+vj(1)+ --- +vj(q) and wj*(q) = uj*(Q)Γjj+Λ)+wj(1)+ --- +wj(q).

4.3. Pre-tallying

Votes encrypted in the voting phase are decrypted by mix-servers MQ, MQ-1, ---, M1 in the decryption stage, but they decrypt only selected ones. The pre-tallying phase determines these votes. Namely, mix-servers in this phase decrypt only EQ*(Dj, Ω) in each pair {EQ*(Dj), EQ*(Dj, Ω)}, and as a result only decryption form F0*(Dj, Ω) = <{gkj*(Q), Γj = DjΩ}, {gvj*(Q), Rj}, {gwj*(Q), RjΓj∙(Γj+Λ)}> is disclosed.

Then, election authority A compares disclosed D1Ω, D2Ω, ---, DNΩ, and determines EQ*(Dh) that corresponds to EQ*(Dh, Ω*(Q)) is an inferior vote that will not be decrypted when value DhΩ appears less than the predefined number of times in set {D1Ω, D2Ω, ---, DNΩ}. Here, because no one knows integer Ω anyone cannot know Dj from Dj∙Ω. Decryption of EQ*(Dj, Ω) itself is carried out totally in the same way as in Sec. 3.

4.4. Tallying

Because authority A can determine election winners without decrypting inferior votes, mix-servers in the tallying phase decrypt encryption form EQ*(Dj) only when it corresponds to a non-inferior vote. As a result, voters can conceal correspondences between them and their votes from others even when they are forced to choose candidates unique to them.

As same as EQ*(Dj, Ω), decryption of EQ*(Dj) is carried out as in Sec. 3. But mix-servers do not need to decrypt all non-inferior votes because EQ*(Dj) and EQ*(Dh) are decrypted to same value Dj if EQ*(Dj, Ω) and EQ*(Dh, Ω) were decrypted to DjΩ. Therefore, mix-servers decrypt only 1 encryption form EQ*(Dj) from a set of encryption forms that are accompanied by same value DjΩ.

4.5. Detecting Dishonesties and Identifying Liable Entities

Revised-SVRM used in the developed e-voting scheme enables any entity to detect illegitimately handled votes efficiently as discussed in Sec. 3. It also enables election authority A to identify entities liable for dishonesties without revealing votes of honest voters.

In addition, in cases when mix-servers are determined dishonest, A can force them to correctly reprocess illegitimately handled votes. Namely, because voters and mix-servers in the unknown number generation stage had verified their behaviors mutually, initial encryption forms put in the encryption stage are ensured to be legitimate. Then, once all voters had approved initial encryption forms of their votes, A and mix-servers can reprocess illegitimately handled votes until their decryption results become consistent without reelections.

In the above, even if voter Vj and mix-server Mq in the unknown number generation stage conspire, they cannot put an inconsistent initial encryption form. The reason is that Vj is anonymous and Mq cannot identify Vj’s vote. To handle Vj’s vote illegitimately Mq must take a risk that its dishonesty is revealed, i.e. Vh claims Mq is dishonest if Mq generates an initial encryption form of Vh’s vote inconsistently instead of Vj’s one. In the same way, Vj can protect itself from threats where conspiring mix-server M1 and entity C that coerces Vj know Vj’s vote. In detail, when M1 in the encryption stage encrypts initial encryption form {E0*(Dj), E0*(Dj, Ω)} of Vj inconsistently, the dishonest entity identification procedure reveals the correspondence between final decryption form {F0*(Dj), F0*(Dj, Ω)} and {E0*(Dj), E0*(Dj, Ω)}. But M1 cannot identify {E0*(Dj), E0*(Dj, Ω)} because Vj is anonymous.

5. Features of the Developed Scheme

The e-voting scheme developed based on revised-SVRM satisfies all essential requirements of elections as follow.

Privacy: As discussed in Sec. 3 and 5, no one except voter Vj itself can know candidate Dj that Vj had chosen. But Vj that did not register itself cannot conceal its abstention because voters register themselves by showing their identities. To conceal its abstention from others Vj must register itself and put an invalid vote or leave the election site without entering a voting booth.

Verifiability: Anonymous credential ensures that only eligible entities can put votes, and used seals of credentials disable voters to put votes multiple times. About tallying, all votes put by voters and vote forms handled by mix-servers are publicly disclosed and revised-SVRM is verifiable. Then, anyone including third parties can verify the accuracy of elections.

Fairness: No one can know the interim election results because the scheme does not disclose votes in their plain forms until the end of the pre-tallying phase.

Incoercibility: Voter Vj can conceal candidate Dj in {E0*(Dj), E0*(Dj, Ω)} from C that is coercing it, i.e. because Dj is encrypted by using unknown integers, Vj can declare that {E0*(Dj), E0*(Dj, Ω)} is an encryption form of any candidate S. Also, erasable-state voting booths disable C to obtain enough information from Vj to reconstruct Dj even if C is conspiring with several mix-servers. Because inferior votes are not decrypted, C cannot confirm whether Vj had chosen C’s designating candidate S or not even when S is unique to Vj.

Here because Vj is anonymous, as discussed at the end of Sec. 4.5, C cannot know the correspondence between initial encryption form {E0*(Dj), E0*(Dj, Ω)} and final decryption result {F0*(Dj), F0*(Dj, Ω)} even if it conspires with 1st mix-server M1 in the encryption stage or mix-servers in the unknown number generation stage. In detail, A in the voter registration phase gives credential T(A, Vj, Zj) to Vj just before Vj enters a voting booth, therefore Vj cannot inform C or mix-servers of integer Zj in T(A, Vj, Zj) so that they can identify Vj’s vote.

But it must be noted that C which is forcing Vj to abstain from the election can confirm whether Vj actually had abstained or not by asking Vj to recalculate the used seal Vj had calculated in the voter registration phase. This threat exists also in usual paper based elections, and currently an only way to remove this thereat is to introduce regulations that force all voters to visit election sites regardless that they choose valid candidates or not. Even if election authority A gives 2 anonymous credentials Tα and Tβ to Vj, C can know whether Vj actually had abstain or not. Namely, although Vj can visit an election site without revealing its identity by showing Tβ (where Vj obtains Tβ by showing Tα that it had obtained in advance while showing its identity), C can know Vj even from Tβ if it asks Vj to disclose secrets in Tβ.

Robustness: Because initial encryption form {E0*(Dj), E0*(Dj, Ω)} of a vote put by voter Vj is verified by mix-servers and Vj itself, Vj cannot claim that mix-servers had constructed it illegitimately. Therefore, once encrypted votes are successfully disclosed, revised-SVRM enables reprocessing of votes until final decryption forms are disclosed correctly without reelections.

6. Conclusion

Based on revised-SVRM an e-voting scheme that satisfies all essential requirements of elections was developed, i.e. it satisfies requirements about privacy, verifiability, fairness, incoercibility and robustness. But the scheme assumes state-erasable voting booths. Therefore as one of future works, efficient schemes for implementing state-erasable voting booths must be developed.


[1]  Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Trans. On Information Theory, IT-22(6), 644-654, 1976.
In article      
[2]  D. Boneh and P. Golle, “Almost entirely correct mixing with applications to voting,” ACM Conference on Computer and Communication Security, 68-77, 2002.
In article      View Article
[3]  P. Golle, S. Zhong, D. Boneh, M. Jakobsson and A. Juels, “Optimistic mixing for exit-polls,” Asiacrypt 2002, 451-465, 2002.
In article      View Article
[4]  M. Jakobson, A. Juels and R. Rivest, “Making mix nets robust for electronic voting by randomized partial checking,” USENIX Security 02, 339-353, 2002.
In article      
[5]  L. Nguen, R. Dafavi-Naini and K. Kurosawa, “Verifiable shuffles: A formal model and a Paillier-based efficient construction with provable security,” PKC 2004, 61-75, 2004.
In article      View Article
[6]  B. Lee, C. Boyd, E. Dawson, K. Kim, J. Yang and S. Yoo, “Providing receipt-freeness in mixnet-based voting protocols,” Proceedings of the ICISC ’03, 261-74, 2003.
In article      
[7]  J. Furukawa, “Efficient, Verifiable shuffle decryption and its requirement of unlinkability,” PKC 2004, 319-332, 2004.
In article      View Article
[8]  K. Sampigethaya and R. Poovendran, “A framework and taxonomy for comparison of electronic voting schemes,” Elsevier Computers and Security, 25, 137-153, 2006.
In article      View Article
[9]  S. Weber, “A coercion-resistant cryptographic voting protocol -evaluation and prototype implementation,” Diploma thesis, Darmstadt University of Technology; 2006
In article      
[10]  P. Y. A. Ryan, D. Bismark, J. Heather, S,Schneider and Z. Xia, “A voter verifiable voting system,” IEEE Trans. On Information Forensics and Security, 4(4), 662-673, 2009.
In article      View Article
[11]  K. A. Md Rokibul, S. Tamura, S. Taniguchi and T. Yanase, “An anonymous voting scheme based on confirmation numbers,” IEEJ Trans. EIS. 130(11), 2065-2073, 2010.
In article      View Article
[12]  C. C. Lee, T. Y. Chen, S. C. Lin and M. S. Hwang, “A new proxy electronic voting scheme based on proxy signatures,” Lecture Notes in Electrical Engineering, 164, Part 1 3-12, 2012.
In article      View Article
[13]  S. Tamura, “Anonymous security systems and applications: requirements and solutions,” Information Science Reference, 2012.
In article      View Article
[14]  S. Tamura and S. Taniguchi, “Simplified verifiable re-encryption mix-nets,” Information Security and Computer Fraud, 1(1), 1-7, 2013.
In article      
[15]  S. Tamura and S. Taniguchi, “Enhancement of anonymous tag based credentials,” Information Security and Computer Fraud, 2(1), 10-20, 2014.
In article      
[16]  S. Tamura, “Elements of schemes for preserving privacies in e-society systems,” Lambert Academic Publishing, 2015.
In article      
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn