How to Challenge and Cast Your e-Vote

Abstract

An electronic voting protocol provides cast-as-intended verifiability if the voter can verify that her encrypted vote contains the voting options that she selected. There are some proposals of protocols with cast-as-intended verifiability in the literature, but all of them have drawbacks either in terms of usability or in terms of security. In this paper, we propose a new voting scheme with cast-as-intended verifiability which allows to audit the vote to be cast, while providing measures for avoiding coercion by allowing the voter to create fake proofs of the content of her vote. We provide an efficient implementation and formally analize its security properties.

A Security Definitions and Analysis Results

1.1 A.1 Definitions

In this section we define the notions of ballot privacy, and cast as intended verifiability for an electronic voting scheme such as that described in Sect. 3. We take as basis the definitions from [5] and then adapt them to the particularities of our scheme. Other definitions such as strong consistency or strong correctness are available in the full version [19].

Ballot Privacy. It is defined by means of an experiment where an adversary is presented with two experiments and has to be able to distinguish between them. In each experiment the adversary has indirect access to a ballot box which receives the ballots created by honest voters, as well as ballots cast by the adversary itself on behalf of corrupted voters. In the case of honest voters, we let the adversary choose two possible votes which they will use to create their ballots. Which vote is used to cast a voter’s ballot that goes to a specific ballot box depends on the experiment that is taking place.

At the end of the experiment, the adversary is presented with the result of tallying the ballot box, which is the same regardless of the experiment. As noted in [5], revealing the true tally in each experiment would easily allow the adversary to distinguish between both ballot boxes. Additionally, for the votes cast by honest voters, we provide the resulting encryption proof data to the adversary in order to model a coercer which uses it to learn something about the vote. We will use a simulation functionality to generate fake proofs when required.

${{\mathbf {\mathsf{{Exp}}}}}_{\mathcal {A}, V}^{{{\mathbf {\mathsf{{priv}}}}}, \beta }$ :

• 1. Setup phase: The challenger $\mathcal {C}$ sets up two empty bulletin boards $\mathsf {BB}_0$ and $\mathsf {BB}_1$ and runs the $\mathsf {Setup}(1^\lambda )$ algorithm to obtain the election key pair $(pk, sk)$ and the empty list of credentials $\mathsf {ID}$. $\mathcal {A}$ is given access to $\mathsf {BB}_0$ when $\beta =0$ and to $\mathsf {BB}_1$ when $\beta =1$.

• 2. Registration phase: The adversary may make the following query:

  • ${\varvec{\mathcal {O}}}$ Register($\mathtt {id}$): $\mathcal {A}$ provides an identity $\mathtt {id}\not \in \mathsf {ID}$. $\mathcal {C}$ runs $\mathsf {Register}(1^\lambda , \mathtt {id})$, provides the voter key pair $(pk_{\mathtt {id}}, sk_{\mathtt {id}})$ to $\mathcal {A}$, and adds $(\mathtt {id}, pk_{\mathtt {id}})$ to $\mathsf {ID}$.

• 3. Voting phase: The adversary may make the following types of queries:

  • ${\varvec{\mathcal {O}}}$ VoteLR($\mathtt {id}, v_0, v_1$): this query models the votes cast by honest voters. $\mathcal {A}$ provides an identity $\mathtt {id}\in \mathsf {ID}$ and two possible votes $v_0$, $v_1$ $\in V$. The challenger $\mathcal {C}$ does the following:

    • It picks the corresponding $pk_{\mathtt {id}}$ from $\mathsf {ID}$ and executes $\mathsf {CreateVote} (v_0, pk_{\mathtt {id}})$ and $\mathsf {CreateVote}(v_1, pk_{\mathtt {id}})$ which produce the ballots $b^0$ and $b^1$ respectively and their encryption proof data $\sigma _0$ and $\sigma _1$.

    • Then it executes $\mathsf {CastVote}(b^0, sk_{\mathtt {id}}, \mathtt {id})$, $\mathsf {CastVote}(b^1, sk_{\mathtt {id}}, \mathtt {id})$ to obtain the authenticated ballots $b^0_a$ and $b^1_a$, and $\mathsf {ProcessBallot}(BB_0, b^0_a)$ and $\mathsf {ProcessBallot}(BB_1, b^1_a)$. If both processes return 1, the ballot boxes $\mathsf {BB}_0$ and $\mathsf {BB}_1$ are updated with $b^0_a$ and $b^1_a$ respectively. Otherwise, $\mathcal {C}$ stops and returns $\perp$.

    • Finally, $\mathcal {C}$ executes $\mathsf {FakeProof}(b^\beta , sk_{\mathtt {id}}, pk_{\mathtt {id}}, v_{\overline{\beta }})$ and provides $\sigma _\beta$ and the simulated encryption proof data $\sigma _\beta ^*$ to $\mathcal {A}$.

  • ${\varvec{\mathcal {O}}}$ Cast($b_a$): this query models the votes cast by corrupted voters. $\mathcal {A}$ provides an authenticated ballot $b_a$, and then $\mathcal {C}$ executes $\mathsf {ProcessBallot}$ with $b_a$ and each ballot box. If both algorithms return 1, both ballot boxes are updated with $b_a$. Otherwise, $\mathcal {C}$ halts and none of the ballot boxes are updated.

• 4. Counting phase: The challenger runs $\textsf {Tally}(\mathsf {BB}_0, sk)$ and obtains the result r and the tally proof $\varPi$, which are provided to $\mathcal {A}$ in case $\beta =0$. In case $\beta =1$, $\mathcal {C}$ runs $\mathsf {SimProof}(\mathsf {BB}_1, r)$ to obtain $\varPi ^*$, and provides $(r, \varPi ^*)$ to $\mathcal {A}$.

• 5. Output: The output of the experiment is the guess of the adversary for the bit $\beta$.

We say that a voting protocol as defined in Sect. 3 has ballot privacy if there exists an algorithm $\mathsf {SimProof}$ such that for any probabilistic polynomial time (p.p.t.) adversary $\mathcal {A}$, the following advantage is negligible in the security parameter $\lambda$:

$$\textsf {Adv}_{\mathcal {A}}^\textsf {priv}= |\,\text {Pr}[\textsf {Exp}_{\mathcal {A}, V}^{\textsf {priv}, 0} = 1] - \text {Pr}[\textsf {Exp}_{\mathcal {A}, V}^{\textsf {priv}, 1} = 1] \,|$$

Cast-as-Intended Verifiability. A voting system is defined to be cast-as-intended verifiable if a corrupt voting device is unable to cast a vote on behalf of a voter, with a voting option different than the one chosen by the voter, without being detected. In our definition, we consider an adversary who posts ballots in the bulletin board on behalf of honest and corrupt voters. In case of honest voters, they follow the protocol and perform some validations before approving the ballot to be cast. Corrupt voters provide their approval without doing any prior verification.

${{\mathbf {\mathsf{{Exp}}}}}_{\mathcal {A}, V}^{{{\mathbf {\mathsf{{CaI}}}}}}$ :

• 1. Setup phase: The challenger $\mathcal {C}$ runs the $\mathsf {Setup}(1^\lambda )$ algorithm and provides the election key pair $(pk, sk)$ to $\mathcal {A}$. Then it publishes the empty lists of voter credentials $\mathsf {ID}_h$ and $\mathsf {ID}_c$ such that $\mathsf {ID}= (\mathsf {ID}_h \cup \mathsf {ID}_c)$. Finally $\mathcal {A}$ is given read access to $\mathsf {BB}$.

• 2. Registration phase: The adversary may make the following queries:

  • ${\varvec{\mathcal {O}}}$ RegisterHonest($\mathtt {id}$): $\mathcal {A}$ provides an identity $\mathtt {id}\not \in \mathsf {ID}$. The challenger $\mathcal {C}$ runs $\mathsf {Register}(1^\lambda , \mathtt {id})$, and adds $(\mathtt {id}, pk_{\mathtt {id}})$ to $\mathsf {ID}_h$.

  • ${\varvec{\mathcal {O}}}$ RegisterCorrupt($\mathtt {id}$): $\mathcal {A}$ provides an identity $\mathtt {id}\not \in \mathsf {ID}$. The challenger $\mathcal {C}$ runs $\mathsf {Register}(1^\lambda , \mathtt {id})$, and adds $(\mathtt {id}, pk_{\mathtt {id}})$ to $\mathsf {ID}_c$.

• 3. Voting phase: The adversary may make the following types of queries:

  • ${\varvec{\mathcal {O}}}$ VoteHonest($\mathtt {id}, v_i, b, \sigma$): this query models the votes cast by honest voters. $\mathcal {A}$ provides an identity $\mathtt {id}\in \mathsf {ID}_h$, a ballot b, an encryption proof data $\sigma$ and the voting option $v_i$. The challenger $\mathcal {C}$ runs $\mathsf {AuditVote}(v_i, b, \sigma , pk_{\mathtt {id}})$, and only if the result is 1 it provides $sk_{\mathtt {id}}$ to $\mathcal {A}$.

  • ${\varvec{\mathcal {O}}}$ VoteCorrupt($b, \mathtt {id}$): this query models the votes cast by corrupted voters. $\mathcal {A}$ provides a ballot b and an identity $\mathtt {id}\in \mathsf {ID}_c$. $\mathcal {C}$ answers with $sk_{\mathtt {id}}$.

• 4. Output: The adversary submits an authenticated ballot $b_a' = (\mathtt {id}', b', \psi ')$. The output of the experiment is 1 if the following conditions hold:

  • $\mathtt {id}' \in \mathsf {ID}_h$

  • $\mathsf {ProcessBallot}(\mathsf {BB},b_a')=1$

  • $\mathsf {VerifyVote}(\mathsf {BB}, b',\mathtt {id}')=1$

  • $\mathsf {Extract}(b_a'; sk)\ne v_i'$, where $v_i'$ is the voting option submitted by the adversary in the $\mathcal {O}$VoteHonest query.

We say that a voting protocol as defined in Sect. 3 has cast-as-intended verifiability if, given an $\mathsf {Extract}$ algorithm for which the protocol is consistent with respect to $\rho$, the following advantage is negligible in the security parameter $\lambda$ for any probabilistic polynomial time (p.p.t.) adversary $\mathcal {A}$:

$$\textsf {Adv}_{\mathcal {A}}^\textsf {CaI}= |\,\text {Pr}[\textsf {Exp}_{\mathcal {A}, V}^{\textsf {CaI}, 0} = 1]\,|$$

1.2 A.2 Security Analysis Results

In this section we provide the results of our security analysis, which is available in the full version of this paper [19].

Theorem 1

Let $(\mathsf {Gen_e}, \mathsf {Enc}, \mathsf {Dec})$ be an NM-CPA secure encryption scheme and $(\mathsf {GenCRS}, \mathsf {NIZKProve}, \mathsf {NIZKVerify}, \mathsf {NIZKSimulate})$ a NIZKPK which provides zero-knowledge. Then the protocol presented in Sect. 3 satisfies the ballot privacy property.

Theorem 2

Let $(\mathsf {Gen_e}, \mathsf {Enc}, \mathsf {Dec}, \mathsf {EncVerify})$ be a probabilistic encryption scheme, $(\mathsf {GenCRS}, \mathsf {NIZKProve}, \mathsf {NIZKVerify}, \mathsf {NIZKSimulate})$ a NIZKPK which is sound and $(\mathsf {Gen_s}, \mathsf {Sign}, \mathsf {SignVerify})$ an unforgeable signature scheme. Then the protocol presented in Sect. 3 satisfies the cast-as-intended verifiability property.