# Ballot secrecy and ballot independence coincide Ben Smyth, David Bernhard ## Abstract We study ballot independence for election schemes: - We formally define ballot independence as a cryptographic game and prove that ballot secrecy implies ballot independence. - We introduce a notion of controlled malleability and show that it is sufficient for ballot independence. We also show that non-malleable ballots are sufficient, but not necessary, for ballot independence. - We prove that ballot independence is sufficient for ballot secrecy under practical assumptions. Our results show that ballot independence is necessary in election schemes satisfying ballot secrecy. Furthermore, our sufficient conditions enable simpler proofs of ballot secrecy. 0 # Introduction Voters should be able to express their free will in elections without fear of retribution; this property is known as privacy. Cryptographic formulations of privacy depend on the specific setting and *ballot secrecy* (Delaune, Kremer, and Ryan 2006; Backes, Hriţcu, and Maffei 2008; Cortier and Smyth 2013) has emerged as a *de facto* standard privacy requirement of election schemes. - *Ballot secrecy.* A voter’s vote is not revealed to anyone. Ballot secrecy provides privacy in an intimidation-free environment and stronger properties such as *receipt-freeness* and *coercion resistance* (Delaune, Kremer, and Ryan 2009) provide privacy in environments where intimidation may occur. Bernhard *et al.* (Bernhard et al. 2011; Bernhard, Pereira, and Warinschi 2012b, 2012a) propose a cryptographic formalisation of ballot secrecy. However, we show that their definition allows election schemes that reveal voters’ votes to be proven secure and we strengthen the definition to prevent this issue. *Ballot independence* (Gennaro 1995; Cortier and Smyth 2013) is seemingly related to ballot secrecy. - *Ballot independence.* Observing another voter’s interaction with the election system does not allow a voter to cast a meaningfully related vote. Indeed, Cortier and Smyth (Cortier and Smyth 2013, 2011; Smyth and Cortier 2011) attribute a class of ballot secrecy attacks to the absence of ballot independence. However, ballot independence has not been formally defined and its relationship with ballot secrecy is unknown. We provide a definition of ballot independence and show that ballot secrecy and ballot independence coincide in practical settings. In traditional paper-based elections, physical mechanisms can be used to achieve privacy, for instance, ballots are completed in isolation inside polling booths, placed into locked ballot boxes, and mixed with other ballots before tallying. (See Schneier (Schneier 2013) for a detailed, informal security analysis of Papal elections.) By comparison, the provision of ballot secrecy is more difficult in end-to-end verifiable election schemes, since ballots are posted on publicly readable bulletin boards. Nonetheless, ballot secrecy is a *de facto* standard property of election schemes and, hence, must be satisfied. The aforementioned physical mechanisms also provide an assurance of ballot independence in paper-based elections, however, the motivation for election schemes satisfying ballot independence is unclear, indeed, Bulens, Giry & Pereira (Bulens, Giry, and Pereira 2011, sec. 3.2) question whether ballot independence is a desirable property of election schemes and highlight the investigation of voting schemes which allow the submission of related votes whilst preserving ballot secrecy as an interesting research direction. Moreover, in the context of the Helios (Adida 2008; Adida et al. 2009) election scheme, Desmedt & Chaidos (Desmedt and Chaidos 2012) present a protocol which allows Bob to cast the same vote as Alice, with Alice’s cooperation, and claim that Bob cannot learn Alice’s vote. In this paper, we study the relationship between ballot secrecy and ballot independence and show that the two properties coincide in practical settings. #### Contribution and Outline. In Section 3 we show that the definition of ballot secrecy by Bernhard *et al.* allows election schemes that reveal voters’ votes to be proven secure and we present a stronger definition of ballot secrecy to prevent this issue. In Section 4 we propose a definition of ballot independence and give sufficient conditions to achieve this notion, including a definition of controlled-malleable encryption. In Section 5 we prove that ballot secrecy implies ballot independence, thereby providing an argument to end the ballot independence debate: ballot independence is a necessary property of election schemes (assuming ballot secrecy is required). In addition, we critique (Section 5.1) the results by Desmedt & Chaidos and argue that their security results do not support their claims. In Section 6 we present a practical class of election schemes (which includes Helios) for which ballot secrecy and ballot independence coincide. #### Related work. The concept of independence was introduced by Chor *et al.* (Chor et al. 1985) and studied in the context of election schemes by Gennaro (Gennaro 1995). Cortier and Smyth (Cortier and Smyth 2011, 2013; Smyth and Cortier 2011) have discovered attacks on ballot secrecy in several election schemes and considered the relationship to independence (Cortier and Smyth 2013, sec. 7); their evidence suggests ballot secrecy implies ballot independence in homomorphic voting systems such as Helios. However, Cortier & Smyth did not make any formal claims, because ballot independence had not been formally defined. By comparison, in this paper, we present a formal definition of ballot independence and prove that ballot secrecy implies ballot independence. Bernhard, Pereira & Warinschi (Bernhard, Pereira, and Warinschi 2012b) show that a non-malleable encryption scheme is sufficient to build an election scheme satisfying ballot secrecy and our work generalises their result. # Preliminaries We adopt standard notation for the application of probabilistic algorithms: if $A$ is a probabilistic algorithm, then $A(x_1,\dots,x_n; r)$ is the result of running $A$ on input $x_1,\dots,x_n$ and coins $r$. We let $y \leftarrow A(x_1,\dots,x_n)$ denote picking $r$ at random and assigning the output of $A(x_1,\dots,x_n;r)$ to the variable $y$. If $S$ is a finite set, then $x\leftarrow S$ assigns a uniformly chosen element of $S$ to $x$. If $\alpha$ is neither a probabilistic algorithm nor a set, then $x\leftarrow\alpha$ assigns $\alpha$ to $x$. Vectors are denoted using boldface, for example, ${\bf x}$. We extend set membership notation to vectors: we write $x\in{\bf x}$ (respectively, $x\not\in{\bf x}$) if $x$ is an element (respectively, $x$ is not an element) of the vector $\bf x$. ## Non-malleable encryption Let us recall the standard syntax for *asymmetric encryption schemes*.
An *asymmetric encryption scheme* is a triple of efficient algorithms $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ such that: - The *key generation algorithm* $\mathsf{Gen}$ takes a security parameter $1^n$ as input and outputs a key pair $(\mathit{pk},\mathit{sk})$, where $\mathit{pk}$ is a public key and $\mathit{sk}$ is a private key. - The *encryption algorithm* $\mathsf{Enc}$ takes a public key $\mathit{pk}$ and message $m$ as input, and outputs a ciphertext $c$. - The *decryption algorithm* $\mathsf{Dec}$ takes a private key $\mathit{sk}$ and ciphertext $c$ as input, and outputs a message $m$ or the special symbol $\perp$ denoting failure. Moreover, the scheme must be correct: for all $(\mathit{pk},\mathit{sk}) \leftarrow\mathsf{Gen}(1^n)$, we have for all messages $m$ and ciphertexts $c\leftarrow \mathsf{Enc}_{\mathit{pk}}(m)$, that $\mathsf{Dec}_{\mathit{sk}}(c) = {m}$ with overwhelming probability.
*Non-malleability* (Dolev, Dwork, and Naor 1991, 2000; Bellare et al. 1998) is a standard computational security model used to evaluate the suitability of encryption schemes. Intuitively, if an encryption scheme satisfies non-malleability, then an adversary is unable to construct a ciphertext *“meaningfully related"* to a challenge ciphertext, thereby capturing the idea that ciphertexts are tamper-proof. 1 This notion can be captured by a pair of cryptographic games – namely, $\textsf{Succ}_{\mathcal A,\Pi}^{\textrm{CPA}}$ and $\textsf{Succ}_{\mathcal A,\Pi,\$}^{\textrm{CPA}}$ – between an adversary and a challenger. The first three steps of both games are identical. First, the challenger constructs a key pair $(\mathit{pk},\mathit{sk})$. Secondly, the adversary $\mathcal A$ executes the algorithm $A_1$ on the public key $\mathit{pk}$ and outputs the pair $(M,s)$, where $M$ is a sampling algorithm for some message space and $s$ is some state information. Thirdly, the challenger randomly selects a plaintext $x$ from the message space; at this point, the challenger in $\textsf{Succ}_{\mathcal A,\Pi,\$}^{\textrm{CPA}}$ performs an additional step, namely, the challenger samples a second plaintext $x'$. Fourthly, the challenger constructs a ciphertext $y\leftarrow \mathsf{Enc}_{\mathit{pk}}(x)$. Fifthly, the adversary executes algorithm $A_2$ which outputs a relation $R$ and a vector of ciphertexts ${\bf y}$. Finally, the challenger decrypts ${\bf y}$ and outputs the corresponding plaintexts ${\bf x}$. The encryption scheme satisfies non-malleability if the adversary’s relation $R$ cannot meaningfully relate $x$ and ${\bf x}$. Formally, Definition [def:NM-CPA] recalls the non-malleability game proposed by Bellare *et al.* (Bellare et al. 1998).
Let $\Pi = (\mathsf{Gen},\mathsf{Enc},\allowbreak\mathsf{Dec})$ be an asymmetric encryption scheme, $\mathcal A= ( A_1, A_2)$ be an adversary, and $$\textsf{NM-CPA}_{\mathcal A, \Pi}(n):= |\textsf{Succ}_{\mathcal A,\Pi}^{\textrm{CPA}}(n) - \textsf{Succ}_{\mathcal A,\Pi,\$}^{\textrm{CPA}}(n)|$$ where $\textsf{Succ}_{\mathcal A,\Pi}^{\textrm{CPA}}(n)$ and $\textsf{Succ}_{\mathcal A,\Pi,\$}^{\textrm{CPA}}(n)$ are defined below, and $n$ is a security parameter. $$\begin{gathered} \textsf{Succ}_{\mathcal A,\Pi}^{\textrm{CPA}}(n) = \mathit{Pr}[ (\mathit{pk},\mathit{sk}) \leftarrow \mathsf{Gen}(1^n);\; (M,s) \leftarrow A_1(\mathit{pk});\\ x \leftarrow M;\; y \leftarrow \mathsf{Enc}_{\mathit{pk}}(x);\; (R,{\bf y}) \leftarrow A_2(M,s,y);\\ {\bf x} \leftarrow \mathsf{Dec}_{\mathit{sk}}({\bf y}) : y\not\in{\bf y} \mathrel\wedge {\perp} \not\in{\bf x} \mathrel\wedge R(x,{\bf x})] \end{gathered}$$ $$\begin{gathered} \textsf{Succ}_{\mathcal A,\Pi,\$}^{\textrm{CPA}}(n) = \mathit{Pr}[ (\mathit{pk},\mathit{sk}) \leftarrow \mathsf{Gen}(1^n);\; (M,s) \leftarrow A_1(\mathit{pk});\\ x,x' \leftarrow M;\; y \leftarrow \mathsf{Enc}_{\mathit{pk}}(x);\; (R,{\bf y}) \leftarrow A_2(M,s,y);\\ {\bf x} \leftarrow \mathsf{Dec}_{\mathit{sk}}({\bf y}) : y\not\in{\bf y} \mathrel\wedge {\perp} \not\in{\bf x} \mathrel\wedge R(x',{\bf x})] \end{gathered}$$ In the above games we insist that the message space is valid (that is, $|x| = |x'|$ for any $x,x'\leftarrow M$ given non-zero probability in the message space) and samplable in polynomial time, and the relation $R$ is computable in polynomial time. We say $\Pi$ satisfies $\textsf{NM-CPA}$ if for all probabilistic polynomial-time adversaries $\mathcal A$ and security parameters $n$, there exists a negligible function $\mathsf{negl}$ such that $\textsf{NM-CPA}_{\mathcal A, \Pi}(n)\leq \mathsf{negl}(n)$.
# Election schemes and ballot secrecy Based upon Bernhard *et al.* (Bernhard et al. 2011; Bernhard, Pereira, and Warinschi 2012b, 2012a), we define a syntax for *election schemes* as follows.
An *election scheme* is a tuple of efficient algorithms $(\mathsf{Setup},\mathsf{Vote},\mathsf{BB},\mathsf{Tally})$ such that: - The *setup algorithm* $\mathsf{Setup}$ takes a security parameter $1^n$ as input and outputs a bulletin board $\mathfrak{bb}$, vote space $\mathfrak m$, public key $\mathit{pk}$, and private key $\mathit{sk}$, where $\mathfrak{bb}$ is a multiset and $\mathfrak m$ is a set. - The *vote algorithm* $\mathsf{Vote}$ takes a public key $\mathit{pk}$ and vote $v\in\mathfrak m$ as input, and outputs a ballot $b$. - The *bulletin board algorithm* $\mathsf{BB}$ takes a bulletin board $\mathfrak{bb}$ and ballot $b$ as input, where $\mathfrak{bb}$ is a multiset. It outputs $\mathfrak{bb}\cup\{b\}$ if successful (i.e., $b$ is added to $\mathfrak{bb}$) or $\mathfrak{bb}$ to denote failure (i.e., $b$ is not added). - The *tally algorithm* $\mathsf{Tally}$ takes a private key $\mathit{sk}$ and bulletin board $\mathfrak{bb}$ as input, where $\mathfrak{bb}$ is a multiset. It outputs a multiset $\mathfrak v$ representing the election result if successful or the empty set $\emptyset$ to denote failure, and auxiliary data $\mathit{aux}$. Moreover, the scheme must satisfy the following correctness property: for all parameters $(\mathfrak{bb}_0,\mathfrak m,\mathit{pk},\mathit{sk}) \leftarrow \mathsf{Setup}(1^n)$, votes $v\in\mathfrak m$, multisets $\mathfrak{bb}$, ballots $b\gets\mathsf{Vote}_{\mathit{pk}}(v)$, bulletin boards $\mathfrak{bb}'\leftarrow\mathsf{BB}(\mathfrak{bb},b)$ and tallying data $(\mathfrak v, \mathit{aux}) \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb})$ and $(\mathfrak v', \mathit{aux}') \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb}')$, we have with overwhelming probability that $\mathfrak{bb}' = \mathfrak{bb}\cup \{b\}$ and if $\mathfrak v\not= \emptyset$, then $\mathfrak v' = \mathfrak v\cup \{v\}$ and $|\mathfrak v| = |\mathfrak{bb}|$, otherwise, $\mathfrak v' = \emptyset$.
In comparison with earlier presentations by Bernhard *et al.*, Definition [def:election] is stricter, since we explicitly define the bulletin board and election result as multisets. Moreover, the correctness condition, asserting that the election result corresponds to the multiset of votes cast, is new. Although the correctness condition restricts the applicability of our definition – for example, we cannot model schemes with weighted votes nor schemes which only reveal the winning candidate (as opposed to the number of votes for each candidate) – we believe it is useful for simplicity. In addition, there are some minor differences in error handling and we merge some functionality into a single function. We demonstrate the applicability of our definition by recalling the construction (Definition [def:mv]) for election schemes proposed by Bernhard *et al.* (Bernhard et al. 2011; Bernhard, Pereira, and Warinschi 2012b). We stress that more sophisticated schemes can also be captured – for example, Bernhard *et al.* (Bernhard et al. 2011; Bernhard, Pereira, and Warinschi 2012b, 2012a) model Helios – but the following scheme is sufficient for our purposes.
Given an asymmetric encryption scheme $\Pi = (\mathsf{Gen},\allowbreak\mathsf{Enc},\mathsf{Dec})$, we define the election scheme $\mathsf{Enc2Vote}(\Pi)$ as follows. - $\mathsf{Setup}$ takes a security parameter $1^n$ as input and outputs $(\emptyset,\mathfrak m,\mathit{pk},\mathit{sk})$, where $(\mathit{pk},\mathit{sk})\leftarrow\mathsf{Gen}(1^n)$ and $\mathfrak m$ is the encryption scheme’s message space. - $\mathsf{Vote}$ takes a public key $\mathit{pk}$ and vote $v\in\mathfrak m$ as input, and outputs $\mathsf{Enc}_{\mathit{pk}}(v)$. - $\mathsf{BB}$ takes a bulletin board $\mathfrak{bb}$ and ballot $b$ as input, where $\mathfrak{bb}$ is a multiset. If $b\in\mathfrak{bb}$, then the algorithm outputs $\mathfrak{bb}$ (denoting failure), otherwise, the algorithm outputs $\mathfrak{bb}\cup \{b\}$. - $\mathsf{Tally}$ takes as input a private key $\mathit{sk}$ and a bulletin board $\mathfrak{bb}$, where $\mathfrak{bb}$ is a multiset. It outputs the multiset $\{\mathsf{Dec}_{\mathit{sk}}(b) \mid b\in\mathfrak{bb}\}$ and auxiliary data $\perp$.
Intuitively, given an asymmetric encryption scheme $\Pi$ satisfying $\textsf{NM-CPA}$, the construction $\mathsf{Enc2Vote}(\Pi)$ derives ballot secrecy from $\Pi$ until tallying and the $\mathsf{Tally}$ algorithm maintains ballot secrecy by returning the number of votes for each candidate as an unordered multiset of votes. ### Ballot Secrecy. Ballot secrecy is a *de facto* standard property of election schemes and, based upon Bernhard *et al.* (Bernhard et al. 2011; Bernhard, Pereira, and Warinschi 2012b, 2012a), we formalise a cryptographic game for ballot secrecy (Definition [def:secretElection]). We will describe the differences between our formalisation and earlier presentations after our definition. Informally, our game proceeds as follows. First, the challenger executes the setup algorithm to construct a bulletin board $\mathfrak{bb}_0$, a vote space $\mathfrak m$, a public key $\mathit{pk}$, and a private key $\mathit{sk}$; the challenger also initialises a bulletin board $\mathfrak{bb}_1$ as a copy of $\mathfrak{bb}_0$ and selects a random bit $\beta$. Secondly, the adversary executes the algorithm $A_1$. The algorithm $A_1$ has access to an oracle $\mathcal O_{}$ as follows: $\mathcal O_{}(v_0, v_1)$ allows the adversary to honestly cast a vote $v_0\in\mathfrak m$ on bulletin board $\mathfrak{bb}_0$ and honestly cast a vote $v_1\in\mathfrak m$ on bulletin board $\mathfrak{bb}_1$, where the votes are cast using ballots constructed by the $\mathsf{Vote}$ algorithm; $\mathcal O_{}(b)$ allows the adversary to cast a ballot $b$, where $b$ is constructed by the adversary and might be rejected by the bulletin board; and $\mathcal O_{}()$ returns the bulletin board $\mathfrak{bb}_\beta$. Thirdly, the challenger computes the election result $\mathfrak v$ as follows: if the honestly cast votes on the bulletin board $\mathfrak{bb}_0$ correspond to the honestly cast votes on the bulletin board $\mathfrak{bb}_1$, then the challenger reveals the election result for $\mathfrak{bb}_\beta$, otherwise, the challenger reveals the election result for $\mathfrak{bb}_0$, thereby preventing the adversary from trivially revealing $\beta$ when the honestly cast votes differ. (The distinction between $\mathfrak{bb}_0$ and $\mathfrak{bb}_1$ is trivial when the honestly cast votes differ, because the adversary can test for the presence of honestly cast votes in the election result.) Formally, we introduce the multisets $L_0$ and $L_1$ to record the honestly cast votes on bulletin boards $\mathfrak{bb}_0$ and $\mathfrak{bb}_1$, and model the correspondence between bulletin boards as an equality test on $L_0$ and $L_1$, that is, we compute $(\mathfrak v, \mathit{aux}) \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb}_\alpha)$ such that $\alpha = \beta$, if $L_0 = L_1$, and $\alpha = 0$, otherwise. Finally, the adversary executes the algorithm $A_2$ on the election result $\mathfrak v$ and any state information $s$ provided by $A_1$. The election scheme satisfies ballot secrecy if the adversary has less than a negligible advantage over guessing the bulletin board she interacted with.
Let $\Gamma = (\mathsf{Setup},\mathsf{Vote},\mathsf{BB},\mathsf{Tally})$ be an election scheme, $\mathcal A= (A_1,A_2)$ be an adversary, and $\textsf{IND-SEC}_{\mathcal A, \Gamma}(n)$ be the quantity defined below, where $n$ is the security parameter. $$\begin{gathered} 2 \cdot \mathit{Pr}[ L_0 \gets \emptyset; L_1 \gets \emptyset; (\mathfrak{bb}_0,\mathfrak m,\mathit{pk},\mathit{sk}) \leftarrow \mathsf{Setup}(1^n);\; \mathfrak{bb}_1 \leftarrow \mathfrak{bb}_0;\; \beta \leftarrow \{0,1\};\\ s \leftarrow A_1^{\mathcal O_{}}(\mathfrak m,\mathit{pk});\; (\mathfrak v, \mathit{aux}) \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb}_\alpha): A_2(\mathfrak{bb}_\beta, \mathfrak v, \mathit{aux}, s) = \beta] - 1 \end{gathered}$$ In the above game, $L_0$ and $L_1$ are multisets, the oracle $\mathcal O_{}$ is defined below, and the bit $\alpha$ is defined as follows: if $L_0 = L_1$, then $\alpha = \beta$, otherwise, $\alpha = 0$. - $\mathcal O_{}(v_0,v_1)$ executes $L_0 \gets L_0 \cup \{ v_0 \}; L_1 \gets L_1 \cup \{ v_1 \}; b_0 \leftarrow \mathsf{Vote}_{\mathit{pk}}(v_0); b_1 \leftarrow \mathsf{Vote}_{\mathit{pk}}(v_1); \mathfrak{bb}_0 \leftarrow \mathsf{BB}(\mathfrak{bb}_0,b_0); \mathfrak{bb}_1 \leftarrow \mathsf{BB}(\mathfrak{bb}_1,b_1)$, if $v_0,v_1\in\mathfrak m$. - $\mathcal O_{}(b)$ assigns $\mathfrak{bb}'_\beta \leftarrow \mathfrak{bb}_\beta$, executes $\mathfrak{bb}_\beta \leftarrow \mathsf{BB}(\mathfrak{bb}_\beta,b)$ and if $\mathfrak{bb}_\beta \not=\mathfrak{bb}'_\beta$, then executes $\mathfrak{bb}_{1 - \beta} \leftarrow \mathsf{BB}(\mathfrak{bb}_{1 - \beta},b)$. - $\mathcal O_{}()$ outputs $\mathfrak{bb}_\beta$. We say $\Gamma$ satisfies *ballot secrecy* if for all probabilistic polynomial-time adversaries $\mathcal A$ and security parameters $n$, there exists a negligible function $\mathsf{negl}$ such that $\textsf{IND-SEC}_{\mathcal A, \Gamma}(n)\leq \mathsf{negl}(n)$.
Our game captures a setting where an adversary can cast ballots on behalf of a subset of voters, whom we call dishonest voters, and controls the distribution of votes cast by the remaining voters, whom we call honest voters, but honest voters always cast ballots constructed by the $\mathsf{Vote}$ algorithm. Furthermore, at the end of the election, the adversary obtains the election result. Intuitively, if the adversary loses the game, then the adversary is unable to distinguish between the bulletin boards $\mathfrak{bb}_0$ and $\mathfrak{bb}_1$, hence, the adversary cannot distinguish between an honest ballot $b_0\in\mathfrak{bb}_0$ and an honest ballot $b_1\in\mathfrak{bb}_1$, therefore, voters’ votes cannot be revealed. On the other hand, if the adversary wins the game, then there exists a strategy to distinguish honestly cast ballots. 1 For example, suppose an adversary in control of one dishonest voter can violate ballot secrecy in a referendum with two honest voters, when all voters participate, each voter casts a valid vote, and no auxiliary data is produced (as per the $\mathsf{Enc2Vote}$ construction, we can model the absence of auxiliary data using a constant symbol such as $\perp$). In this setting, we require a vote space $\{v_0,v_1\}$ and the adversary must make three oracle calls, namely, $\mathcal O_{}(v_0,v_1)$, $\mathcal O_{}(v_1,v_0)$, and $\mathcal O_{}(b)$. It follows that the election result will be $\{v_0,v_1,v\}$, where $v$ is the adversary’s vote. Moreover, the adversary must have a strategy to generate $b$ such that the adversary’s vote $v$ is related to either $v_0$ or $v_1$, otherwise, the election results from both bulletin boards will be equal and the adversary cannot win the game. We stress that a unanimous election result 1 – for instance, the election result generated by tallying the bulletin board $\mathfrak{bb}_\beta$ produced by the oracle calls $\mathcal O_{}(v_0,v_1)$, $\mathcal O_{}(v_0,v_1)$, and $\mathcal O_{}(b)$, where $b$ contains the vote $v_\beta$ – will always reveal all voters’ votes and we tolerate this factor in our game by challenging the adversary to guess the bit $\beta$, rather than the distribution of votes. #### Comparing $\textsf{IND-SEC}$ and earlier definitions. In comparison with earlier definitions by Bernhard *et al.* (Bernhard et al. 2011; Bernhard, Pereira, and Warinschi 2012b, 2012a), Definition [def:secretElection] permits $\alpha\in\{0,1\}$, whereas, earlier presentations implicitly insist $\alpha = 0$. It follows that Definition [def:secretElection] allows the adversary to access auxiliary data generated by tallying $\mathfrak{bb}_\beta$, whereas, earlier definitions only allow the adversary to access the auxiliary data generated by tallying $\mathfrak{bb}_0$. Accordingly, earlier definitions implicitly assume that auxiliary data cannot be used to violate ballot secrecy, indeed, this corresponds to the description by Bernhard *et al.* (Bernhard et al. 2011, sec. 2.2): *“\[ballot secrecy\] is satisfied if an adversary \[...\] cannot learn anything about the votes of \[...\] honest voters beyond what can be inferred from the election result."* Unfortunately, however, it is possible that the auxiliary data can reveal voters’ votes. For example, a variant of $\mathsf{Enc2Vote}$ (Definition [def:mv]) could define auxiliary data that maps ballots to decrypted ballots, thereby violating ballot secrecy; indeed, as highlighted in Footnote [footnote], Bernhard, Pereira & Warinschi (Bernhard, Pereira, and Warinschi 2012b) provided such a mapping in their variant of $\mathsf{Enc2Vote}$. As discussed, we permit $\alpha\in\{0,1\}$, rather than $\alpha = 0$, thereby strengthening Definition [def:secretElection] in comparison with earlier definitions and, thus, overcoming the limitations of previous works. # Ballot independence Intuitively, if an election scheme satisfies ballot independence, then an adversary is unable to construct a ballot that will be accepted by the election’s bulletin board *and* be meaningfully related to a non-adversarial ballot from the bulletin board (Cortier and Smyth 2013, sec. 7.2), thereby capturing the notion that accepted ballots are tamper-proof. Building upon inspiration from non-malleable encryption, we formalise ballot independence as a non-malleability game. ## Non-malleability game The concept of non-malleability and first formalisation is due to Dolev, Dwork & Naor (Dolev, Dwork, and Naor 1991, 2000). Bellare *et al.* (Bellare et al. 1998) build upon these results to introduce $\textsf{NM-CPA}$ (Definition [def:NM-CPA]) and based upon $\textsf{NM-CPA}$, we formalise ballot independence (Definition [def:independence]) as a pair of cryptographic games: $\textsf{Succ}_{\mathcal A,\Pi}^{\textrm{BB}}$ and $\textsf{Succ}_{\mathcal A,\Pi,\$}^{\textrm{BB}}$. The first three steps of both games are identical. First, the challenger sets up the keys, vote space, and bulletin board. Secondly, the adversary gets the vote space $\mathfrak m$, the public key $\mathit{pk}$ and the board $\mathfrak{bb}$ as input and must return a distribution $M$ on the vote space. The adversary may also read the board and submit ballots of his own. Thirdly, the challenger samples a vote $v$ from $M$. At this point the two games diverge: in $\textsf{Succ}_{\mathcal A,\Pi}^{\textrm{BB}}$, the challenger constructs a ballot $\mathsf{Vote}_{\mathit{pk}}(v)$ and adds it to the bulletin board; whereas, in $\textsf{Succ}_{\mathcal A,\Pi,\$}^{\textrm{BB}}$, the challenger samples a second vote $v'$ from $M$, constructs a ballot $\mathsf{Vote}_{\mathit{pk}}(v')$ and adds it to the bulletin board. Fourthly, the adversary must compute a relation $R$ which is intended to distinguish the election results produced by the two games. Finally, the challenger tallies the election and evaluates the relation $R$ on the vote $v$ and, after removing the challenge vote, the election result. The adversary’s advantage is the difference between the probabilities that his relation is satisfied in each game.
Let $\Gamma = (\mathsf{Setup},\mathsf{Vote},\mathsf{BB},$$\mathsf{Tally})$ be an election scheme, $\mathcal A=(A_1,A_2)$ be an adversary, and $$\textsf{NM-BB}_{\mathcal A, \Gamma}(n):= |\textsf{Succ}_{\mathcal A,\Gamma}^{\textrm{BB}}(n) - \textsf{Succ}_{\mathcal A,\Gamma,\$}^{\textrm{BB}}(n)|$$ where $\textsf{Succ}_{\mathcal A,\Gamma}^{\textrm{BB}}(n)$ and $\textsf{Succ}_{\mathcal A,\Gamma,\$}^{\textrm{BB}}(n)$ are defined below, and $n$ is the security parameter. $$\begin{gathered} \textsf{Succ}_{\mathcal A,\Gamma}^{\textrm{BB}}(n) = \mathit{Pr}[ (\mathfrak{bb},\mathfrak m,\mathit{pk},\mathit{sk}) \leftarrow \mathsf{Setup}(1^n);\; (M,s) \leftarrow A_1^{\mathcal O_{}}(\mathfrak m,\mathit{pk});\; \\ v \leftarrow M;\; b \leftarrow \mathsf{Vote}_{\mathit{pk}}(v);\; \mathfrak{bb}\leftarrow \mathsf{BB}(\mathfrak{bb},b);\; R \leftarrow A_2^{\mathcal O_{}}(s);\; \\ (\mathfrak v, \mathit{aux}) \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb}) : %\textrm{\textcolor{red}{\sout{$#1\not\in\bb \wedge$}}} R(v,\mathfrak v\backslash\{v\}) ] \end{gathered}$$ $$\begin{gathered} \textsf{Succ}_{\mathcal A,\Gamma,\$}^{\textrm{BB}}(n) = \mathit{Pr}[ (\mathfrak{bb},\mathfrak m,\mathit{pk},\mathit{sk}) \leftarrow \mathsf{Setup}(1^n);\; (M,s) \leftarrow A_1^{\mathcal O_{}}(\mathfrak m,\mathit{pk});\; \\ v,v' \leftarrow M;\; b \leftarrow \mathsf{Vote}_{\mathit{pk}}(v');\; \mathfrak{bb}\leftarrow \mathsf{BB}(\mathfrak{bb},b);\; R \leftarrow A_2^{\mathcal O_{}}(s);\; \\ (\mathfrak v, \mathit{aux}) \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb}) : %\textrm{\textcolor{red}{\sout{$#1\not\in\bb \wedge$}}} R(v,\mathfrak v\backslash\{v'\}) ] \end{gathered}$$ In the above games we let $\mathcal O_{}$ be defined as follows: $\mathcal O_{}(b)$ executes $\mathfrak{bb}\leftarrow \mathsf{BB}(\mathfrak{bb},b)$ and $\mathcal O_{}()$ outputs $\mathfrak{bb}$. Moreover, we insist the vote space sampling algorithm $M$ and the relation $R$ are computable in polynomial time, and for all $v \leftarrow M$ we have $v\in\mathfrak m$. We say $\Gamma$ satisfies $\textsf{NM-BB}$ (or *ballot independence*) if for all probabilistic polynomial-time adversaries $\mathcal A$ and security parameters $n$, there exists a negligible function $\mathsf{negl}$ such that $\textsf{NM-BB}_{\mathcal A, \Gamma}(n)\leq \mathsf{negl}(n)$.
Intuitively, if an adversary wins the game, then the adversary is able to construct a relation $R$ which holds for a challenge ballot $b\leftarrow \mathsf{Vote}_{\mathit{pk}}(v)$ but fails for $b\leftarrow \mathsf{Vote}_{\mathit{pk}}(v')$. However, we must avoid crediting the adversary for trivial and unavoidable relations which hold iff the challenge vote appears in the election result, hence, we remove the challenge vote from the election result. By contrast, if the adversary can derive a ballot containing the challenge vote and the bulletin board accepts such a ballot, then the adversary can win the game. For example, suppose an election scheme allows the bulletin board to accept duplicate ballots and witness that an adversary can win the game as follows, namely, the adversary selects $M$ as a uniform distribution on $\mathfrak m$, calls $\mathcal O_{}(b)$ with the challenge ballot $b$, and defines a relation $R(v,\mathfrak v)$ that holds iff $v\in\mathfrak v$. In this setting, $R(v,\{v\})$ always holds at the end of $\textsf{Succ}_{\mathcal A,\Gamma}^{\textrm{BB}}$, whereas, $R(v,\{v'\})$ holds with probability $1/\mathfrak m$ at the end of $\textsf{Succ}_{\mathcal A,\Gamma,\$}^{\textrm{BB}}$, since $v'$ is sampled independently from $v$. Finally, if an adversary loses the game, then the adversary is unable to construct a suitable relation, hence, there is no ballot which the bulletin board will accept such that the ballot is related to $\mathsf{Vote}_{\mathit{pk}}(v)$ but not $\mathsf{Vote}_{\mathit{pk}}(v')$, therefore, the adversary cannot cast a ballot which is meaningfully related to an honest voter’s ballot. #### Comparing $\textsf{NM-BB}$ and $\textsf{NM-CPA}$. The main distinction between the notion of non-malleability (Definition [def:NM-CPA]) and our definition of ballot independence is: $\textsf{NM-CPA}$ universally quantifies over ciphertexts, whereas, $\textsf{NM-BB}$ quantifies over ballots accepted by the bulletin board. It follows that non-malleability for encryption is intuitively stronger than ballot independence, since non-malleability for encryption insists that the adversary cannot construct ciphertexts meaningfully related to the challenge ciphertext, whereas, ballot independence tolerates meaningfully related ballots, assuming that they are rejected by the bulletin board algorithm $\mathsf{BB}$. For example, suppose an adversary $\mathcal A$ includes the challenge ciphertext in the vector ${\bf y}$ and observe that this adversary cannot win $\textsf{NM-CPA}_{\mathcal A, \Pi}(n)$, due to the constraint $y\not\in{\bf y}$; by comparison, suppose an adversary $\mathcal B$ copies the challenge ballot $b$ and observe that this adversary can win $\textsf{NM-BB}_{\mathcal B, \Gamma}(n)$. Nonetheless, for ballot independence, the bulletin board must not contain meaningfully related ballots and, hence, checking for meaningfully related ballots is a prerequisite of the bulletin board algorithm $\mathsf{BB}$. ### Non-malleable ballots are sufficient. Non-malleability for encryption prevents the adversary from constructing a ciphertext meaningfully related to the challenge ciphertext and, hence, it follows that non-malleable ballots are sufficient for ballot independence. Indeed, we can derive non-malleable ballots in our $\mathsf{Enc2Vote}$ construction using encryption schemes satisfying NM-CPA.
Given an encryption scheme $\Pi$ satisfying $\textsf{NM-CPA}$, the election scheme $\mathsf{Enc2Vote}(\Pi)$ satisfies ballot independence.
In Proposition [prop], it is sufficient for the bulletin board algorithm, defined by $\mathsf{Enc2Vote}(\Pi)$, to reject ballots that already appear on the bulletin board since non-malleability prevents the adversary from creating ballots meaningfully related to honest voters’ votes (except for exact copies). The proof is essentially the same as that of (Bernhard, Pereira, and Warinschi 2012b, Theorem 4.2). 1 More generally, we could adapt the non-malleability game for encryption (Definition [def:NM-CPA]) to a non-malleability game for ballots. In this setting, given an election scheme satisfying our non-malleability game for ballots and such that the bulletin board algorithm rejects duplicates, we believe that the election scheme satisfies ballot independence. Formalising this result is a possible direction for future research. ## Indistinguishability game Our non-malleability game ($\textsf{NM-BB}$) captures an intuitive notion of ballot independence, however, the definition is relatively complex and security proofs in this setting are relatively difficult. Bellare & Sahai (Bellare and Sahai 1999) observed similar complexities with definitions of non-malleability for encryption and show that $\textsf{NM-CPA}$ is equivalent to a simpler, indistinguishability-based notion. In a similar direction, we introduce an indisinguishability game $\textsf{IND-BB}$ for ballot independence and, based upon Bellare & Sahai’s proof, show that our games $\textsf{NM-BB}$ and $\textsf{IND-BB}$ are equivalent. We model ballot independence as an indistinguishability game between an adversary and a challenger (Definition [def:ballotIndependence]). Informally, the game proceeds as follows. First, the challenger initialises the bulletin board $\mathfrak{bb}$, defines the vote space $\mathfrak m$, and constructs a key pair $(\mathit{pk},\mathit{sk})$. Secondly, the adversary executes the algorithm $A_1$ on the public key $\mathit{pk}$ and vote space $\mathfrak m$, and outputs the triple $(v_0,v_1,s)$, where $v_0,v_1 \in \mathfrak m$ and $s$ is some state information. Thirdly, the challenger randomly selects a bit $\beta$, computes a challenge ballot $b$, and updates the bulletin board with $b$. Fourthly, the adversary executes the algorithm $A_2$ which outputs some state $t$. Next, the challenger computes the election result $\mathfrak v$. Finally, the adversary executes the algorithm $A_3$ on the input $t$ and $\mathfrak v\backslash\{v_\beta\}$. The election scheme satisfies ballot independence if the adversary has less than a negligible advantage over guessing the bit $\beta$.
Let $\Gamma = (\mathsf{Setup},\mathsf{Vote},\mathsf{BB},$$\mathsf{Tally})$ be an election scheme, $\mathcal A=(A_1,A_2,A_3)$ be an adversary, $n$ be the security parameter and $\textsf{IND-BB}_{\mathcal A, \Gamma}(n)$ the cryptographic game defined below. $$\begin{gathered} 2 \cdot \mathit{Pr}[ (\mathfrak{bb},\mathfrak m,\mathit{pk},\mathit{sk}) \leftarrow \mathsf{Setup}(1^n);\; (v_0,v_1,s) \leftarrow A_1^{\mathcal O_{}}(\mathfrak m,\mathit{pk});\; \beta\leftarrow\{0,1\};\;\\ b \leftarrow \mathsf{Vote}_{\mathit{pk}}(v_\beta);\; \mathfrak{bb}\leftarrow \mathsf{BB}(\mathfrak{bb},b);\; t\leftarrow A_2^{\mathcal O_{}}(s);\; (\mathfrak v, \mathit{aux}) \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb}) : \\ A_3(t,\mathfrak v\backslash\{v_\beta\}) = \beta] - 1 \end{gathered}$$ In the above game we let $\mathcal O_{}$ be defined as follows: - $\mathcal O_{}(b)$ executes $\mathfrak{bb}\leftarrow \mathsf{BB}(\mathfrak{bb},b)$ - $\mathcal O_{}()$ outputs $\mathfrak{bb}$ Moreover, we insist that $v_0,v_1 \in \mathfrak m$. We say $\Gamma$ satisfies $\textsf{IND-BB}$ (or *ballot independence*) if for all probabilistic polynomial-time adversaries $\mathcal A$ and security parameters $n$, there exists a negligible function $\mathsf{negl}$ such that $\textsf{IND-BB}_{\mathcal A, \Gamma}(n)\leq \mathsf{negl}(n)$.
Intuitively, if an adversary wins the game, then the adversary is able to distinguish between challenge ballots $b\leftarrow \mathsf{Vote}_{\mathit{pk}}(v_0)$ and $b\leftarrow \mathsf{Vote}_{\mathit{pk}}(v_1)$. As per our $\textsf{NM-BB}$ game, we avoid trivial and unavoidable distinctions by removing the challenge vote from the election result. Our ballot independence games are based on standard security models for encryption: $\textsf{NM-BB}$ is based on non-malleability whereas $\textsf{IND-BB}$ game is based on indistinguishability. Bellare and Sahai (Bellare and Sahai 1999) have shown that non-malleability is equivalent to a notion of indistinguishability for encryption and we adapt their proof to show that $\textsf{NM-BB}$ and $\textsf{IND-BB}$ are equivalent.
Given an election scheme $\Gamma$, we have $\Gamma$ satisfies $\textsf{NM-BB}$ if and only if $\Gamma$ satisfies $\textsf{IND-BB}$.
Theorem [thm:equiv] relates the advantage of an adversary casting a vote meaningfully related to an honest voter’s vote to an advantage in guessing the honest voter’s vote, in a setting where the election result does not contain the honest voter’s vote. 1The proof of Theorem [thm:equiv] can be found in the full version of our paper (Smyth and Bernhard 2013). 1 Let $\Gamma = (\mathsf{Setup},\mathsf{Vote},\mathsf{BB},\mathsf{Tally})$. For the forward implication, suppose $\Gamma$ does not satisfy $\textsf{IND-BB}$, hence, for any negligible function $f$, there exists an adversary $\mathcal{A} = (A_1,A_2,A_3)$ and a security parameter $n$ such that $\textsf{IND-BB}_{\mathcal A, \Gamma}(n)> f(n)$, moreover, $\textsf{IND-BB}_{\mathcal A, \Gamma}(n)> 2 \cdot f(n)$, since since doubling a negligible function produces another negligible function. Let us show that $\Gamma$ does not satisfy $\textsf{NM-BB}$, by constructing an adversary $\mathcal B = (B_1,B_2)$ as follows: Algorithm $B_1$. Given input $\mathfrak m$ and $\mathit{pk}$, the algorithm computes $(v_0,v_1,s) \leftarrow A_1^{\mathcal O}(\mathfrak m,\mathit{pk})$ and outputs $(\{v_0,v_1\},(\{v_0,v_1\},s))$. Algorithm $B_2$. Given input $(\{v_0,v_1\},s)$, the algorithm computes $t\leftarrow A_2^{\mathcal O}(s)$, selects some random coins $r$, and outputs the relation $R$ such that $R(v,\mathfrak v)$ holds if $v = v_g$ and fails otherwise, where $g \leftarrow A_3(t,\mathfrak v; r)$. Let us consider executions of $\textsf{Succ}_{\mathcal B,\Pi}^{\textrm{BB}}(n)$ and $\textsf{Succ}_{\mathcal B,\Pi,\$}^{\textrm{BB}}(n)$. - First, $\textsf{Succ}_{\mathcal B,\Pi}^{\textrm{BB}}(n)$, where a single vote $v$ is sampled from $M$. By inspecting the values provided to the embedded instance of $\mathcal A$, we see that the distribution of these values is identical to if $\mathcal A$ were interacting with $\textsf{IND-BB}$ directly. The use of $A_3$ is in a non-black-box manner but this does not matter: it is still invoked exactly one time in the game. Hence, the probability that $A_3$’s output matches the challenger’s bit $\beta$ is equal to the probability that $\mathcal A$ wins the $\textsf{IND-BB}$ game, that is, strictly greater than $(2 \cdot f(n) + 1)/2$. - Secondly, $\textsf{Succ}_{\mathcal B,\Pi,\$}^{\textrm{BB}}(n)$, where two votes $v$ and $v'$ are sampled from $M$. The value $v$ is independent of $A$’s perspective, indeed, $v$ could be sampled after $A_3$ has terminated and immediately before evaluating the relation $R$. It follows immediately that $R$ holds iff $v=v_g$, where $g$ is $A_3$’s output and $g$ is independent of $v$. Hence, the probability that $R$ holds is $1/2$. The advantage of our adversary $\mathcal B$ in $\textsf{NM-BB}$ is therefore strictly greater than $(2 \cdot f(n) + 1)/2 - 1/2 = f(n)$, concluding this direction of the proof by contraposition. For the reverse implication, suppose $\Gamma$ does not satisfy $\textsf{NM-BB}$, hence, for any negligible function $f$ there exists an adversary $\mathcal{A} = (A_1,A_2)$ and a security parameter $n$ such that $\textsf{NM-BB}_{\mathcal A, \Gamma}(n)> 2 \cdot f(n)$. Let us construct an adversary $\mathcal B = (B_1,B_2,B_3)$ against $\textsf{IND-BB}$ as follows: Algorithm $B_1$. Given input $\mathfrak m$ and $\mathit{pk}$, the algorithm computes $(M,s) \leftarrow \linebreak{A_1^{\mathcal O_{}}(\mathfrak m,\mathit{pk})};\; v_0,v_1 \leftarrow M$ and outputs $(v_0,v_1,(v_0,M,s))$. Algorithm $B_2$. Given input $(v_0,M,s)$, the algorithm computes $R \leftarrow A_2^\mathcal{O}(M,s)$ and outputs $(v_0,R)$. Algorithm $B_3$. Given input $(v_0,R)$ and $\mathfrak v$, the algorithm evaluates $R(v_0,\mathfrak v)$ and if the relation holds, then the algorithm outputs $0$, otherwise, the algorithm outputs $1$. If the challenger selects $\beta = 0$ in $\textsf{IND-BB}$, then the embedded adversary $\mathcal A$ sees exactly the same distribution of values as in $\textsf{Succ}_{\mathcal B,\Pi}^{\textrm{BB}}(n)$, otherwise ($\beta = 1$), $\mathcal A$ sees the same distribution as in the second $\textsf{Succ}_{\mathcal B,\Pi,\$}^{\textrm{BB}}(n)$. Let $g$ be $\mathcal B$’s guess in $\textsf{IND-BB}$. The success probability of $B$ is: $$\begin{array}{lcl} \textrm{Pr}[\beta = g ] &=& \textrm{Pr}[\beta = 0] \cdot\textrm{Pr}[g = 0 \mid \beta = 0] + \textrm{Pr}[\beta = 1] \cdot\textrm{Pr}[g = 1 \mid \beta = 1] \\ &=& 1/2 \cdot ( \textrm{Pr}[g = 0 \mid \beta = 0] + \textrm{Pr}[g = 1 \mid \beta = 1] ) \\ &=& 1/2 \cdot ( \textrm{Pr}[ R(v_0, \mathfrak v) ] + (1 - \textrm{Pr}[ R(v_1, \mathfrak v) ]) ) \\ &=& 1/2 + 1/2 \cdot \textsf{NM-CPA}_{\mathcal A, \Pi}(n) \end{array}$$ Since $1/2 + 1/2 \cdot \textsf{NM-CPA}_{\mathcal A, \Pi}(n)> 1/2 + f(n)$, the advantage of $B$ is greater than $f(n)$, concluding the proof. ## Controlled malleability is sufficient Recall that ballot independence tolerates meaningfully related ballots, assuming they are rejected by the bulletin board. It follows intuitively that we can weaken the requirement for an $\textsf{NM-CPA}$ encryption scheme in Proposition [prop], assuming we modify $\mathsf{Enc2Vote}$’s bulletin board algorithm to reject ballots meaningfully related to existing ballots on the bulletin board. We start with a simple example. Given an encryption scheme satisfying $\textsf{NM-CPA}$, we can derive a new encryption scheme by prepending a random bit to all ciphertexts and removing this bit before decryption. This new encryption scheme does not satisfy $\textsf{NM-CPA}$, however, we can derive an election scheme satisfying ballot independence using $\mathsf{Enc2Vote}$ if we modify $\mathsf{Enc2Vote}$’s bulletin board algorithm as follows: given a bulletin board $\mathfrak{bb}$ and ballot $b$, reject $b$ if it is identical to any ballot already on $\mathfrak{bb}$ up to the first bit. This example shows that non-malleable ballots are not necessary for ballot independence. Let us now formalise a notion of *controlled malleability*, denoted $\textsf{NM-CPA}/R$ (pronounced “NM-CPA modulo $R$”), which we will show is sufficient for ballot independence.
Let $\Pi = (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be an asymmetric encryption scheme and $R$ be an efficiently computable equivalence relation on $\Pi$’s ciphertext space. We say that $\Pi$ satisfies NM-CPA/$R$ (or *controlled malleability*) if for all efficient adversaries $\mathcal A$ the following probability is negligible $$\textrm{Pr}\left[ (\mathit{pk},\mathit{sk}) \leftarrow \mathsf{Gen}(1^n); \beta \gets \{0, 1\} \ : \ \mathcal A^{\textup{\textsf{chal}}_\beta, \textup{\textsf{dec}}}(pk) = \beta \right]$$ where the oracles $\textup{\textsf{chal}}$ and $\textup{\textsf{dec}}$ are defined as follows and each oracle may be called once, in any order. - $\textup{\textsf{chal}}_\beta$ takes two messages $m_0$ and $m_1$ of equal length as input, computes $c^* \gets \textup{\textsf{Enc}}_{pk}(m_\beta)$, and outputs $c^*$. - $\textup{\textsf{dec}}$ takes a vector $\mathbf{c}$ of ciphertexts as input. If $\textup{\textsf{chal}}_\beta$ has previously output a ciphertext $c^*$ such that $R(c, c^*)$ holds for some $c\in\mathbf{c}$, then output $\perp$, otherwise, output $\textup{\textsf{Dec}}_{sk}(\mathbf{c})$.
Our definition generalises non-malleability for encryption, in particular, $\textsf{NM-CPA}\linebreak[1] = \textsf{NM-CPA}/R$, when $R$ is the identity. Moreover, we note that our definition could be adapted to a notion of $\textsf{CCA2}/R$ by allowing arbitrarily many decryption queries. The construction $\mathsf{Enc2Vote}$ can be generalised to asymmetric encryption schemes satisfying controlled malleability as follows.
Suppose $\Pi = (\mathsf{Gen},\allowbreak\mathsf{Enc},\mathsf{Dec})$ is an asymmetric encryption scheme and $R$ is an efficiently computable equivalence relation on $\Pi$’s ciphertext space, we define $\mathsf{Enc2Vote}/R(\Pi) = (\mathsf{Setup},\mathsf{Vote},\mathsf{BB},\mathsf{Tally})$ as follows. Let the $\mathsf{Setup}$, $\mathsf{Vote}$ and $\mathsf{Tally}$ algorithms be given by $\mathsf{Enc2Vote}(\Pi)$. The $\mathsf{BB}$ algorithm takes $\mathfrak{bb}$ and $b$ as input, where $\mathfrak{bb}$ is a multiset. If there exists $b'\in\mathfrak{bb}$ such that $R(b,b')$, then $\mathsf{BB}$ outputs $\mathfrak{bb}$, otherwise, $\mathsf{BB}$ outputs $\mathfrak{bb}\cup \{b\}$.
Assuming that the relation $R$ does not relate fresh, honestly generated ciphertexts in $\Pi$’s ciphertext space to other values (Definition [def:sparse]), we can ensure that $\mathsf{Enc2Vote}/R(\Pi)$ satisfies the correctness condition of election schemes and, hence, $\mathsf{Enc2Vote}/R(\Pi)$ is an election scheme satisfying ballot independence by (Proposition [propp]).
Let $\Pi = (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be an asymmetric encryption scheme and $R$ be an efficiently computable equivalence relation on $\Pi$’s ciphertext space. We say $R$ is a *sparse relation* if for all $(pk, sk) \gets \textup{\textsf{Gen}}$, $c$ and $m$, we have $c' \gets \textup{\textsf{Enc}}(m, pk)$ yields $R(c, c') = 0$ with overwhelming probability.
Suppose $\Pi$ is an asymmetric encryption scheme and $R$ is an efficiently computable and sparse equivalence relation on $\Pi$’s ciphertext space such that $\Pi$ satisfies NM-CPA/$R$. We have $\mathsf{Enc2Vote}/R(\Pi)$ satisfies ballot independence.
The proof of Proposition [propp] is similar to the proof of (Bernhard, Pereira, and Warinschi 2012b, Theorem 4.2). 1 Intuitively, we could adapt the controlled malleability game for encryption (Definition [def:controlled]) to a controlled malleability game for ballots. In this setting, given an election scheme satisfying our controlled malleability game for ballots and such that the bulletin board algorithm rejects duplicates, we believe that the election scheme satisfies ballot independence. Moreover, the generalised definition would allow us to consider whether controlled malleability for ballots is necessary for ballot independence. (Clearly such results cannot be considered using controlled malleability for encryption, since this definition excludes election schemes based upon alternative cryptographic primitives, such as commitments, for example.) Formalising this result is a possible direction for future research. ### Design paradigms and discussion. We derive the following design paradigms from our results: 1) use non-malleable ballots (Section 4.1), or 2) identify and reject related ballots using controlled malleability. The latter paradigm is particularly useful when ballots contain malleable data such as voter identities or pseudonyms, since we can tolerate malleability and provide provable security. Moreover, it facilitates more realistic models of election schemes in comparison with earlier work, for example, Bernhard *et al.* (Bernhard et al. 2011; Bernhard, Pereira, and Warinschi 2012b, 2012a) abstractly model Helios ballots as non-malleable ciphertexts, whereas, in practice, Helios ballots embed non-malleable ciphertexts in malleable JavaScript Object Notation (JSON) data structures (this is particularly relevant, since Smyth & Cortier (Smyth and Cortier 2010, sec. 4.1) have shown that the JSON structures introduces vulnerabilities). # Ballot secrecy implies ballot independence In this paper, all election schemes satisfy correctness: the bulletin board algorithm $\mathsf{BB}$ adds honestly constructed ballots to the bulletin board, the tally algorithm $\mathsf{Tally}$ includes honest votes in the election result, and the number of votes in an election result corresponds to the number of ballots (that is, each ballot contains one vote). In this setting, an election scheme satisfying ballot secrecy also satisfies ballot independence.
Given an election scheme 1$\Gamma = (\mathsf{Setup},\mathsf{Vote},\mathsf{BB},\mathsf{Tally})$$\Gamma$ satisfying ballot secrecy, we have $\Gamma$ satisfies ballot independence.
1 The proof is by a standard reduction argument: given a successful $\textsf{IND-BB}$ adversary, we construct an adversary against $\textsf{IND-SEC}$. The single challenge query on $(v_0, v_1)$ becomes a pair of vote queries $\textup{\textsf{Vote}}(v_0, v_1)$ and $\textup{\textsf{Vote}}(v_1, v_0)$, and oracle queries $\mathcal O(b)$ become ballot queries. When we obtain the election outcome from the $\textsf{IND-SEC}$ game, we remove $v_0$ and $v_1$ since this is the distribution that the $\textsf{IND-BB}$ adversary expects. Finally, we show that the advantage translates between games. Theorem [thm:relation] relates an advantage in guessing an honest voter’s vote in a setting where the election result *does not* contain the honest voter’s vote to an advantage in the ballot secrecy game where the election result *does* include the honest voter’s vote. It follows, by Theorem [thm:equiv], that an advantage in casting a vote meaningfully related to an honest voter’s vote translates into an advantage in guessing an honest voter’s vote, hence, we have shown that ballot independence is necessary for ballot secrecy in election schemes defined by Definition [def:election]. 1 The proof of Theorem [thm:relation] can be found in the full version of our paper (Smyth and Bernhard 2013). 1 The proof of Theorem [thm:relation] is standard: by contradiction, we construct an adversary $\mathcal B = (B_1,B_2)$ against $\textsf{IND-SEC}$ from a successful adversary $\mathcal A = (A_1,A_2,A_3)$ against $\textsf{IND-BB}$ such that $\mathcal B$ ensures $\mathcal A$’s perspective of the bulletin board and election result are consistent with $\textsf{IND-BB}$. Before explaining how we ensure that $\mathcal A$’s perspective is consistent, let us briefly review the distinction between $\mathcal A$’s and $\mathcal B$’s perspectives of their respective bulletin board and election result. We first remark that the functionalities provided by $\mathcal A$’s oracle $\mathcal O_{\mathcal A}$ are a subset of those provided by $\mathcal B$’s oracle $\mathcal O_{\mathcal B}$. In $\textsf{IND-BB}$, the adversary $A_1$ expects $\mathcal O_{\mathcal A}() = \mathfrak{bb}$ such that $b\in\mathfrak{bb}$ implies $A_1$ previously called $\mathcal O_{\mathcal A}(b)$. Moreover, adversaries $A_2$ and $A_3$ expect $\mathcal O_{\mathcal A}() = \mathfrak{bb}\cup \{b'\}$ such that $b'$ is the challenge ballot and $b\in\mathfrak{bb}$ implies $A_1$ or $A_2$ previously called $\mathcal O_{\mathcal A}(b)$. Furthermore, $A_3$ observes the election result $\mathfrak v\backslash\{v_\beta\}$, where $v_\beta$ is the challenge vote and $(\mathfrak v, \mathit{aux}) \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb})$. By comparison, the adversary $\mathcal B$ expects $\mathcal O_{\mathcal B}() = \mathfrak{bb}$ such that $b\in\mathfrak{bb}$ implies $\mathcal B$ previously called $\mathcal O_{\mathcal B}(b)$ or $\mathcal O_{\mathcal B}(v_0,v_1)$, and in the latter case the oracle constructed $b = \mathsf{Vote}_{\mathit{pk}}(v_\beta)$. Furthermore, $\mathcal B$ observes the election result $\mathfrak v$, where $(\mathfrak v, \mathit{aux}) \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb}_\alpha)$. It follows immediately that $A_2$ and $A_3$ will observe a challenge ballot on the bulletin board, whereas, $\mathcal B$ will not. In addition, the challenge vote will be removed from the election result observed by $A_3$, whereas no votes are removed from the election result observed by $\mathcal B$. Let us now informally explain how $\mathcal B$ ensures that $\mathcal A$’s perspective of the bulletin board and election result are consistent with $\textsf{IND-BB}$. First, $\mathcal B$ ensures that a challenge ballot appears on the bulletin board observed by adversaries $A_2$ and $A_3$ by calling $\mathcal O_{\mathcal B}(v_0, v_1)$, where votes $v_0$ and $v_1$ are output by $A_1$. Secondly, the adversary $\mathcal B$ calls $\mathcal O_{\mathcal B}(v_1, v_0)$ and inputs the election result $\mathfrak v'\backslash\{v_1,v_0\}$ to $A_3$, where $(\mathfrak v', \mathit{aux}') \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb})$. We remark that tallying after the first step will produce an election result which includes the challenge vote $v_\beta$ and does not correspond to the election result expected by $\mathcal A$; the second step overcomes this problem. Suppose $\Gamma = (\mathsf{Setup},\mathsf{Vote},\mathsf{BB},\mathsf{Tally})$ is an election scheme with ballot secrecy that does not satisfy $\textsf{IND-BB}$, hence for any negligible function $f$ there exists an adversary $\mathcal{A} = (A_1,A_2,A_3)$ and security parameter $n$ such that $\textsf{IND-BB}_{\mathcal A, \Gamma}(n) > f(n)$. We construct an adversary $\mathcal B = (B_1,B_2)$ against $\textsf{IND-SEC}$ as follows. Algorithm $B_1$. Given input $\mathfrak m$ and $\mathit{pk}$, the algorithm proceeds as follows. First, $B_1$ computes $(v_0,v_1,s) \leftarrow A_1^{\mathcal O_{\mathcal A}}(\mathfrak m,\mathit{pk})$, handling any oracle calls from $A_1$ as follows: if $A_1$ calls $\mathcal O_{\mathcal A}(b)$, then $B_1$ calls $\mathcal O_{\mathcal B}(b)$, similarly, if $A_1$ calls $\mathcal O_{\mathcal A}()$, then $B_1$ computes $\mathfrak{bb}\leftarrow\mathcal O_{\mathcal B}()$ and returns $\mathfrak{bb}$ to $A_1$. Secondly, $B_1$ creates and extracts the challenge ballot by computing $\mathfrak{bb}\leftarrow \mathcal O_{\mathcal B}();\mathcal O_{\mathcal B}(v_0,v_1);\mathfrak{bb}'\leftarrow \mathcal O_{\mathcal B}();b\leftarrow \mathfrak{bb}'\backslash \mathfrak{bb}$. Thirdly, $B_1$ computes $t\leftarrow A_2^{\mathcal O_{\mathcal A}}(s)$, handling any oracle calls from $A_2$ as before. Finally, $B_1$ computes $\mathfrak{bb}^\dagger \gets \mathcal O_{\mathcal B}(); \mathcal O_{\mathcal B}(v_1,v_0); \mathfrak{bb}^\ddagger \gets \mathcal O_{\mathcal B}(); b^\dagger \gets \mathfrak{bb}^\ddagger \setminus \mathfrak{bb}^\dagger$ and outputs $(t, b^\dagger)$. Algorithm $B_2$. Given input $\mathfrak v$ and $(t, b^\dagger)$, the algorithm computes $A_3(t, \mathfrak v\setminus \{v_0, v_1\})$ and outputs $A_3$’s guess. The embedded adversary $\mathcal A$ sees the same distribution of all elements as in the $\textsf{IND-BB}$ game for the same value of $\beta$. Indeed, the challenge ballot is computed in the same manner, $\mathcal O_{\mathcal A}()$ produces the expected multiset of ballots (we stress that $b^\dagger$ – namely, the ballot introduced by $B_1$ to ensure that the election result is consistent with $A_3$’s expectations – never appears in a multiset output by $\mathcal O_{\mathcal A}()$, since $b^\dagger$ is added to the bulletin board after all oracle calls by $\mathcal A$), and the election result observed by $A_3$ is as expected. It follows that $\mathcal B$ guesses $\beta$ correctly with the same advantage as $\mathcal A$ and, therefore, $\textsf{IND-SEC}_{B, \Gamma}(n) > f(n)$, concluding our proof. ## Critique of Desmedt & Chaidos’s Helios variant Intuitively, Theorem [thm:relation] contradicts the results by Desmedt & Chaidos (Desmedt and Chaidos 2012), who claim to provide a variant of the Helios election scheme which allows Bob to cast the same vote as Alice, with Alice’s cooperation, whilst preventing Bob from learning Alice’s vote. In their protocol, Bob selects Alice’s ballot from the bulletin board and communicates with Alice to generate a new ballot that is guaranteed to contain the same vote as Alice’s. Desmedt & Chaidos’s security claim is true *before the election result is announced*, since Bob gains no advantage in guessing Alice’s vote. However, *after the election result is announced*, the claim is false. We can informally contradict this claim – using results by Cortier & Smyth (Cortier and Smyth 2011, 2013; Smyth and Cortier 2011) – in an election with voters Alice, Bob and Charlie: if Bob casts the same vote as Alice, then Bob can learn Alice’s vote by observing the election result and checking which candidate obtained at least two votes (that is, Bob can learn Alice’s vote when the election result is not unanimous). We believe the erroneous claim by Desmedt & Chaidos is due to an invalid inference from their computational security result. Indeed, although the result (Desmedt and Chaidos 2012, Theorem 1) is correct, their model does not support their claims for real world security: Desmedt & Chaidos consider a passive adversary that cannot observe the election result, whereas, we believe a practical notion of security must consider an *active* adversary who can cast ballots and observe the election result, since this captures the capabilities of an attacker in the real world. Nonetheless, a weaker notion of ballot secrecy may be satisfiable in Desmedt & Chaidos’s variant of Helios, assuming Alice never cooperates with the adversary. Clearly, no claims can be made about Bob’s knowledge of Alice’s vote in this setting. We have shown Desmedt & Chaidos our results and Chaidos agrees with our findings (Chaidos 2013). ## Discussion We have shown that election schemes satisfying ballot secrecy must also satisfy ballot independence. However, we must concede that alternative formalisms of election schemes may permit different results. Indeed, Cortier & Smyth (Cortier and Smyth 2013, sec. 7.1) present a result to the contrary using anonymous channels, which are implicitly excluded from our model. Moreover, our model also excludes settings where the adversary cannot control a majority of voters and places some restrictions on the election result, namely, the election result is captured as a multiset which reveals the number of votes for each candidate. In this setting, an election result can be computed from a partial election result if the votes of the remaining voters are known. This property is implicitly used in our proof of Theorem [thm:relation]1, where we take the election result and challenge vote, and compute the partial election result which removes the challenge vote. On the other hand, some practical election schemes do not have this property. For example, consider an election scheme which announces the winning candidate, but does not provide a breakdown of the votes for each candidate (Benaloh and Yung 1986; Hevia and Kiwi 2002, 2004; Desmedt and Kurosawa 2005). It follows that knowledge of a partial election result can only be used to derive the election result if the adversary controls a majority of voters. Similarly, given an election result and knowledge of a minority of votes, a partial election result which excludes the known votes cannot be derived. In this setting, we believe election schemes can satisfy ballot secrecy but not ballot independence, since casting a minority of related ballots is not sufficient to reveal a voter’s vote. Formal treatment of this case and consideration of whether such schemes are practical is a possible direction for future work. # Sufficient conditions for ballot secrecy The main distinctions between our ballot secrecy ($\textsf{IND-SEC}$) and ballot independence ($\textsf{IND-BB}$) games are as follows. 1. The challenger in our ballot independence game explicitly defines a challenge ballot and adds the ballot to the bulletin board, whereas, the challenger in our ballot secrecy game provides the adversary with an oracle $\mathcal O_{\mathcal B}(\cdot,\cdot)$. The two formulations are similar, indeed, the challenger’s computation $b \leftarrow \mathsf{Vote}_{\mathit{pk}}(v_\beta);\; \mathfrak{bb}\leftarrow \mathsf{BB}(\mathfrak{bb},b)$ is similar to an oracle call $\mathcal O_{\mathcal B}(v_0,v_1)$. Moreover, a hybrid argument will show that it does not matter if we give the adversary only one challenge ballot or many oracle calls. 2. The adversary in our ballot secrecy game has access to the auxiliary data produced during tallying, but the adversary in our ballot independence game does not. The second point distinguishes our two games; Theorem [thm:relation] shows that ballot secrecy is stronger than independence and Footnote [footnote] gives a case where it is strictly stronger: the presentation of the $\mathsf{Enc2Vote}$ construction by Bernhard, Pereira & Warinschi provides ballot independence, but the auxiliary data maps voters to votes, thereby violating ballot secrecy. Nonetheless, by restricting the adversary’s access to auxiliary data we can show that the two games are equivalent (Theorem [proppp]) and, hence, in the absence of auxiliary data, ballot independence is a sufficient condition for ballot secrecy, in particular, $\mathsf{Enc2Vote}$ and $\mathsf{Enc2Vote}/R$ are constructions for election schemes satisfying ballot secrecy.
Suppose $\Gamma = (\mathsf{Setup},\mathsf{Vote},\mathsf{BB},\mathsf{Tally})$ is an election scheme such that there exists a constant symbol $\perp$ and for all parameters $(\mathfrak{bb}_0,\mathfrak m,\mathit{pk},\mathit{sk}) \leftarrow \mathsf{Setup}(1^n)$, multiesets $\mathfrak{bb}$ and tallying data $(\mathfrak v, \mathit{aux}) \leftarrow \mathsf{Tally}_{\mathit{sk}}(\mathfrak{bb})$, we have $\mathit{aux}= \perp$. It follows that $\Gamma$ satisfies ballot secrecy if and only if $\Gamma$ satisfies ballot independence.
1 Suppose $\Gamma$ is an election scheme that does not satisfy $\textsf{IND-BB}$, hence for any negligible function $f$ there exists an adversary $\mathcal{A}$ and security parameter $n$ such that $\textsf{IND-BB}_{\mathcal A, \Gamma}(n) > f(n)$. The adversary $\mathcal B$ defined in the proof of Theorem [thm:relation] is such that $\textsf{IND-SEC}_{B, \Gamma}(n) > f(n)$. It remains to show that ballot independence implies ballot secrecy. Suppose $\Gamma$ is an election scheme that does not satisfy $\textsf{IND-SEC}$, hence for any negligible function $f$ there exists an adversary $\mathcal{B} = (B_1,B_2)$ and security parameter $n$ such that $\textsf{IND-SEC}_{\mathcal B, \Gamma}(n) > f(n)$. By inspection of the game $\textsf{IND-SEC}$, the adversary $B_1$ makes an oracle call $\mathcal O_{\mathcal B}(v_0,v_1)$ for some votes $v_0,v_1$ in the voting scheme’s vote space, hence, there exist adversaries $B_{1,1}$ and $B_{1,2}$ such that $B_1 = s' \leftarrow B_{1,1};\mathcal O_{\mathcal B}(v_0,v_1);B_{1,2}(s')$ and $B_{1,2}$ outputs $s$. We wish to construct an adversary $\mathcal A = (A_1,A_2,A_3)$ against $\textsf{IND-BB}$ out of $\mathcal B$ but the $\textsf{IND-BB}$ game only gives us one opportunity to call the challenge oracle (as the output $v_0, v_1$ of $A_1$). We deal with the $\mathcal O_\mathcal B(\cdot, \cdot)$ calls using a hybrid argument: Let $q$ be an upper bound on the number of $\mathcal O_\mathcal B(\cdot, \cdot)$ queries that $\mathcal B$ makes. Since $\mathcal B$ is efficient, assume that $q$ is polynomial in the security parameter. Let $G_0$ be the $\textsf{IND-SEC}$ game modified such that the bit $\beta$ is always chosen as $0$ and let $G_q$ be the game in which $\beta$ is always $1$; the adversary $\mathcal B$’s advantage against $\textsf{IND-SEC}$ is clearly his distinguishing advantage between $G_0$ and $G_q$. Let $G_i$ for $0 < i < q$ be the $\textsf{IND-SEC}$ game in which the first $i$ queries to $\mathcal O_\mathcal B(\cdot, \cdot)$ are answered as if $\beta = 1$ and the rest as if $\beta = 0$. If $\mathcal B$ has non-negligible advantage in distinguishing $G_0$ from $G_q$ then there must be an $i$ such that $0 \leq i < q$ and $\mathcal B$ distinguishes $G_i$ from $G_{i+1}$ with non-negligible advantage too; more precisely if $\textsf{IND-SEC}_{\mathcal B, \Gamma}(n) = \alpha$ then there must be an $i$ for which the distinguishing advantage is at least $i/q$. Suppose we know such an $i$. We construct $\mathcal A$ as the following adversary. $\textup{\textsf{$A_1$}}$ Receive $\mathfrak m, \mathit{pk}$ from the challenger and run $B_1$ on these inputs; forward $\mathcal O()$ and $\mathcal O(b)$ calls to the challenger and return its replies. Initialise two lists $L_0$ and $L_1$ to be empty. For the first $i$ $\mathcal O_\mathcal B(v_0, v_1)$ calls that $B_1$ makes, create a ballot $b$ for $v_1$ and issue an $\mathcal O(b)$ call to the challenger. Also store the votes $(v_0, v_1)$ by appending them to $L_0$ and $L_1$ respectively. When $A_1$ makes the $i+1$-st two-element call with parameters $v_0, v_1$, suspend the execution of $B_1$, save its state as $s$, add the parameters to the current call to $L_0$ and $L_1$ and return $(v_0, v_1, (s, L_0, L_1))$. $\textup{\textsf{$A_2$}}$ Parse the received state as $(s, L_0, L_1)$. Resume $B_1$ using state $s$ and handle oracle calls as above except that for oracle calls $\mathcal O_\mathcal B(v_0, v_1)$, create a ballot $b$ for $v_0$ and issue a $\mathcal O(b)$ call for it. Keep adding the inputs to two-element oracle calls to $L_0$ and $L_1$. When $B_1$ outputs some state $s$, make a $\mathfrak{bb}\gets \mathcal O()$ call to obtain the current board and return $(\mathfrak{bb}, s, L_0, L_1)$. (If $B_1$ outputs state $s$ before it has made $i+1$ two-element oracle queries, we abort $\mathcal B$ and let $A_3$ guess a random bit $g \stackrel{R}{\gets}\{0, 1\}$.) $\textup{\textsf{$A_3$}}$ We get a state $t = (\mathfrak{bb}, s, L_0, L_1)$ and a tally $\mathfrak v' = \mathfrak v\setminus \{v_\beta \}$ as input. We remove all votes from $\mathfrak v'$ that came from $\mathcal O_\mathcal B(\cdot, \cdot)$ calls (except the “challenge” one which has already been removed by our challenger). We can do this using the lists $L_0$ and $L_1$. Next, we add all the votes in $L_0$ back on to the result; call the multiset thus created $\mathfrak v_\mathcal B$. We run $\mathcal B_2$ on $\mathfrak{bb}$, $\mathfrak v_\mathcal B$, auxiliary data$\bot$ and state $s$ until it terminates with a guess $g$, which we return to our challenger and halt. We claim that this construction provides a view of either $G_i$ or $G_{i+1}$ towards $\mathcal B$ and retains the distinguishing advantage. In the case that $\mathcal B$ makes fewer than $i+1$ two-element oracle queries, its advantage must be $1/2$ since the two games are identical until the $i+1$-st of these queries. Therefore we can let $A_3$ just guess randomly in this case. From now on, assume that $\mathcal B$ makes at least $i+1$ two-element oracle queries. Suppose that our challenger chose $\beta = 0$. In this case, the first $i$ two-element queries result in a ballot for the “right-hand” vote (i.e. $v_1$ if the submitted pair of votes is $(v_0, v_1)$, the $i+1$-st query is forwarded to our challenger who chooses $v_0$ due to $\beta = 0$ and all further calls are answered using $v_0$: this is exactly the procedure of $G_i$. If $\beta = 1$ then the only difference is that the $i+1$-st oracle call is answered using $v_1$, resulting in exactly the procedure of $G_{i+1}$. Therefore, we preserve the distinguishing advantage $f(n)$ of $\mathcal B$ in our adversary $\mathcal A$ against $\textsf{IND-BB}$. A proof of Theorem [proppp] can be found in the full version of this paper (Smyth and Bernhard 2013). In essence, the proof uses a standard hybrid argument to show that it is sufficient to consider a variant of the $\textsf{IND-SEC}$ game in which the adversary is restricted to a single oracle call $\mathcal O_{}(v_0,v_1)$ and shows that an adversary in this game can be used to construct a successful adversary against $\textsf{IND-BB}$. Intuitively, we can generalise Theorem [proppp] to election schemes in which the auxiliary data can be simulated. Since the auxiliary data output by election schemes typically consists of signatures of knowledge proving that the election result has been correctly computed from the bulletin board, we expect many practical election schemes will satisfy zero-knowledge auxiliary data, indeed, Helios outputs partial ElGamal decryptions (Pedersen 1991; Chaum and Pedersen 1993) and proofs demonstrating knowledge of discrete logarithms (Chaum et al. 1987; Chaum, Evertse, and Graaf 1988; Schnorr 1990) which can be simulated. In this context, we believe ballot secrecy and ballot independence coincide (Remark [thm:independenceImpliesSecrecy]). Unfortunately, formalising zero-knowledge is a complex issue – in particular, the simulator needs some extra capabilities compared to the election officials (otherwise the officials could publish simulated proofs!) – to which there is no general solution and, hence, there is no general proof of Remark [thm:independenceImpliesSecrecy]. Nonetheless, we believe Remark [thm:independenceImpliesSecrecy] can be shown to hold for particular formalisations of zero-knowledge, for instance, a proof could be constructed in the programmable random oracle model (the proof would essentially be that of Theorem [proppp] with the simulator being run at the appropriate point; we briefly comment on this in the proof of Theorem [proppp]) and, hence, a proof of ballot secrecy can be reduced to a proof of ballot independence.
Given an election scheme $\Gamma$ satisfying zero-knowledge auxiliary data (informally, zero-knowledge auxiliary data means that the auxiliary data can be simulated given the result), we have $\Gamma$ satisfies ballot secrecy if and only if $\Gamma$ satisfies ballot independence.
Remark [thm:independenceImpliesSecrecy] suggests that ballot independence is a sufficient condition for ballot secrecy in election schemes where auxiliary data can be simulated. Coupled with earlier results (Bernhard, Pereira, and Warinschi 2012a), this should facilitate a proof of ballot secrecy in Helios. (Bernhard *et al.* (Bernhard et al. 2011) provide a proof of ballot secrecy in a variant of Helios which uses the Naor & Yung transformation (Naor and Yung 1990) to derive non-malleable ballots and Bernhard, Pereira & Warinschi (Bernhard, Pereira, and Warinschi 2012a) prove that Helios satisfies ballot secrecy in the special case of referendums, however, a full proof of ballot secrecy in Helios is not currently known.) # Conclusion We have formalised *ballot independence* in a variant of the model for election schemes proposed by Bernhard *et al.* Our main results are as follows. Ballot secrecy implies ballot independence; the converse holds too if there is no auxiliary data. Moreover, we have argued that ballot independence and ballot secrecy coincide if auxiliary data is “zero knowledge;” since auxiliary data typically consists of zero knowledge proofs, this assumption is realistic and holds for election schemes such as Helios, for instance. Furthermore, we provide some sufficient conditions for ballot independence and, hence, ballot secrecy: we show that non-malleable ballots are sufficient but not necessary for independence and secrecy, and introduce a weaker notion of controlled-malleable encryption which we show is sufficient, moreover, this notion is better suited to modelling the way ballots are handled in practice (for example, by Helios). In addition, we show that the notion of ballot secrecy proposed by Bernhard *et al.* does not capture attacks which rely on auxiliary data and we adopt a stronger definition. Furthermore, we show that the variant of Helios proposed by Desmedt & Chaidos does not satisfy ballot secrecy. #### Acknowledgements. We are particularly grateful to Bogdan Warinschi and the anonymous reviewers who read earlier versions of this paper and provided useful guidance. This work has been partly supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) / ERC project *CRYSP* (259639) and by EPSRC via grant EP/H043454/1. 0 # References
Adida, Ben. 2008. “Helios: Web-based Open-Audit Voting.” In *USENIX Security’08: 17th USENIX Security Symposium*, 335–48. USENIX Association.
Adida, Ben, Olivier de Marneffe, Olivier Pereira, and Jean-Jacques Quisquater. 2009. “Electing a University President Using Open-Audit Voting: Analysis of Real-World Use of Helios.” In *EVT/WOTE’09: Electronic Voting Technology Workshop/Workshop on Trustworthy Elections*. USENIX Association.
Backes, Michael, Cătălin Hriţcu, and Matteo Maffei. 2008. “Automated Verification of Remote Electronic Voting Protocols in the Applied Pi-calculus.” In *CSF’08: 21st Computer Security Foundations Symposium*, 195–209. IEEE Computer Society.
Bellare, Mihir, Anand Desai, David Pointcheval, and Phillip Rogaway. 1998. “Relations Among Notions of Security for Public-Key Encryption Schemes.” In *CRYPTO’98: 18th International Cryptology Conference*, 1462:26–45. LNCS. Springer.
Bellare, Mihir, and Amit Sahai. 1999. “Non-malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization.” In *CRYPTO’99: 19th International Cryptology Conference*, 1666:519–36. LNCS. Springer.
Benaloh, Josh, and Moti Yung. 1986. “Distributing the Power of a Government to Enhance the Privacy of Voters.” In *PODC’86: 5th Principles of Distributed Computing Symposium*, 52–62. ACM Press.
Bernhard, David, Véronique Cortier, Olivier Pereira, Ben Smyth, and Bogdan Warinschi. 2011. “Adapting Helios for provable ballot privacy.” In *ESORICS’11: 16th European Symposium on Research in Computer Security*, 6879:335–54. LNCS. Springer.
Bernhard, David, Olivier Pereira, and Bogdan Warinschi. 2012a. “How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios.” In *ASIACRYPT’12: 18th International Conference on the Theory and Application of Cryptology and Information Security*, 7658:626–43. LNCS. Springer.
———. 2012b. “On Necessary and Sufficient Conditions for Private Ballot Submission.” Cryptology ePrint Archive, Report 2012/236 (version 20120430:154117b).
Bulens, Philippe, Damien Giry, and Olivier Pereira. 2011. “Running Mixnet-Based Elections with Helios.” In *EVT/WOTE’11: Electronic Voting Technology Workshop/Workshop on Trustworthy Elections*. USENIX Association.
Chaidos, Pyrros. 2013. “Private Email Communication.”
Chaum, David, Jan-Hendrik Evertse, and Jeroen van de Graaf. 1988. “An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations.” In *EUROCRYPT’87: 4th International Conference on the Theory and Applications of Cryptographic Techniques*, 304:127–41. LNCS. Springer.
Chaum, David, Jan-Hendrik Evertse, Jeroen van de Graaf, and René Peralta. 1987. “Demonstrating Possession of a Discrete Logarithm Without Revealing It.” In *CRYPTO’86: 6th International Cryptology Conference*, 263:200–212. LNCS. Springer.
Chaum, David, and Torben P. Pedersen. 1993. “Wallet Databases with Observers.” In *CRYPTO’92: 12th International Cryptology Conference*, 740:89–105. LNCS. Springer.
Chor, Benny, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch. 1985. “Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults.” In *FOCS’85: 26th Foundations of Computer Science Symposium*, 383–95. IEEE Computer Society.
Cortier, Véronique, and Ben Smyth. 2011. “Attacking and fixing Helios: An analysis of ballot secrecy.” In *CSF’11: 24th Computer Security Foundations Symposium*, 297–311. IEEE Computer Society.
———. 2013. “Attacking and fixing Helios: An analysis of ballot secrecy.” *Journal of Computer Security* 21 (1): 89–148.
Delaune, Stéphanie, Steve Kremer, and Mark Ryan. 2006. “Coercion-Resistance and Receipt-Freeness in Electronic Voting.” In *CSFW’06: 19th Computer Security Foundations Workshop*, 28–42. IEEE Computer Society.
Delaune, Stéphanie, Steve Kremer, and Mark D. Ryan. 2009. “Verifying privacy-type properties of electronic voting protocols.” *Journal of Computer Security* 17 (4): 435–87.
Desmedt, Yvo, and Pyrros Chaidos. 2012. “Applying Divertibility to Blind Ballot Copying in the Helios Internet Voting System.” In *ESORICS’12: 17th European Symposium on Research in Computer Security*, 7459:433–50. LNCS. Springer.
Desmedt, Yvo, and Kaoru Kurosawa. 2005. “Electronic Voting: Starting Over?” In *ISC5: International Conference on Information Security*, 3650:329–43. LNCS. Springer.
Dolev, Danny, Cynthia Dwork, and Moni Naor. 1991. “Non-Malleable Cryptography.” In *STOC’91: 23rd Theory of Computing Symposium*, 542–52. ACM Press.
———. 2000. “Nonmalleable Cryptography.” *Journal on Computing* 30 (2): 391–437.
Gennaro, Rosario. 1995. “Achieving Independence Efficiently and Securely.” In *PODC’95: 14th Principles of Distributed Computing Symposium*, 130–36. ACM Press.
Hevia, Alejandro, and Marcos A. Kiwi. 2002. “Electronic Jury Voting Protocols.” In *LATIN’02: Theoretical Informatics*, 2286:415–29. LNCS. Springer.
———. 2004. “Electronic Jury Voting Protocols.” *Theoretical Computer Science* 321 (1): 73–94.
Naor, Moni, and Moti Yung. 1990. “Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks.” In *STOC’90: 22nd Theory of Computing Symposium*, 427–37. ACM Press.
Pedersen, Torben P. 1991. “A Threshold Cryptosystem without a Trusted Party.” In *EUROCRYPT’91: 10th International Conference on the Theory and Applications of Cryptographic Techniques*, 522–26. LNCS 547. Springer.
Schneier, Bruce. 2013. “Hacking the Papal Election.” .
Schnorr, Claus-Peter. 1990. “Efficient Identification and Signatures for Smart Cards.” In *CRYPTO’89: 9th International Cryptology Conference*, 435:239–52. LNCS. Springer.
Smyth, Ben, and David Bernhard. 2013. “Ballot secrecy and ballot independence coincide.” Cryptology ePrint Archive, Report 2013/235.
Smyth, Ben, and Véronique Cortier. 2010. “Does Helios ensure ballot secrecy?” Cryptology ePrint Archive, Report 2010/625 (version 20101217:132825).
———. 2011. “A note on replay attacks that violate privacy in electronic voting schemes.” RR-7643. INRIA.