Cheating Voters and Honest but Curious Authorities

7.5 Cheating Voters and Honest but Curious Authorities

We will now implement some of the NIZK-proofs to our voting protocols. The assumption is as follows:

Assumption 4:The voters are possibly cheating and the authorities are honest but cu-rious.

Since there might be cheating voters, we want to force them to follow the protocol. This can be done by including NIZK proofs to each vote, to assure that each vote casted is a proper vote. When voteri calls for the hash-function, she also include a user identity id(W_i)in the input. This is done in order to prevent vote duplication. How to create and store these user identities, and how they are connected to the unreusability requirement defined in Section 7.1, is out of scope for this thesis. We will just assume that each user has a unique user identity id(W_i) which is known both for the user herself and for the authorities in the counting phase.

We will now discuss how to implement the NIZK-proofs to our voting protocols, and in Section 7.7 we will discuss the security of them. For the yes/no-election we will write the protocol properly. For the other two voting protocols we will use the notation Proof_W

i(statement), where the term statement denotes what the voter wants to prove, andProof_W

i(statement)denotes the output when the voter has created the stated NIZK-proof.

7.5.1 Yes/no-election

Again, this is our most basic protocol. In this protocol we will simply add the “1-out-of-2 is the encryption of0” NIZK-proof described by Figure 7.8 in Section 7.4.2, to each vote casted. This will ensure that the ciphertext is either an encryption of 0 or of 1. The protocol is described in Figure 7.15.

It is easy to see thatc=

v

Y

i=1

ci for all valid votesmi.

114 Chapter 7. An application to electronic voting

Voting protocol: Yes/no-election with cheating voter and semi-honest authority

Set-up Let W be the strict upper bound of voters, and let L= 2. A vote by voterWi

for “no” is represented by m_i = 0 and a vote for “yes” is represented by m_i = 1.

The authorities will be represented byA. Use the encryptions scheme DJN_s, with E_D and D_D as described by Figure 6.1 in Section 6.1.

1. Achooses admissible n=pq.

2. Achoosesdsuch thatdmodn∈Z^∗n andd= 0 modλ(n). “1-out-of-2is the encryption of0” NIZK-proof from Figure 7.8 in Section 7.4.2, with x₁ =c_i, x₂=c_i(n+ 1)⁻¹ and w=r_i .

1.3. Verify z1, z2 according to the “1-out-of-2 is the encryption of 0” NIZK-proof. If true then continue, else stop and set i=i+ 1.

3. Aposts the voting result mand the ciphertextc on the bulletin board.

Figure 7.15: A yes/no voting protocol for cheating voters and honest but curious author-ities.

7.5. Cheating Voters and Honest but Curious Authorities 115

7.5.2 1-out-of-L-election

This voting protocol is very similar to the previous, except that we will use the “ 1-out-of-L is the encryption of 0” NIZK-proof described by Figure 7.10 in Section 7.4.3. The protocol is described in Figure 7.16.

116 Chapter 7. An application to electronic voting

Voting protocol: 1-out-of-L-election with cheating voter and semi-honest authority

Set-up LetW be the strict upper bound of voters, and letLbe the number of candidates.

A vote for candidate numberj∈ {0, . . . , L−1} is represented by the numberW^j. The total votes for candidates (0, . . . , L −1) will be denoted by (v0, . . . , vL−1) respectively. The authorities will be represented byA. Use the encryptions scheme DJN_s, withE_DandD_Das described by Figure 6.1 in Section 6.1, withs≥Llog_nW.

1. Achooses admissible n=pq.

2. Achoosesdsuch thatdmodn∈Z^∗n andd= 0 modλ(n).

Voting phase Each votericasts a vote j_i as follows:

1. Choose randomr_i ∈Z^∗n. 2. Choosej_i ∈ {0, . . . , L−1}.

3. Computec_i =E_D(n, W^ji, r_i).

4. Use “1-out-of-Lis the encryption of 0” NIZK-proof from Figure 7.10, Section 7.4.3, to create

i and if approved then iis added to the setI.

2. Acomputes c=Y

i∈I

c_i whereI is the set of approved votes.

3. Acomputes D_D(d, c) =m=

Figure 7.16: A 1-out-of-L voting protocol for cheating voters and honest but curious authorities.

7.5. Cheating Voters and Honest but Curious Authorities 117

7.5.3 K-out-of-L-election

This voting protocol is very similar to the previous one, except that each voter can vote for several candidates. But for each of the candidates she votes for, she computes the encryption cik =E_D(n, W^jik, rik). By including the “1-out-of-L is the encryption of 0”

NIZK-proof described by Figure 7.10 in Section 7.4.3 to each vote, we are assured that each of this encryptions is a proper vote.

In addition to prove that each vote is a proper one, each voter also has to prove that she did not vote for the same candidate several times. This can be solved by noticing the following:

1. If all the votes are different, then W^jik −W^jit 6= 0 for each pair of votesj_ik 6=j_it. 2. If so, then W^jik −W^jit

W^jik −W^jit−1

= 1.

3. So we have two plaintexts which multiplied equals one, and we can use the NIZK-proof of the relationab=cmodn^s between plaintexts from Section 7.4.4 to prove it.

Now let c_ik, c_it be the corresponding encryptions of W^jik 6=W^jit. Each voter can then do as follows with every pair of their votes:

1. Compute (cik)(cit)⁻¹ which is an encryption of W^jik −W^jit . 2. Compute E_D

n, W^jik −W^jit−1

and E_D(n,1).

3. Use the NIZK-proof of the relation ab = cmodn^s between plaintexts, described by Figure 7.12 in Section 7.4.4, to prove that the plaintext of (c_ik)(c_it)⁻¹ and E_D(n, W^jik −W^jit−1

) multiplies to the plaintext of E_D(n,1). The input for the NIZK-proof will be

118 Chapter 7. An application to electronic voting

• c= 1.

• ra, r_b, rcare the corresponding random variables.

There is a slight difference between the ordinaryab=cmodn^sNIZK-proof, and what we need exactly. The ordinary proof just shows the relation, but we want to be assured that the plaintext of exactly(c_ik)(c_it)⁻¹, multiplied by something known for the prover, equals exactly one, not just an unknown plaintext. Anyone can compute(cik)(cit)⁻¹, so this is easily taken care of. But for them to equal exactly one, we need to add something more.

One idea could be to compute a reference value E_D(n,1) in the set-up phase. But then the random variable of this encryption would have to be public (as the prover needs this value in the NIZK-proof). And this compromise this random variable being a private input for the prover. Another way to solve this is to let the prover choose a random variable and computeE_D(n,1). She can then create a NIZK-proof of the encryption of 0 described by Figure 7.6 in Section 7.6, to prove thatE_D(n,1)(n+ 1)⁻¹ is the encryption of0 and hence E_D(n,1)is the encryption of 1.

The voting protocol is described in Figure 7.17-7.18. Notice that the decision of which of the votes that are accepted depends on the requirements of the election. One case is that all the votes from one voter has to be accepted or else non of them will be accepted.

Another case can be that each vote is accepted independently from wether other votes are accepted or not.

7.5. Cheating Voters and Honest but Curious Authorities 119

Voting protocol: K-out-of-L-election with cheating voter and semi-honest authority

Set-up LetW be the strict upper bound of voters, let L be the number of candidates and letK be the number of candidates each voter can vote for. We will add K−1 dummy candidates to collect votes which are not placed on a real candidate. A vote for candidate number j ∈ {0, . . . , L, . . . , L+K −2} is represented by the numberW^j. The total votes for candidates(0, . . . , L+K−2)will be denoted by (v0, . . . , vL+K−2) respectively. The authorities will be represented by A. Use the encryptions scheme DJN_s, with E_D and D_D as described by Figure 6.1 in Section 6.1, with s≥(L+K−2) log_nW.

1. A chooses admissible n=pq.

2. A choosesdsuch thatdmodn∈Z^∗n and d= 0 modλ(n).

Voting phase Each voteri casts the votesj_ik as follows:

1. Fork∈ {1, . . . , K}:

(a) Choose randomrik ∈Z^∗_n.

(b) Choosejik from {0, . . . , L+K−2}.

(c) Computec_ik =E_D(n, W^jik, r_ik).

(d) Use “1-out-of-L is the encryption of 0” NIZK-proof from Figure 7.10 in Section 7.4.3, to create

Proof_Wi,k c_ik(n+1)^−W0∨· · ·∨c_ik(n+1)^−WL+K−2

is an encryption of0 . 2. For each (K−1)! pair of votes j_ik 6= j_it, k, t ∈ {1, . . . , K}, use “the relation ab = cmodn^s between plaintexts” NIZK-proof from Figure 7.12 in Section 7.4.4, to create

Proof_W

i,kt ab=c wherea, b, cis defined above ,

and “the encryption of0” NIZK-proof from Figure 7.6 in Section 7.6, to create Proof_Wi,1 E_D(n,1)(n+ 1)⁻¹ is an encryption of0

Figure 7.17: A K-out-of-L voting protocol for cheating voters and honest but curious authorities (part 1 of 2).

120 Chapter 7. An application to electronic voting

Counting phase

1. For each1≤i < W Achecksc_ik and the proofs, and validates them. If c_ik is an accepted vote, theni_k is added to the setI.

2. Acomputes c=

K

Y

ik∈I

c_ik.

3. Acomputes D_D(d, c) =m=

L−1

X

j=0

v_jW^j.

4. Posts(v0, . . . , v_L−1)and con the bulletin board.

Figure 7.18: A K-out-of-L voting protocol for cheating voters and honest but curious authorities (part 2 of 2).

In document Applications of Paillier s Cryptosystem. (sider 125-133)