# Non-malleable encryption with proofs of plaintext knowledge and applications to voting
Ben Smyth, Yoshikazu Hanatani
## Abstract
Non-malleable asymmetric encryption schemes which prove plaintext knowledge are sufficient for secrecy in some domains. For example, ballot secrecy in voting. In these domains, some applications derive encryption schemes by coupling malleable ciphertexts with proofs of plaintext knowledge, without evidence that the sufficient condition (for secrecy) is satisfied nor an independent security proof (of secrecy). Consequently, it is unknown whether these applications satisfy desirable secrecy properties. In this article, we propose a generic construction for such a coupling and show that our construction produces non-malleable encryption schemes which prove plaintext knowledge. Furthermore, we show how our results can be used to prove ballot secrecy of voting systems. Accordingly, we facilitate the development of applications satisfying their security objectives.
#### Keywords:
Asymmetric encryption, ballot secrecy, homomorphic encryption, indistinguishability, non-malleability, privacy, secrecy, voting.
# Introduction
An additively-homomorphic asymmetric encryption scheme allows a pair of enciphered plaintexts to be combined into a single ciphertext, such that the single ciphertext enciphers the sum of those plaintexts. Thus, homomorphic encryption allows aggregation without decryption, which is useful in many domains, including social choice theory. For example, a two-candidate voting system might instruct voters to cast asymmetric encryptions of their votes “yes” ($0$) or “no” ($1$), and instruct the tallier to decrypt the combination of encrypted votes to reveal the number of no-votes, from which the number of yes-votes can be deduced. This system ensures ballot secrecy (when instantiated with a suitable encryption scheme), because encryption prevents votes being recovered from ballots and the tallying procedure ensures that individual votes are not revealed.[^1] However, talliers and voters may cheat. Indeed, a malicious tallier many claim a spurious number of yes- and no-votes, or discard some ciphertexts under the guise that they are ill-formed (possibly after peaking inside). Moreover, a malicious voter might encrypt a negative integer to switch no-votes to yes-votes, or an integer greater than one to cast multiple no-votes. To prevent cheating, ciphertexts can be coupled with non-interactive proofs demonstrating correct ciphertext construction (to prevent claims of ill-formedness) for plaintext $0$ or $1$ (to prevent adversarial voters switching yes- and no-votes).
Smyth shows that building voting systems from non-malleable encryption schemes suffices for ballot secrecy (Smyth 2018b), moreover, Quaglia & Smyth show that such systems can be transformed into auction systems satisfying bid secrecy (Elizabeth A. Quaglia and Smyth 2018b). Furthermore, Bernhard, Pereira & Warinschi show that coupling an IND-CPA encryption scheme with a non-interactive zero-knowledge proof suffices to achieve non-malleable encryption (Bernhard, Pereira, and Warinschi 2012). It follows that our exemplar voting system satisfies ballot secrecy (when non-interactive zero-knowledge proofs are used and when the underlying encryption scheme satisfies IND-CPA). Unfortunately, results by Bernhard, Pereira & Warinschi do not apply to many encryption schemes that are used to construct voting systems, such as those proposed by Hirt (Hirt 2001, 2010), Damgård, Jurik & Nielsen (Damgård and Jurik 2001; Damgård, Jurik, and Nielsen 2010), and Adida *et al.* (Adida et al. 2009), as we shall now discuss.
## Related work: Encryption schemes for voting systems and their shortcomings
Hirt (Hirt 2001, 2010) proposes a construction for encryption schemes, from schemes satisfying IND-CPA, for a block of messages $m_1,\dots,m_k\allowbreak\in\{0,1\}$, such that the homomorphic combination of messages in the block is between $1$ and ${\sf max}$: A ciphertext $c_i$ is generated on message $m_i$ for $1 \leq i \leq k$, and ciphertexts $c_{k+1},\dots,c_{k + {\sf max}}$ are generated on *dummy messages* $m_{k+1},\dots,m_{k + {\sf max}}\allowbreak\in\{0,1\}$ such that ${\sf max}= \sum_{j=1}^{k + {\sf max}} m_j$, in addition, proofs of knowledge are used to demonstrate that each ciphertext contains plaintext $0$ or $1$ and the homomorphic combination of ciphertexts $c_1,\dots,c_{k + {\sf max}}$ contains plaintext ${\sf max}$, where non-interactive proofs use a common challenge derived from the ciphertexts and commitments. Concurrently, Damgård, Jurik & Nielsen (Damgård and Jurik 2001; Damgård, Jurik, and Nielsen 2010) propose a similar construction using Paillier encryption, but their work is reliant on unique identifiers to achieve non-malleability and it is unclear what security guarantees can be achieved when state is not maintained. Damgård, Jurik & Nielsen also propose an optimisation to the scheme by Hirt which reduces the number of dummy ciphertexts to one: A ciphertext $c_i$ is generated on each message $m_i$ for $1 \leq i \leq k$, as before, and a ciphertext $c_{k+1}$ is generated on plaintext $m_{k+1} = {\sf max}- \sum_{i=1}^k m_i$ for the dummy candidate, in addition, proofs of knowledge are used to demonstrate that the ciphertexts $c_1,\dots,c_k$ contain plaintext $0$ or $1$, the dummy ciphertext $c_{k+1}$ contains a plaintext between $0$ and ${\sf max}$, and the homomorphic combination of ciphertexts $c_1,\dots,c_{k+1}$ contains plaintext ${\sf max}$. Adida *et al.* (Adida et al. 2009) generalise Hirt’s scheme to consider cases where the homomorphic combination of messages $m_1,\dots,m_k$ is between ${\sf min}$ and ${\sf max}$, this is achieved by removing the dummy ciphertexts and proving that the homomorphic combination of ciphertexts $c_1,\dots,c_k$ contains a plaintext between ${\sf min}$ and ${\sf max}$ (the non-interactive proofs proposed by Adida *et al.* do not include ciphertexts in challenges).
Adida *et al.* use their scheme instantiated with El Gamal to build the Helios voting system (Adida et al. 2009), which instructs each voter to select their vote $v$ from candidates $1,\dots,\mathit{nc}$ and compute ciphertexts $c_1,\allowbreak\dots,\allowbreak c_{\mathit{nc}-1}$ such that if $v\not=\mathit{nc}$, then ciphertext $c_v$ contains plaintext $1$ and the remaining ciphertexts contain plaintext $0$, otherwise, all ciphertexts contain plaintext $0$. (Only $\mathit{nc}-1$ ciphertexts are needed, rather than $\mathit{nc}$, because a vote for candidate $\mathit{nc}$ is uniquely represented when all ciphertexts contain plaintext $0$. As is the case for our exemplar yes-no voting system, described in the opening paragraph.) Moreover, the voter computes zero-knowledge proofs $\sigma_1,\allowbreak\dots,\allowbreak\sigma_\mathit{nc}$ demonstrating correct computation. Proof $\sigma_j$ demonstrates that ciphertext $c_j$ contains $0$ or $1$, where $1\leq\allowbreak j \leq\allowbreak \mathit{nc}-1$, and proof $\sigma_{\mathit{nc}}$ demonstrates that the homomorphic combination of ciphertexts $c_1 \otimes\allowbreak\cdots\allowbreak\otimes\allowbreak c_{\mathit{nc}-1}$ contains $0$ or $1$. The voter casts those El Gamal ciphertexts and proofs as their ballot, which is a ciphertext in the encryption scheme proposed by Adida *et al.* (Adida et al. 2009). It follows from results by Bernhard, Pereira & Warinschi that Helios uses non-malleable encryption for two candidate elections (Bernhard, Pereira, and Warinschi 2012). Moreover, Helios satisfies ballot secrecy for such two candidate elections. However, Cortier & Smyth show that the encryption scheme by Adida *et al.* is malleable in the general case (Cortier and Smyth 2011, 2013). Indeed, given (an Adida *et al.*) ciphertext $c_1,\allowbreak\dots,\allowbreak c_{\mathit{nc}-1},\allowbreak
\sigma_1,\allowbreak\dots,\allowbreak\sigma_{\mathit{nc}}$, we have $c_{\chi(1)},\allowbreak\dots,\allowbreak c_{\chi(\mathit{nc}-1)},\allowbreak
\sigma_{\chi(1)},\allowbreak\dots,\allowbreak\sigma_{\chi(\mathit{nc}-1)},\allowbreak\sigma_{\mathit{nc}}$ is a ciphertext for all permutations $\chi$ on $\{1,\dots,\mathit{nc}-1\}$, hence, the encryption scheme proposed by Adida *et al.* (Adida et al. 2009) is malleable. It follows that Helios does not satisfy ballot secrecy in the general case. Moreover, Bernhard, Pereira & Warinschi show that the proof system used by Adida *et al.* belongs to the class of *weak Fiat-Shamir transformations* and demonstrate additional issues. Furthermore, Smyth shows that the forthcoming Helios release (that uses the Fiat-Shamir transformation, rather than its weak variant) does not satisfy ballot secrecy due to the absence of non-malleability (Smyth 2018b).
We build upon results by Adida *et al.* and Bernhard, Pereira & Warinschi to derive a non-malleable asymmetric encryption scheme suitable for voting systems, auction systems, and other systems with secrecy and verifiability requirements.
## Contribution, structure, & context
Section 2 proposes a generic construction for non-malleable asymmetric encryption schemes on blocks of plaintexts from homomorphic encryption schemes and proofs of knowledge. Our construction is inspired by Adida *et al.* (Adida et al. 2009); it differs by including ciphertexts and block numbers in challenges, to prevent attacks. Section 3 discusses sufficient conditions for ballot secrecy and shows how our results give way to ballot-secrecy proofs for voting systems, including a variant of the Helios voting system (the original Helios system is insecure). The remaining sections present further related work (§4) and a brief conclusion (§5). The appendices recall cryptographic primitives and their associated security properties (Appendix 6), along with a formal definition of Helios (Appendix 7), and present proofs (Appendix 8).
# Non-malleable encryption with proofs of plaintext knowledge
We present our construction for non-malleable asymmetric encryption schemes on blocks of plaintexts from homomorphic encryption schemes and proofs of plaintext knowledge in a subspace as follows. (We recall definitions of an *asymmetric encryption scheme*, *homomorphic encryption*, and a *non-interactive proof system*, along with security definitions, in Appendix 6. We also recall definitions of a sigma protocol which *proves plaintext knowledge in a subspace* and of the *Fiat-Shamir transformation*, the former also defines a *subspace*.)
**Definition 1**. *Let $\Pi = (\mathsf{Gen}_\Pi,\mathsf{Enc}_\Pi,\mathsf{Dec}_\Pi)$ be a homomorphic asymmetric encryption scheme (with respect to ternary operators $\odot$, $\oplus$, and $\otimes$), $\Delta = (\mathsf{Prove},\allowbreak\mathsf{Verify})$ be a non-interactive proof system derived by application of the Fiat-Shamir transformation to a hash function and a sigma protocol that proves plaintext knowledge in a subspace (of the encryption scheme’s message space), and ${\ell}$ be a positive integer. We define $\gamma(\Pi,\Delta,{\ell}) = (\mathsf{Gen},\allowbreak\mathsf{Enc},\mathsf{Dec})$ as follows:*
- *$\mathsf{Gen}(\kappa)$ computes $(\mathit{pk},\allowbreak\mathit{sk},\allowbreak\mathfrak{m}) \leftarrow \mathsf{Gen}_\Pi(\kappa);\mathfrak{m} \leftarrow \{(m_1,\dots,m_{\ell}) \mid m_1,\dots,\allowbreak m_{\ell}\in\mathfrak M \wedge m_1\odot \dots \odot m_{\ell}\in \mathfrak M\}$ and outputs $(\mathit{pk},\mathit{sk},\mathfrak{m})$, where $\mathfrak M$ is the subspace.*
- *$\mathsf{Enc}(\mathit{pk},m)$ parses $m$ as a block of plaintexts $(m_1,\dots,m_{\ell})$, chooses coins $r_1,\dots,r_{\ell}$ uniformly at random, computes*
* $\sigma \leftarrow \mathsf{Prove}((\mathit{pk},c_1\otimes\dots\otimes c_{\ell},\mathfrak M),(m_1\odot\dots\odot m_{\ell},r_1\oplus\dots\oplus r_{\ell}),{\ell}+1,\kappa)$ *
*and outputs $(c_1,\sigma_1,\dots,c_{\ell},\sigma_{\ell},\sigma)$.*
- *$\mathsf{Dec}(\mathit{sk},c)$ parses $c$ as $(c_1,\sigma_1,\dots,c_{\ell},\sigma_{\ell},\sigma)$ and outputs $(\mathsf{Dec}_\Pi(\mathit{sk},c_1),\allowbreak\dots,\allowbreak\mathsf{Dec}_\Pi(\mathit{sk},c_{\ell}))$ if parsing succeeds and $\mathsf{Verify}((\mathit{pk},c_1\otimes\dots\otimes c_{\ell},\mathfrak M),\sigma,{\ell}+1,\kappa)
\wedge \bigwedge_{1\leq i \leq {\ell}} \mathsf{Verify}((\mathit{pk},c_i,\mathfrak M),\sigma_i,i,\kappa)$, and outputs $\perp$ otherwise.*
In the above construction, observe that the message space is restricted such that for all ciphertexts $(c_1,\allowbreak\sigma_1,\dots,\allowbreak c_{\ell},\sigma_{\ell},\sigma)$ output by $\mathsf{Enc}(\mathit{pk},(m_1,\dots,m_{\ell}))$, we have $((\mathit{pk},c_i,\mathfrak M),(m_1,r_i))$ is an element of the non-interactive proof system’s relation, where $1\leq i \leq {\ell}$ and $r_i$ are the coins used to construct $c_i$. Moreover, $((\mathit{pk},c_1\otimes\dots\otimes c_{\ell},\mathfrak M),(m_1\odot\dots\odot m_{\ell},r_1\oplus\dots\oplus r_{\ell}))$ is an element of the relation too. Hence, it follows – by completeness of the non-interactive proof system – that schemes generated using our construction satisfy the correctness property of asymmetric encryption schemes. That is, $\gamma$ constructs asymmetric encryption schemes.
**Lemma 1** (Correctness). *Given a homomorphic asymmetric encryption scheme $\Pi$, a non-interactive proof system $\Delta$ derived by application of the Fiat-Shamir transformation to a hash function and a sigma protocol that proves plaintext knowledge in a subspace, and a positive integer ${\ell}$, we have $\gamma(\Pi,\Delta,{\ell})$ is an asymmetric encryption scheme.*
Our proof of Lemma 1 and all further proofs appear in Appendix 8.
Our construction builds upon homomorphic asymmetric encryption schemes and proofs of plaintext knowledge in a subspace to enhance functionality of the resulting encryption scheme. For example, homomorphic operations can be performed on the malleable ciphertexts encapsulated in a non-malleable ciphertext. That is, given a non-malleable ciphertext $(c_1,\allowbreak\sigma_1,\allowbreak,
\allowbreak\dots,\allowbreak c_{\ell},\allowbreak\sigma_{\ell}, \sigma)$, homomorphic operations can be performed on the encapsulated ciphertexts $c_1,\dots,c_{\ell}$. Moreover, if proofs $\sigma_1,\dots,\sigma_{\ell}$ are valid, then each of those ciphertexts contain plaintexts in the subspace. Furthermore, the homomorphic combination of ciphertexts, namely, $c_1\otimes\dots\otimes c_{\ell}$, contains a plaintext in the subspace if proof $\sigma$ is valid.
This enhanced functionality justifies the efficiency cost incurred from non-interactive proofs. Indeed, asymmetric encryption schemes derived using our construction are useful for privacy preserving applications and, in Section 3, we will demonstrate the applicability of our results in the context of voting systems. First, we prove that our construction produces schemes satisfying comparison based non-malleability under chosen plaintext attack ($\mathsf{CNM}\textsf{-}\mathsf{CPA}$) (Bellare and Sahai 1999).
**Theorem 2**. *Let $\Pi$ be a homomorphic asymmetric encryption scheme, $\Delta$ be a non-interactive proof system derived by application of the Fiat-Shamir transformation to a random oracle and a sigma protocol that proves plaintext knowledge in a subspace, and ${\ell}$ be a positive integer. If $\Pi$ satisfies $\mathsf{IND}\textsf{-}\mathsf{CPA}$ and is perfectly correct, and the sigma protocol satisfies special soundness and special honest verifier zero-knowledge, then asymmetric encryption scheme $\gamma(\Pi,\Delta,{\ell})$ satisfies $\mathsf{CNM}\textsf{-}\mathsf{CPA}$.*
Bellare & Sahai have shown that $\mathsf{CNM}\textsf{-}\mathsf{CPA}$ is equivalent to indistinguishability under a parallel chosen-ciphertext attack ($\mathsf{IND}\textsf{-}\mathsf{PA0}$) (Bellare and Sahai 1999), hence, our theorem can be equivalently stated in terms of indistinguishability.
# Applications to voting
An election is a decision-making procedure to choose representatives (Lijphart and Grofman 1984; Saalfeld 1995; Gumbel 2005; Alvarez and Hall 2010). Choices should be made freely, and this must be ensured by voting systems (*Universal Declaration of Human Rights* 1948; *Document of the Copenhagen Meeting of the Conference on the Human Dimension of the CSCE* 1990; *American Convention on Human Rights, “Pact of San Jose, Costa Rica”* 1969). Many voting systems rely on art, rather than science, to ensure that choices are made freely. Such systems build upon creativity and skill, rather than scientific foundations, and are routinely broken in ways that compromise free choice, e.g., (Gonggrijp and Hengeveld 2007; Bowen 2007; Wolchok et al. 2010, 2012; Springall et al. 2014). Breaks can be avoided by proving that systems satisfy carefully formulated security definitions that capture voters voting freely. We use such a definition to analyse Helios.
## Election schemes
We consider the class of voting systems that consist of the following four steps. First, a tallier generates a key pair. Secondly, each voter constructs and casts a ballot for their preferred candidate. Thirdly, the tallier tallies the ballots and announces a distribution of candidate preferences. Finally, voters and other interested parties check that the distribution corresponds to preferences expressed in ballots. Such systems can be formally captured by the following *election scheme* syntax proposed by Smyth, Frink & Clarkson (Smyth, Frink, and Clarkson 2017).
**Definition 2** (Election scheme (Smyth, Frink, and Clarkson 2017)). *An *election scheme* is a tuple of probabilistic polynomial-time algorithms $(\mathsf{Setup},%\RegisterSymb,
\mathsf{Vote},\mathsf{Tally},\mathsf{Verify})$ such that:*
*$\mathsf{Setup}$, denoted $(\mathit{pk},\mathit{sk},\mathit{mb},\mathit{mc}) \leftarrow \mathsf{Setup}(\kappa)$, is run by the tallier. The algorithm takes a security parameter $\kappa$ as input and outputs a key pair $\mathit{pk},\mathit{sk}$, a maximum number of ballots $\mathit{mb}$, and a maximum number of candidates $\mathit{mc}$.*
*$\mathsf{Vote}$, denoted $b\leftarrow\mathsf{Vote}(%\sd,
\mathit{pk},v,\mathit{nc},\kappa)$, is run by voters. The algorithm takes as input a public key $\mathit{pk}$, a voter’s vote $v$, some number of candidates $\mathit{nc}$, and a security parameter $\kappa$. The vote should be selected from a sequence $1,\dots,\mathit{nc}$ of candidates. The algorithm outputs a ballot $b$ or error symbol $\perp$.*
*$\mathsf{Tally}$, denoted $(\mathfrak v, \mathit{pf})\leftarrow\mathsf{Tally}(\mathit{sk},\mathfrak{bb},%\electoralroll,
\mathit{nc}, \kappa)$, is run by the tallier. The algorithm takes as input a private key $\mathit{sk}$, a bulletin board $\mathfrak{bb}$, some number of candidates $\mathit{nc}$, and a security parameter $\kappa$, where $\mathfrak{bb}$ is a set. And outputs an election outcome $\mathfrak v$ and a non-interactive tallying proof $\mathit{pf}$ demonstrating that the outcome corresponds to votes expressed in ballots on the bulletin board. The election outcome $\mathfrak v$ should be a vector of length $\mathit{nc}$ such that $\mathfrak v[v]$ indicates the number of votes for candidate $v$.*
*$\mathsf{Verify}$, denoted $s \leftarrow \mathsf{Verify}(\mathit{pk},\mathfrak{bb},%\electoralroll,
\mathit{nc},\mathfrak v,\mathit{pf},\kappa)$, is run to audit an election. The algorithm takes as input a public key $\mathit{pk}$, a bulletin board $\mathfrak{bb}$, some number of candidates $\mathit{nc}$, an election outcome $\mathfrak v$, a tallying proof $\mathit{pf}$, and a security parameter $\kappa$. And outputs a bit $s$, which is $1$ if the election verifies successfully or $0$ otherwise.*
*Election schemes must satisfy *correctness*: there exists a negligible function $\mathsf{negl}$, such that for all security parameters $\kappa$, integers $\mathit{nb}$ and $\mathit{nc}$, and votes $v_1,\dots,v_{\mathit{nb}}\in\{1,\dots,\mathit{nc}\}$, it holds that, given a zero-filled vector $\mathfrak v$ of length $\mathit{nc}$, we have: $\Pr[(\mathit{pk},\mathit{sk},\mathit{mb}, \mathit{mc}) \leftarrow \mathsf{Setup}(\kappa);$ $(\mathfrak v',\mathit{pf}) \leftarrow \mathsf{Tally}(\mathit{sk},\{b_1,\dots,b_{\mathit{nb}}\},\mathit{nc}, \kappa):
\mathit{nb}\leq \mathit{mb}\wedge \mathit{nc}\leq \mathit{mc}\Rightarrow \mathfrak v= \mathfrak v'] > 1 - \mathsf{negl}(\kappa)$.*
**Definition 3** ($\mathsf{IND}\textsf{-}\mathsf{CVA}$ (Smyth 2018b)). *Let $\Gamma = (\mathsf{Setup},\mathsf{Vote},\mathsf{Tally},\mathsf{Verify})$ be an election scheme, $\mathcal A$ be an adversary, $\kappa$ be the security parameter, and $\mathsf{IND}\textsf{-}\mathsf{CVA}(\Gamma,\allowbreak\mathcal A,\allowbreak\kappa)$ be the following game.*
* $\;=$
$(\mathit{pk},\mathit{sk},\mathit{mb},\mathit{mc}) \leftarrow \mathsf{Setup}(\kappa)$ $(v_0,v_1,\mathit{nc}) \leftarrow \mathcal A(\mathit{pk},\kappa)$ $\beta \leftarrow_R \{0,1\}$ $b \leftarrow \mathsf{Vote}(\mathit{pk},v_\beta,\mathit{nc},\kappa)$ $\mathfrak{bb}\leftarrow \mathcal A(b)$ $(\mathfrak v,\mathit{pf}) \leftarrow \mathsf{Tally}(\mathit{sk},\mathfrak{bb},%\electoralroll,
\mathit{nc}, \kappa)$ $g\leftarrow \mathcal A(\mathfrak v)$ $g = \beta\mathrel\wedge\allowbreak
b\not\in\mathfrak{bb}\mathrel\wedge\allowbreak 1 \leq v_0,v_1 \leq \mathit{nc}\leq \mathit{mc}\mathrel\wedge\allowbreak |\mathfrak{bb}| \leq \mathit{mb}$ *
*We say $\Gamma$ satisfies *ballot independence* or *indistinguishability under chosen vote attack* ($\mathsf{IND}\textsf{-}\mathsf{CVA}$), if for all probabilistic polynomial-time adversaries $\mathcal A$, there exists a negligible function $\mathsf{negl}$, such that for all security parameters $\kappa$, we have $\mathsf{IND}\textsf{-}\mathsf{CVA}(\Gamma,\allowbreak\mathcal A,\allowbreak\kappa)\leq \frac{1}{2} + \mathsf{negl}(\kappa)$.*
**Definition 4** (Zero-knowledge tallying proofs (Smyth 2018b)). *Let $\Gamma = (\mathsf{Setup},\allowbreak\mathsf{Vote},\allowbreak\mathsf{Tally},\allowbreak\mathsf{Verify})$ be an election scheme. We say $\Gamma$ has *zero-knowledge tallying proofs*, if there exists a zero-knowledge non-interactive proof system $(\mathsf{Prove}, \mathsf{Verify})$, such that for all security parameters $\kappa$, integers $\mathit{nc}$, bulletin boards $\mathfrak{bb}$, outputs $(\mathit{pk},\allowbreak\mathit{sk},\allowbreak\mathit{mb},\allowbreak \mathit{mc})$ of $\mathsf{Setup}(\kappa)$, and outputs $(\mathfrak v,\allowbreak\mathit{pf})$ of $\mathsf{Tally}(\mathit{sk},\mathfrak{bb},%\electoralroll,
\mathit{nc}, \kappa)$, we have $\mathit{pf}=\mathsf{Prove}((\mathit{pk},\allowbreak\mathfrak{bb},\allowbreak\mathit{nc},\allowbreak\mathfrak v),\allowbreak\mathit{sk},\allowbreak\kappa;\allowbreak{}r)$, such that coins $r$ are chosen uniformly at random by $\mathsf{Tally}$.*
**Theorem 3**. *Let $\Gamma$ be an election scheme with zero-knowledge tallying proofs. Suppose $\Gamma$ satisfies $\mathsf{HB}\textrm{-}\mathsf{Tally}\textrm{-}\mathsf{Soundness}$. We have $\Gamma$ satisfies $\mathsf{Ballot}\textrm{-}\mathsf{Secrecy}$ iff $\Gamma$ satisfies $\mathsf{IND}\textsf{-}\mathsf{CVA}$.*
A proof of Theorem 3 appears in (Smyth 2018b). We exploit the theorem to simplify analysis of ballot secrecy in Helios.
#### Suitability of $\mathsf{Ballot}\textrm{-}\mathsf{Secrecy}$.
Discussion of ballot secrecy originates from Chaum (D. L. Chaum 1981) and the earliest definitions of ballot secrecy are due to Benaloh *et al.* (J. Benaloh and Yung 1986; J. C. Benaloh and Tuinstra 1994; J. Benaloh 1996).[^2] More recently, Bernhard *et al.* propose a series of ballot secrecy definitions (Bernhard, Pereira, and Warinschi 2012; Smyth and Bernhard 2013, 2014; Bernhard et al. 2015). Smyth shows that these definitions do not detect vulnerabilities that arise when an adversary controls the bulletin board or the communication channel (Smyth 2018b). By comparison, the definition of ballot secrecy that we consider (Definition 3) detects such vulnerabilities and appears to be the strongest definition in the literature.
## Case study: Helios
Helios can be informally modelled as an election scheme such that:
$\mathsf{Setup}$ generates a key pair for an asymmetric homomorphic encryption scheme, proves correct key generation in zero-knowledge, and outputs the key pair along with the proof.
$\mathsf{Vote}$ enciphers the vote to a ciphertext, proves in zero-knowledge that the ciphertext is correctly constructed and that the vote is selected from the sequence of candidates, and outputs the ciphertext coupled with the proof.
$\mathsf{Tally}$
selects the ballots on the bulletin board for which proofs hold, homomorphically combines the ciphertexts in those ballots, decrypts the homomorphic combination to reveal the election outcome, and announces the outcome, along with a zero-knowledge proof of correct decryption.
$\mathsf{Verify}$ checks the proofs and accepts the outcome if these checks succeed.
Helios was first released in 2009 as *Helios 2.0*, the current release is *Helios 3.1.4*, and a new release is planned.[^3] Henceforth, we’ll refer to the planned release as *Helios’12*.
Smyth proves that neither Helios 2.0 nor Helios 3.1.4 satisfy $\mathsf{Ballot}\textrm{-}\mathsf{Secrecy}$ (Smyth 2018b). Moreover, he reasons that Helios’12 does not satisfy $\mathsf{Ballot}\textrm{-}\mathsf{Secrecy}$ either. This is due to the use of malleable ballots in Helios 2.0, Helios 3.1.4 & Helios’12.[^4] Smyth, Frink & Clarkson propose a generic construction $\mathsf{Helios}$ for Helios-like election schemes, which is parameterised on the choice of homomorphic encryption scheme and sigma protocols. That construction can be used to derive a variant of Helios called *Helios’16* (Smyth, Frink, and Clarkson 2017). (We formally define $\mathsf{Helios}$ and Helios’16 in Appendix 7.) We use our results to prove that Helios’16 satisfies ballot secrecy.
**Theorem 4**. *Helios’16 satisfies $\mathsf{Ballot}\textrm{-}\mathsf{Secrecy}$.*
A proof of Theorem 4 appears in Appendix 8.3. Smyth also presents a proof (Smyth 2018b). These proofs are different in structure. In particular, we exploit Theorem 2 to simplify our proof, which allows us to present our proof in just two pages, whereas Smyth required five.
# Further related work
In complimentary work, constructions for IND-CCA1 and IND-CCA2 secure encryption schemes from schemes satisfying IND-CPA have been presented. Naor & Yung (Naor and Yung 1990) propose a construction for IND-CCA1 encryption schemes from IND-CPA schemes by encrypting each plaintext twice and using a proof of knowledge to demonstrate that both ciphertexts encrypt the same plaintext, moreover, Sahai (Sahai 1999) defines additional conditions to achieve IND-CCA2 security and efficient variants which maintain IND-CCA2 security are known, e.g., (Lindell 2003; Bernhard et al. 2011). Cramer & Shoup (Cramer and Shoup 2002) derive IND-CCA2 secure encryption schemes from IND-CPA schemes using *“universal hash proof systems,"* furthermore, efficient constructions have been shown, e.g., (Cramer and Shoup 1998, 2002; Desmedt et al. 2010). Elkind & Sahai (Elkind and Sahai 2002) have shown that the techniques by Naor & Yung and Cramer & Shoup are special cases of a more general paradigm: given an IND-CPA secure encryption scheme (where *“ill-formed"* ciphertexts are indistinguishable from *“well-formed"* ciphertexts), an IND-CCA2 secure encryption scheme can be constructed by coupling ciphertexts with *“proofs of well-formedness."* Fujisaki & Okamoto (Fujisaki and Okamoto 1999) derive IND-CCA2 secure encryption schemes from probabilistic trapdoor one-way functions satisfying IND-CPA (such as El Gamal). Canetti, Halevi & Katz (Canetti, Halevi, and Katz 2004) derive IND-CCA2 encryption schemes from IND-CPA secure identity-based encryption schemes and more efficient variants are known, e.g., (Boneh and Katz 2005; Boyen, Mei, and Waters 2005; Boneh et al. 2007).
These results are orthogonal to our work, since we explicitly focus on schemes using proofs of knowledge to achieve additional security properties. The aforementioned schemes do not.
Discussion of ballot independence originates from Gennaro (Gennaro 1995) and the relationship with ballot secrecy has been explored: Benaloh shows that a simplified version of his voting system allows the administrator’s private key to be recovered by an adversary who casts a ballot as a function of other voters’ ballots (J. Benaloh 1996, sec. 2.9) and, more generally, Sako & Kilian (Sako and Kilian 1995, sec. 2.4), Michels & Horster (Michels and Horster 1996, sec. 3), Wikström (Wikström 2006, 2008, 2016) and Cortier & Smyth (Cortier and Smyth 2013, 2011) discuss how malleable ballots can be abused to compromise ballot secrecy. The first definition of ballot independence seems to be due to Smyth & Bernhard (Smyth and Bernhard 2013, 2014), moreover, they formally prove relations between their definitions of secrecy and independence. Independence has also been studied beyond elections, e.g., (Chor et al. 1985), and the possibility of compromising security in the absence of independence has been considered, e.g., (Chor and Rabin 1987; Pfitzmann and Pfitzmann 1989; Pfitzmann 1994; Dolev, Dwork, and Naor 1991, 2000; Gennaro 2000).
An earlier version of our construction appeared in (Smyth, Hanatani, and Muratani 2015). In that work, we considered
a construction from a sigma protocol, rather than a non-interactive proof system derived from a sigma protocol and a hash function. This overcomplicated the construction and proofs. Thus, this work improves upon our earlier work by considerably simplifying results. Moreover, we have used our results to prove that a variant of Helios satisfies ballot secrecy, whereas our earlier work did not include such a proof.
# Conclusion
We deliver a generic construction for non-malleable asymmetric encryption schemes from homomorphic schemes coupled with proofs of knowledge. The proofs of knowledge enhance functionality. In particular, an observer can check that ciphertexts contain plaintexts from a particular message space, without the private key. Moreover, homomorphic operations can be performed on the malleable ciphertexts embedded in non-malleable ciphertexts. We believe that the enhanced functionality justifies the efficiency cost. Indeed, such functionality has proven to be particularly useful in secret, verifiable voting systems.
# Cryptographic primitives
## Asymmetric encryption
**Definition 5** (Asymmetric encryption scheme (Katz and Lindell 2007)). *An *asymmetric encryption scheme* is a tuple of probabilistic polynomial-time algorithms $(\mathsf{Gen},\mathsf{Enc},\allowbreak\mathsf{Dec})$, such that:[^5]*
- ****Gen***, denoted $(\mathit{pk},\mathit{sk},\mathfrak m)\leftarrow \mathsf{Gen}(\kappa)$, inputs a security parameter $\kappa$ and outputs a key pair $(\mathit{pk},\mathit{sk})$ and message space $\mathfrak m$.*
- ****Enc***, denoted $c\leftarrow \mathsf{Enc}(\mathit{pk},m)$, inputs a public key $\mathit{pk}$ and message $m\in\mathfrak m$, and outputs a ciphertext $c$.*
- ****Dec***, denoted $m\leftarrow \mathsf{Dec}(\mathit{sk},c)$, inputs a private key $\mathit{sk}$ and ciphertext $c$, and outputs a message $m$ or an error symbol. We assume $\mathsf{Dec}$ is deterministic.*
*Moreover, the scheme must be *correct*: there exists a negligible function $\mathsf{negl}$, such that for all security parameters $\kappa$ and messages $m$, we have $\Pr [
(\mathit{pk},\mathit{sk},\mathfrak m) \leftarrow\mathsf{Gen}(\kappa);
c\leftarrow \mathsf{Enc}(\mathit{pk},m):
m\in\mathfrak m \Rightarrow
\mathsf{Dec}(\mathit{sk},c) = {m}] > 1-\mathsf{negl}(\kappa)$. A scheme has *perfect correctness* if the probability is $1$.*
**Definition 6** (Homomorphic encryption (Smyth, Frink, and Clarkson 2017)). *An asymmetric encryption scheme $\Gamma =
(\mathsf{Gen},\mathsf{Enc},\allowbreak\mathsf{Dec})$ is *homomorphic*, with respect to ternary operators $\odot$, $\oplus$, and $\otimes$,[^6] if there exists a negligible function $\mathsf{negl}$, such that for all security parameters $\kappa$, we have the following.[^7] First, for all messages $m_1$ and $m_2$ we have $\Pr [(\mathit{pk},\mathit{sk},\mathfrak m) \leftarrow\mathsf{Gen}(\kappa);c_1\leftarrow\mathsf{Enc}(\mathit{pk},m_1);c_2\leftarrow\mathsf{Enc}(\mathit{pk},m_2)
: m_1,m_2\in\mathfrak m \Rightarrow\mathsf{Dec}(\mathit{sk},c_1 \otimes_{\mathit{pk}} c_2) = \mathsf{Dec}(\mathit{sk},\allowbreak c_1) \odot_{\mathit{pk}} \mathsf{Dec}(\mathit{sk},c_2)
] > 1-\mathsf{negl}(\kappa)$. Secondly, for all messages $m_1$ and $m_2$, and all coins $r_1$ and $r_2$, we have $\Pr [(\mathit{pk},\mathit{sk},\mathfrak m) \leftarrow\mathsf{Gen}(\kappa): m_1,m_2\in\mathfrak m\Rightarrow\mathsf{Enc}(\mathit{pk},m_1;r_1) \otimes_{\mathit{pk}} \mathsf{Enc}(\mathit{pk},m_2;r_2) = \mathsf{Enc}(\mathit{pk},m_1\odot_{\mathit{pk}} m_2;r_1 \oplus_{\mathit{pk}} r_2)
] > 1-\mathsf{negl}(\kappa)$. We say $\Gamma$ is *additively homomorphic*, if for all security parameters $\kappa$, key pairs $\mathit{pk},\mathit{sk}$, and message spaces $\mathfrak m$, such that there exists coins $r$ and $(\mathit{pk},\mathit{sk},\mathfrak m) = \mathsf{Gen}(\kappa;r)$, we have $\odot_{\mathit{pk}}$ is the addition operator in group $(\mathfrak m,\odot_{\mathit{pk}})$.*
**Definition 7** ($\mathsf{IND}\textsf{-}\mathsf{CPA}$ (Bellare et al. 1998)). *Let $\Pi = (\mathsf{Gen},\mathsf{Enc},\allowbreak\mathsf{Dec})$ be an asymmetric encryption scheme, $\mathcal A$ be an adversary, $\kappa$ be the security parameter, and $\mathsf{IND}\textsf{-}\mathsf{CPA}(\allowbreak{}\Pi,\allowbreak \mathcal A,\allowbreak \kappa)$ be the following game.[^8]*
* $\;=$
$(\mathit{pk},\mathit{sk},\mathfrak m) \leftarrow \mathsf{Gen}(\kappa)$ $(m_0,m_1) \leftarrow \mathcal A(\mathit{pk},\mathfrak m,\kappa)$ $\beta \leftarrow_R \{0,1\}$ $c \leftarrow \mathsf{Enc}(\mathit{pk},m_\beta)$ $g \leftarrow \mathcal A(c)$ $g = \beta$ *
*In the above game, we require $m_0,m_1\in\mathfrak m$ and $|m_0| = |m_1|$. We say $\Gamma$ satisfies $\mathsf{IND}\textsf{-}\mathsf{CPA}$, if for all probabilistic polynomial-time adversaries $\mathcal A$, there exists a negligible function $\mathsf{negl}$, such that for all security parameters $\kappa$, we have $\mathsf{Succ}(\mathsf{IND}\textsf{-}\mathsf{CPA}(\allowbreak{}\Pi,\allowbreak \mathcal A,\allowbreak \kappa)) \leq 1/2 + \mathsf{negl}(\kappa)$.*
**Definition 8** ($\mathsf{IND}\textsf{-}\mathsf{PA0}$ (Bellare and Sahai 1999)). *Let $\Pi = (\mathsf{Gen},\mathsf{Enc},\allowbreak\mathsf{Dec})$ be an asymmetric encryption scheme, $\mathcal A$ be an adversary, $\kappa$ be the security parameter, and $\mathsf{IND}\textsf{-}\mathsf{PA0}(\allowbreak{}\Pi,\allowbreak \mathcal A,\allowbreak\kappa)$ be the following game.*
* $\;=$
$(\mathit{pk},\mathit{sk},\mathfrak m) \leftarrow \mathsf{Gen}(\kappa)$ $(m_0,m_1) \leftarrow \mathcal A(\mathit{pk},\mathfrak m,\kappa)$ $\beta \leftarrow_R \{0,1\}$ $c \leftarrow \mathsf{Enc}(\mathit{pk},m_\beta)$ ${\bf c} \leftarrow \mathcal A(c)$ ${\bf m} \leftarrow (\mathsf{Dec}(\mathit{sk},{\bf c}[1]),\dots,\mathsf{Dec}(\mathit{sk},{\bf c}[|{\bf c}|])$ $g\leftarrow\mathcal A({\bf m})$ $g = \beta \mathrel\wedge \bigwedge_{1\leq i \leq |{\bf c}|} c \not={\bf c}[i]$ *
*In the above game, we require $m_0,m_1\in\mathfrak m$ and $|m_0| = |m_1|$. We say $\Gamma$ satisfies $\mathsf{IND}\textsf{-}\mathsf{PA0}$, if for all probabilistic polynomial-time adversaries $\mathcal A$, there exists a negligible function $\mathsf{negl}$, such that for all security parameters $\kappa$, we have $\mathsf{Succ}(\mathsf{IND}\textsf{-}\mathsf{PA0}(\allowbreak{}\Pi,\allowbreak \mathcal A,\allowbreak\kappa)) \leq 1/2 + \mathsf{negl}(\kappa)$.*
## Proof systems
**Definition 9** (from (Smyth, Frink, and Clarkson 2017)). *Let $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ be a homomorphic asymmetric encryption scheme and $\Sigma$ be a sigma protocol for a binary relation $R$.[^9]*
- *$\Sigma$ *proves correct key generation* if a $((\kappa,\allowbreak\mathit{pk},\allowbreak\mathfrak m),\allowbreak(\mathit{sk},\allowbreak s)) \in R \Leftrightarrow\allowbreak (\mathit{pk},\allowbreak \mathit{sk},\allowbreak\mathfrak m) =\allowbreak \mathsf{Gen}(\kappa;s)$.*
*Further, suppose that $(\mathit{pk},\mathit{sk},\mathfrak m)$ is the output of $\mathsf{Gen}(\kappa;s)$, for some security parameter $\kappa$ and coins $s$.*
- *$\Sigma$ *proves plaintext knowledge in a subspace* if $((\mathit{pk},\allowbreak c,\allowbreak \mathfrak m'),\allowbreak (m,\allowbreak r)) \in R
\Leftrightarrow\allowbreak c = \mathsf{Enc}(\mathit{pk},m;r)\wedge m\in\mathfrak m' \wedge \mathfrak m'\subseteq \mathfrak m$. We call $\mathfrak m'$ the subspace.*
- *$\Sigma$ *proves correct decryption* if $((\mathit{pk},c,m),\mathit{sk}) \in R \Leftrightarrow m=\mathsf{Dec}(\mathit{sk},c).$*
**Definition 10** (Non-interactive proof system (Smyth, Frink, and Clarkson 2017)). *A *non-interactive proof system* for a relation $R$ is a tuple of algorithms $(\mathsf{Prove}, \mathsf{Verify})$, such that:*
- ****Prove***, denoted $\sigma \leftarrow \mathsf{Prove}(s,w,\kappa)$, is executed by a prover to prove $(s,w) \in R$.*
- ****Verify***, denoted $v\leftarrow \mathsf{Verify}(s,\sigma,\kappa)$, is executed by anyone to check the validity of a proof. We assume $\mathsf{Verify}$ is deterministic.*
*Moreover, the system must be *complete*: there exists a negligible function $\mathsf{negl}$, such that for all statement and witnesses $(s,w)\in R$ and security parameters $\kappa$, we have $\Pr[\sigma \leftarrow \mathsf{Prove}(s,w,\kappa):\mathsf{Verify}(s,\sigma,\kappa) = 1] > 1 - \mathsf{negl}(\kappa)$.*
**Definition 11** (Fiat-Shamir transformation (Fiat and Shamir 1987)). *Given a sigma protocol $\Sigma = (\mathsf{Comm},\mathsf{Chal},\allowbreak\mathsf{Resp},\mathsf{Verify}_\Sigma)$ for relation $R$ and a hash function $\mathcal H$, the *Fiat-Shamir transformation*, denoted $\mathsf{FS}(\Sigma,\mathcal H)$, is the tuple $(\mathsf{Prove}, \mathsf{Verify})$ of algorithms, defined as follows:*
*$\;=$
$({\sf comm},t) \leftarrow \mathsf{Comm}(s,w,\kappa)$ ${\sf chal}\leftarrow\mathcal H({\sf comm},s)$ ${\sf resp}\leftarrow\mathsf{Resp}({\sf chal},t,\kappa)$ $({\sf comm},{\sf resp})$ *
*$\;=$
${\sf chal}\leftarrow\mathcal H({\sf comm},s)$ $\mathsf{Verify}_\Sigma(s,({\sf comm},\allowbreak {\sf chal},{\sf resp}),\kappa)$ *
*A string $m$ can be included in the hashes computed by algorithms $\mathsf{Prove}$ and $\mathsf{Verify}$. That is, the hashes are computed in both algorithms as ${\sf chal}\leftarrow\mathcal H({\sf comm},\allowbreak s,\allowbreak m)$. We write $\mathsf{Prove}(s,\allowbreak w,m,\kappa)$ and $\mathsf{Verify}(s,\allowbreak({\sf comm},\allowbreak {\sf resp}),\allowbreak m,\allowbreak k)$ for invocations of $\mathsf{Prove}$ and $\mathsf{Verify}$ which include string $m$.*
**Definition 12** (Zero-knowledge (Elizabeth A. Quaglia and Smyth 2018b)). *Let $\Delta = (\mathsf{Prove}, \mathsf{Verify})$ be a non-interactive proof system for a relation $R$, derived by application of the Fiat-Shamir transformation (Fiat and Shamir 1987) to a random oracle $\mathcal H$ and a sigma protocol. Moreover, let $\mathcal S$ be an algorithm, $\mathcal A$ be an adversary, $\kappa$ be a security parameter, and $\textsf{ZK}(\allowbreak\Delta,\allowbreak\mathcal A,\allowbreak\mathcal H,\allowbreak\mathcal S,\allowbreak\kappa)$ be the following game.*
* $\;=$
$\beta \leftarrow_R \{0,1\}$ $g\leftarrow \mathcal A^{\mathcal H,\mathcal P}(\kappa)$ $g = \beta$ *
*Oracle $\mathcal P$ is defined on inputs $(s,w)\in R$ as follows:*
- *$\mathcal P(s,w)$ computes and outputs $\sigma$.*
*And algorithm $\mathcal S$ can patch random oracle $\mathcal H$.[^10] We say $\Delta$ satisfies *zero-knowledge*, if there exists a probabilistic polynomial-time algorithm $\mathcal S$, such that for all probabilistic polynomial-time algorithm adversaries $\mathcal A$, there exists a negligible function $\mathsf{negl}$, and for all security parameters $\kappa$, we have $\mathsf{Succ}(\textsf{ZK}(\Delta,\mathcal A,\mathcal H,\mathcal S,\kappa))
\leq \frac{1}{2} + \mathsf{negl}(\kappa)$. An algorithm $\mathcal S$ for which zero-knowledge holds is called a *simulator* for $(\mathsf{Prove}, \mathsf{Verify})$.*
**Definition 13** (Simulation sound extractability (Smyth, Frink, and Clarkson 2017; Bernhard, Pereira, and Warinschi 2012; Groth 2006)). *Suppose $\Sigma$ is a sigma protocol for relation $R$, $\mathcal H$ is a random oracle, and $(\mathsf{Prove}, \allowbreak\mathsf{Verify})$ is a non-interactive proof system, such that $\mathsf{FS}(\Sigma,\mathcal H) = (\mathsf{Prove}, \allowbreak\mathsf{Verify})$. Further suppose $\mathcal S$ is a simulator for $(\mathsf{Prove}, \mathsf{Verify})$ and $\mathcal H$ can be patched by $\mathcal S$. Proof system $(\mathsf{Prove}, \mathsf{Verify})$ satisfies *simulation sound extractability* if there exists a probabilistic polynomial-time algorithm $\mathcal K$, such that for all probabilistic polynomial-time adversaries $\mathcal A$ and coins $r$, there exists a negligible function $\mathsf{negl}$, such that for all security parameters $\kappa$, we have:[^11] $$\begin{gathered}
\Pr[{\bf P}\leftarrow();
{\bf Q} \leftarrow\mathcal A^{\mathcal H,\mathcal P}(\mbox{---};r);
{\bf W} \leftarrow \mathcal K^{\mathcal A'}({\bf H},{\bf P},{\bf Q})
%
: \\
|{\bf Q}|\not=|{\bf W}| \vee \exists j\in\{1,\dots,|{\bf Q}|\} \mathrel . ({\bf Q}[j][1],{\bf W}[j])\not\in R \mathrel \wedge \\
\forall (s,\sigma) \in {\bf Q},(t,\tau) \in {\bf P} \mathrel . \mathsf{Verify}(s,\sigma,\kappa) = 1 \mathrel\wedge \sigma\not=\tau] \leq \mathsf{negl}(\kappa)
\end{gathered}$$*
*where $\mathcal A(\mbox{---};r)$ denotes running adversary $\mathcal A$ with an empty input and coins $r$, where ${\bf H}$ is a transcript of the random oracle’s input and output, and where oracles $\mathcal A'$ and $\mathcal P$ are defined below:*
- *$\mathcal A'()$. Computes ${\bf Q'}\leftarrow\mathcal A(\mbox{---};r)$, forwarding any of $\mathcal A$’s oracle queries to $\mathcal K$, and outputs ${\bf Q'}$. By running $\mathcal A(\mbox{---};r)$, $\mathcal K$ is rewinding the adversary.*
- *$\mathcal P(s)$. Computes $\sigma \leftarrow \mathcal S(s); {\bf P} \leftarrow ({\bf P}[1],\allowbreak\dots,\allowbreak{\bf P}[|{\bf P}|],\allowbreak(s,\sigma))$ and outputs $\sigma$.*
*Algorithm $\mathcal K$ is an *extractor* for $(\mathsf{Prove}, \mathsf{Verify})$.*
**Theorem 5** (from (Bernhard, Pereira, and Warinschi 2012)). *Let $\Sigma$ be a sigma protocol for relation $R$, and let $\mathcal H$ be a random oracle. Suppose $\Sigma$ satisfies special soundness and special honest verifier zero-knowledge. Non-interactive proof system $\mathsf{FS}(\Sigma,\mathcal H)$ satisfies zero-knowledge and simulation sound extractability.*
# Helios
Smyth, Frink & Clarkson (Smyth, Frink, and Clarkson 2017) formalise a generic construction for Helios-like election schemes (Definition 14), which can be instantiated to derive Helios’16 (Definition 15).
**Definition 14** (Generalised Helios (Smyth, Frink, and Clarkson 2017)). *Suppose $\Pi = (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ is an additively homomorphic asymmetric encryption scheme, $\Sigma_1$ is a sigma protocol that proves correct key generation, $\Sigma_2$ is a sigma protocol that proves plaintext knowledge in a subspace, $\Sigma_3$ is a sigma protocol that proves correct decryption, and $\mathcal H$ is a hash function. Let $\mathsf{FS}(\Sigma_1,\mathcal H) = (\mathsf{ProveKey}, \mathsf{VerKey})$, $\mathsf{FS}(\Sigma_2,\mathcal H) = (\mathsf{ProveCiph}, \mathsf{VerCiph})$, and $\mathsf{FS}(\Sigma_3,\mathcal H) = (\mathsf{ProveDec}, \mathsf{VerDec})$. We define election scheme *generalised Helios*, denoted $\mathsf{Helios}(\Pi,\Sigma_1, \Sigma_2, \Sigma_3, \mathcal H) = (\mathsf{Setup},\allowbreak\mathsf{Vote},\allowbreak\mathsf{Tally},\allowbreak\mathsf{Verify})$, as follows.*
- *$\mathsf{Setup}(\kappa)$. Select coins $s$ uniformly at random, compute $(\mathit{pk},\mathit{sk},\mathfrak m) \leftarrow \mathsf{Gen}(\kappa;\allowbreak s);\allowbreak\rho \leftarrow\allowbreak \mathsf{ProveKey}((\kappa,\allowbreak\mathit{pk},\allowbreak\mathfrak m),\allowbreak(\mathit{sk},\allowbreak s),\allowbreak\kappa);\mathit{pk}'\leftarrow(\mathit{pk},\allowbreak\mathfrak m,\allowbreak\rho);\mathit{sk}'\leftarrow(\mathit{pk},\allowbreak\mathit{sk})$, let $m$ be the largest integer such that $\{0,\dots,m\}\subseteq\{0\} \cup \mathfrak m$, and output $(\mathit{pk}',\allowbreak\mathit{sk}',\allowbreak m,\allowbreak m)$.*
- *$\mathsf{Vote}(\mathit{pk}',\allowbreak v,\allowbreak\mathit{nc},\allowbreak\kappa)$. Parse $\mathit{pk}'$ as a vector $(\mathit{pk},\mathfrak m,\rho)$. Output $\perp$ if parsing fails or $\mathsf{VerKey}((\kappa,\allowbreak\mathit{pk},\allowbreak\mathfrak m),\rho,\kappa)\not= 1 \vee v\not\in\{1,\dots,\mathit{nc}\}$. Select coins $r_1, \dots, r_{\mathit{nc}-1}$ uniformly at random and compute:*
*
$c_j \leftarrow \mathsf{Enc}(\mathit{pk},m_j;r_j)$ $\sigma_j \leftarrow \mathsf{ProveCiph}((\mathit{pk}, c_j,\{0,1\}),(m_j, r_j),j,\kappa)$ $c\leftarrow c_1 \otimes \dots \otimes c_{\mathit{nc}-1}$ $m\leftarrow m_1 \odot \dots \odot m_{\mathit{nc}-1}$ $r\leftarrow r_1 \oplus \dots \oplus r_{\mathit{nc}-1}$ $\sigma_{\mathit{nc}} \leftarrow \mathsf{ProveCiph}((\mathit{pk},c,\{0,1\}),(m, r),\mathit{nc},\kappa)$ *
*Output ballot $(c_1,\dots,c_{\mathit{nc}-1},\sigma_1,\dots,\sigma_{\mathit{nc}})$.*
- *$\mathsf{Tally}(\mathit{sk}',\allowbreak\mathfrak{bb},\allowbreak\mathit{nc},\allowbreak \kappa)$. Initialise vectors $\mathfrak v$ of length $\mathit{nc}$ and $\mathit{pf}$ of length $\mathit{nc}-1$. Compute . Parse $\mathit{sk}'$ as a vector $(\mathit{pk},\mathit{sk})$. Output $(\mathfrak v,\mathit{pf})$ if parsing fails. Let $\{b_1, \dots, b_\ell\}$ be the largest subset of $\mathfrak{bb}$ such that $b_1 < \dots < b_\ell$ and for all $1 \leq i \leq \ell$ we have $b_i$ is a vector of length $2\cdot \mathit{nc}-1$ and $\bigwedge_{j = 1}^{\mathit{nc}-1} \mathsf{VerCiph}((\mathit{pk},\allowbreak b_i[j],\allowbreak\{0,1\}),b_i[j+\mathit{nc}-1],j,\kappa) =1 \wedge
\mathsf{VerCiph}((\mathit{pk},\allowbreak b_i[1]\otimes\allowbreak\cdots\allowbreak\otimes\allowbreak b_i[\mathit{nc}-1],\{0,1\}),b_i[2 \cdot\allowbreak \mathit{nc}-1],\mathit{nc},\kappa) =1$. If $\{b_1, \dots, b_\ell\} = \emptyset$, then output $(\mathfrak v,\mathit{pf})$, otherwise, compute:*
* $c \leftarrow b_1[j] \otimes \dots \otimes b_\ell[j]$ $\mathfrak v[j] \leftarrow\mathsf{Dec}(\mathit{sk},c)$ $\mathit{pf}[j] \leftarrow \mathsf{ProveDec}((\mathit{pk}, c,\mathfrak v[j]),\mathit{sk},k)$ $\mathfrak v[\mathit{nc}] \leftarrow \ell-\sum_{j=1}^{\mathit{nc}-1}\mathfrak v[j]$ *
*Output $(\mathfrak v,\mathit{pf})$.*
- *$\mathsf{Verify}(\mathit{pk}',\mathfrak{bb},\mathit{nc},\mathfrak v,\mathit{pf},\kappa)$. Parse $\mathfrak v$ as a vector of length $\mathit{nc}$, parse $\mathit{pf}$ as a vector of length $\mathit{nc}-1$, parse $\mathit{pk}'$ as a vector $(\mathit{pk},\mathfrak m,\rho)$. Output $0$ if parsing fails or $\mathsf{VerKey}((\kappa,\allowbreak\mathit{pk},\allowbreak\mathfrak m),\rho,\kappa)\not= 1$. Let $\{b_1, \dots, b_\ell\}$ be the largest subset of $\mathfrak{bb}$ satisfying the conditions given by the tally algorithm and let $\mathit{mb}$ be the largest integer such that $\{0,\dots,\mathit{mb}\}\subseteq\mathfrak m$. If $\{b_1, \dots, b_\ell\} = \emptyset \wedge \bigwedge_{j=1}^{\mathit{nc}}\mathfrak v[j] = 0$ or $\bigwedge_{j=1}^{\mathit{nc}-1}\mathsf{VerDec}((\mathit{pk}, b_1[j] \otimes \dots \otimes b_\ell[j],\mathfrak v[j]),\mathit{pf}[j],k) = 1\wedge \mathfrak v[\mathit{nc}]=\ell-\sum_{j=1}^{\mathit{nc}-1}\mathfrak v[j] \wedge 1 \leq \ell \leq \mathit{mb}$, then output $1$, otherwise, output $0$.*
*The above algorithms assume $\mathit{nc}>1$. Smyth, Frink & Clarkson define special cases of $\mathsf{Vote}$, $\mathsf{Tally}$ and $\mathsf{Verify}$ when $\mathit{nc}= 1$. We omit those cases for brevity and, henceforth, assume $\mathit{nc}$ is always greater than one.*
**Definition 15** (Helios’16 (Smyth, Frink, and Clarkson 2017)). *Election scheme *Helios’16* is $\mathsf{Helios}(\Pi,\allowbreak\Sigma_1,\allowbreak\Sigma_2,\allowbreak\Sigma_3,\allowbreak\mathcal H)$, where $\Pi$ is additively homomorphic El Gamal (Cramer, Gennaro, and Schoenmakers 1997, sec. 2), $\Sigma_1$ is the sigma protocol for proving knowledge of discrete logarithms by Chaum et al. (D. Chaum et al. 1987, Protocol 2), $\Sigma_2$ is the sigma protocol for proving knowledge of disjunctive equality between discrete logarithms by Cramer et al. (Cramer et al. 1996, fig. 1), $\Sigma_3$ is the sigma protocol for proving knowledge of equality between discrete logarithms by Chaum & Pedersen (D. Chaum and Pedersen 1993, sec. 3.2), and $\mathcal H$ is a random oracle.*
Although Helios actually uses SHA-256 (NIST 2012), we assume that $\mathcal H$ is a random oracle to prove Theorem 4. Moreover, we assume the sigma protocols used by Helios’16 satisfy the preconditions of generalised Helios, that is, (D. Chaum et al. 1987, Protocol 2) is a sigma protocol for proving correct key generation, (Cramer et al. 1996, fig. 1) is a sigma protocol for proving plaintext knowledge in a subspace, and (D. Chaum and Pedersen 1993, sec. 3.2) is a sigma protocol for proving decryption. We leave formally proving this assumption as future work.
# Proofs
## Proof of Lemma 1 (correctness)
Let $\Pi = (\mathsf{Gen}_\Pi,\mathsf{Enc}_\Pi,\mathsf{Dec}_\Pi)$, $\Delta = (\mathsf{Prove},\mathsf{Verify})$, and $\gamma(\Pi,\Delta,{\ell}) = (\mathsf{Gen},\allowbreak\mathsf{Enc},\mathsf{Dec})$. Moreover, let $\mathcal H$ denote the hash function. Suppose $\kappa$ is a security parameter and $m$ is a message. Further suppose $(\mathit{pk},\mathit{sk},\mathfrak m)$ is an output of $\mathsf{Gen}(\kappa)$ such that $m\in\mathfrak m$ and $c$ is an output of $\mathsf{Enc}(\mathit{pk},m)$. By definition of the $\mathsf{Gen}$, we have $\mathfrak{m} = \{(m_1,\dots,m_{\ell}) \mid m_1,\dots,m_{\ell}\in\mathfrak M \wedge m_1\odot \dots \odot m_{\ell}\in \mathfrak M\}$, where $\mathfrak M$ is the subspace. Hence, $m$ is a block of messages $(m_1,\dots,m_{\ell})$. By definition of $\mathsf{Enc}$, ciphertext $c$ is a tuple $(c_1,\sigma_1,\dots,c_{\ell},\sigma_{\ell},\sigma)$ such that $c_i = \mathsf{Enc}_\Pi(\mathit{pk},m_i;r_i)$ and $\sigma_i$ is an output of $\mathsf{Prove}((\mathit{pk},c_i,\mathfrak M),(m_i,r_i),\kappa)$, where $1 \leq i \leq {\ell}$ and coins $r_i$ are chosen uniformly at random. Moreover, $\sigma$ is an output of $\mathsf{Prove}((\mathit{pk},c,\mathfrak M),(m,r),\kappa)$, where $c = c_1\otimes\dots\otimes c_{\ell}$, $m = m_1\odot\dots\odot m_{\ell}$, and $r = r_1\oplus\dots\oplus r_{\ell}$. By completeness of $\Delta$, we have $\mathsf{Verify}((\mathit{pk},c,\mathfrak M),\sigma,\kappa) \wedge \bigwedge_{1\leq i \leq {\ell}}
\mathsf{Verify}((\mathit{pk},c_i,\mathfrak M),\sigma_i,\kappa)$, with overwhelming probability. Hence, $\mathsf{Dec}(\mathit{sk},\allowbreak c)$ outputs $(\mathsf{Dec}_\Pi(\mathit{sk},c_1),\allowbreak\dots,\allowbreak\mathsf{Dec}_\Pi(\mathit{sk},c_{\ell}))$, with overwhelming probability. And, by correctness of $\Pi$, we have $(\mathsf{Dec}_\Pi(\mathit{sk},c_1),\allowbreak\dots,\allowbreak\mathsf{Dec}_\Pi(\mathit{sk},c_{\ell})) = m$, with overwhelming probability. Thereby concluding our proof.
## Proof of Theorem 2 (non-malleability)
Let $\Pi = (\mathsf{Gen}_\Pi,\mathsf{Enc}_\Pi,\mathsf{Dec}_\Pi)$, $\Delta = (\mathsf{Prove},\mathsf{Verify})$, and $\Gamma = \gamma(\Pi,\Delta,{\ell}) = (\mathsf{Gen},\allowbreak\mathsf{Enc},\mathsf{Dec})$. Moreover, let $\mathfrak M$ be the subspace used by $\Delta$. Proof system $\Delta$ satisfies zero-knowledge and simulation sound extractability, because the underlying sigma protocol satisfies special soundness and special honest verifier zero-knowledge (Theorem 5). Hence, there exists a simulator $\mathcal S$ and a extractor $\mathcal K$ for $\Delta$. Suppose $\Gamma$ does not satisfy $\mathsf{CNM}\textsf{-}\mathsf{CPA}$. Hence, $\Gamma$ does not satisfy $\mathsf{IND}\textsf{-}\mathsf{PA0}$ either (Bellare and Sahai 1999), and there exists an adversary that wins $\mathsf{IND}\textsf{-}\mathsf{PA0}$ against $\Gamma$. We proceed with a sequence of games.[^12]
### Simulate decryption.
Let $\mathsf{G}$ be the game derived from $\mathsf{IND}\textsf{-}\mathsf{PA0}$ by replacing ${\bf m} \leftarrow (\mathsf{Dec}(\mathit{sk},{\bf c}[1]),\dots,\allowbreak\mathsf{Dec}(\mathit{sk},{\bf c}[|{\bf c}|])$ with ${\bf m} \leftarrow D({\bf c})$, where algorithm $D$ exploits extractor $\mathcal K$ to simulate decryption without private key $\mathit{sk}$. Namely,
- $D({\bf c})$ proceeds as follows. Parse ${\bf c}$ as vector $({\bf c}_1,\dots,{\bf c}_{|{\bf c}|})$. Initialises ${\bf m}$ as a vector of length $|{\bf c}|$ and ${\bf Q}$ as an empty vector. For each $i\in\{1,\dots,|{\bf c}|\}$ process ${\bf c}_i$ as follows: if ciphertext ${\bf c}_i$ is a valid ciphertext, i.e., ${\bf c}_i$ is a vector of length $2 \cdot {\ell}+ 1$ and all its proofs hold,[^13] then compute ${\bf Q} \leftarrow ({\bf Q}[1],\dots,{\bf Q}[|{\bf Q}|],
((\mathit{pk},{\bf c}_i[1],\mathfrak M),{\bf c}_i[2] ),\dots,
((\mathit{pk},{\bf c}_i[2\cdot {\ell}-1],\mathfrak M),{\bf c}_i[2\cdot {\ell}]))$, otherwise, compute ${\bf m}[i]\leftarrow {\perp}$. Initialise ${\bf H}$ as a transcript of the random oracle’s input and output, and ${\bf P}$ as a transcript of simulated proofs. Compute
${\bf W} \leftarrow \mathcal K({\bf H},{\bf P},{\bf Q})$ $i\leftarrow 1$
We prove that games $\mathsf{G}$ and $\mathsf{IND}\textsf{-}\mathsf{PA0}$ are equivalent.
Game $\mathsf{G}$ computes ${\bf m}[i] = {\perp}$ when ${\bf c}_i$ is not a valid ciphertext, where $1 \leq i \leq |{\bf c}|$. By inspection of algorithm $\mathsf{Dec}$, game $\mathsf{IND}\textsf{-}\mathsf{PA0}$ similarly computes ${\bf m}[i] = {\perp}$. Hence, to determine whether games $\mathsf{G}$ and $\mathsf{IND}\textsf{-}\mathsf{PA0}$ are equivalent, it suffices to check computations for valid ciphertexts.
By simulation sound extractability, we have for all $i\in\{1,\dots,|{\bf c}|\}$, if ${\bf c}_i$ is a valid ciphertext, then for all $j\in\{1,\dots,{\ell}\}$ there exists a message $m_{i,j}$ and coins $r_{i,j}$ such that ${\bf c}_i[2\cdot j - 1] = \mathsf{Enc}_\Pi(\mathit{pk},m_{i,j};r_{i,j})$ and ${\bf c}_i[2 \cdot j] = \mathsf{Prove}({(\mathit{pk},{\bf c}_i[2\cdot j - 1],\mathfrak M),(m_{i,j},r_{i,j}),i,\kappa})$, with overwhelming probability. Hence, ${\bf Q}$ is a tuple of statements and proofs for ciphertexts embedded in valid ciphertexts, and ${\bf W}$ contains the corresponding witnesses, i.e., pairs of messages and coins. It follows that Game $\mathsf{G}$ computes ${\bf m}[i]$ as the plaintext corresponding to ciphertext ${\bf c}_i$, for valid ciphertexts, with overwhelming probability. Moreover, although ciphertexts constructed using $\mathsf{Enc}_\Pi$ may not have been constructed using coins chosen uniformly at random, we nevertheless have that game $\mathsf{IND}\textsf{-}\mathsf{PA0}$ also computes ${\bf m}[i]$ as the plaintext corresponding to ciphertext ${\bf c}_i$, because $\Pi$ is perfectly correct. Thus, games $\mathsf{G}$ and $\mathsf{IND}\textsf{-}\mathsf{PA0}$ are equivalent. Since there exists an adversary that wins $\mathsf{IND}\textsf{-}\mathsf{PA0}$ against $\Gamma$, there must also exist an adversary $\mathcal A$ that wins $\mathsf{G}$ against $\Gamma$, i.e., for all negligible functions $\mathsf{negl}$, there exists a security parameter $\kappa$ such that $\frac{1}{2} + \mathsf{negl}(\kappa)< \mathsf{Succ}(\mathsf{G}{}(\Gamma,\mathcal A,\kappa))$.
### Hybrid games.
Let $\mathsf{G}0$, respectively $\mathsf{G}1$, be the game derived from $\mathsf{G}$ by replacing $\beta\leftarrow_R\{0,1\}$ with $\beta\leftarrow0$, respectively $\beta\leftarrow1$. These games are trivially related to $\mathsf{G}$, namely, $$\mathsf{Succ}(\mathsf{G}{}(\Gamma,\mathcal A,\kappa)) = \frac{1}{2} \cdot \mathsf{Succ}(\mathsf{G}0{}(\Gamma,\mathcal A,\kappa)) + \frac{1}{2}\cdot\mathsf{Succ}(\mathsf{G}1{}(\Gamma,\mathcal A,\kappa))$$ We define hybrid games $H_1,\dots,H_{\ell}$ such that $H_i$ is derived from $\mathsf{G}0$ by replacing $c \leftarrow \mathsf{Enc}(\mathit{pk},m_\beta)$ with $c \leftarrow \mathsf{Enc}(\mathit{pk},(m_1[1],\dots,m_1[i],m_0[i+1],\dots,m_0[{\ell}]))$.
It follows that a ciphertext is computed for plaintext $m_0$ in both $\mathsf{G}0{}(\Gamma,\mathcal A,\kappa)$ and $H_0$, hence, $$\mathsf{Succ}(\mathsf{G}0{}(\Gamma,\mathcal A,\kappa)) = \mathsf{Succ}(H_0(\Gamma,\mathcal A,\kappa))$$ Let $\mathsf{G}1\textrm{:}0$ be the game derived from $\mathsf{G}1$ by replacing $g=\beta$ with $g=0$. These games are trivially related, namely, $\mathsf{Succ}(\mathsf{G}1{}(\Gamma,\mathcal A,\kappa)) = 1 - \mathsf{Succ}(\mathsf{G}1\textrm{:}0{}(\Gamma,\mathcal A,\kappa))$. Moreover, we have $$\mathsf{Succ}(\mathsf{G}1\textrm{:}0{}(\Gamma,\mathcal A,\kappa)) = \mathsf{Succ}(H_{\ell}(\Gamma,\mathcal A,\kappa))$$ because a ciphertext is computed for plaintext $m_1$ in both $\mathsf{G}1\textrm{:}0$ and $H_{\ell}$. It follows that $$\begin{aligned}
\mathsf{Succ}(\mathsf{G}{}(\Gamma,\mathcal A,\kappa)) &= \frac{1}{2} \cdot (\mathsf{Succ}(\mathsf{G}0{}(\Gamma,\mathcal A,\kappa)) + \mathsf{Succ}(\mathsf{G}1{}(\Gamma,\mathcal A,\kappa)))\\
&= \frac{1}{2} + \frac{1}{2} \cdot (\mathsf{Succ}(H_0(\Gamma,\mathcal A,\kappa)) - \mathsf{Succ}(\mathsf{G}1\textrm{:}0{}(\Gamma,\mathcal A,\kappa)))\\
&= \frac{1}{2} + \frac{1}{2} \cdot (\mathsf{Succ}(H_0(\Gamma,\mathcal A,\kappa)) - \mathsf{Succ}(H_{\ell}(\Gamma,\mathcal A,\kappa)))\\
%
\intertext{which can be rewritten as a telescoping series}
%
&=\frac{1}{2} + \frac{1}{2} \cdot \sum_{1\leq j < {\ell}} \mathsf{Succ}(H_j(\Gamma,\mathcal A,\kappa)) - \mathsf{Succ}(H_{j+1}(\Gamma,\mathcal A,\kappa))\\
%
\intertext{Suppose $\mathsf{Succ}(H_{\iota}(\Gamma,\mathcal A,\kappa)) - \mathsf{Succ}(H_{\iota+1}(\Gamma,\mathcal A,\kappa))$ is the largest term in the series,
where $1 \leq \iota< {\ell}$. Thus,}
%
&\leq \frac{1}{2} + \frac{1}{2} \cdot {\ell}\cdot (\mathsf{Succ}(H_{\iota}(\Gamma,\mathcal A,\kappa)) - \mathsf{Succ}(H_{\iota+1}(\Gamma,\mathcal A,\kappa)))
\end{aligned}$$ Moreover, since adversary $\mathcal A$ wins $\mathsf{G}$ against $\Gamma$, we have $$\label{eq:soundnessProof:hybrid}
\frac{1}{2} + \frac{1}{{\ell}}\cdot\mathsf{negl}(\kappa)< \frac{1}{2} + \frac{1}{2} \cdot (\mathsf{Succ}(H_{\iota}(\Gamma,\mathcal A,\kappa)) - \mathsf{Succ}(H_{\iota+1}(\Gamma,\mathcal A,\kappa)))$$ Seeking a contradiction, we use $\mathcal A$ to construct an adversary that wins $\mathsf{IND}\textsf{-}\mathsf{CPA}$ against $\Pi$.
### Simulate proofs.
Let $\mathcal B$ be an adversary against $\mathsf{IND}\textsf{-}\mathsf{CPA}$ that simulates $\mathcal A$’s challenger by embedding its challenge ciphertext as the $\iota$th ciphertext in the challenge ciphertext it computes for $\mathcal A$. Moreover, the adversary exploits simulator $\mathcal S$ to simulate the proof corresponding to the $\iota$th ciphertext and to simulate the proof corresponding to the homomorphic combination of ciphertexts:
$\mathcal B(\mathit{pk},\mathfrak{m},\kappa)$
computes $\mathfrak{m} \leftarrow \{(m_1,\dots,m_{\ell}) \mid m_1,\dots,m_{\ell}\in\mathfrak M \wedge m_1\odot \dots \odot m_{\ell}\in \mathfrak M\}; (m_0, m_1) \leftarrow \mathcal A(\mathit{pk},\mathfrak{m},\kappa)$, parses $m_0$ as vector $(m_{0,1}, \dots, m_{0,{\ell}})$ and $m_1$ as vector $(m_{1,1}, \dots,\allowbreak m_{1,{\ell}})$, and outputs $(m_{0,\iota},m_{1,\iota})$.
$\mathcal B(c_{\iota})$
picks coins $r_1,\dots,r_{\iota-1},r_{\iota+1},\dots,r_{\ell}$, computes
$\sigma_{\iota}\leftarrow \mathcal S((\mathit{pk},c_{\iota},\mathfrak M),\iota,\kappa)$ $c \leftarrow c_1 \otimes \dots \otimes c_{\ell}$ $\sigma\leftarrow \mathcal S((\mathit{pk},c,\mathfrak M),{\ell}+1,\kappa)$ ${\bf c} \leftarrow \mathcal A((c_1,\sigma_1,\dots,c_{\ell},\sigma_{\ell},\sigma))$ ${\bf m} \leftarrow D({\bf c})$ $g \leftarrow \mathcal A({\bf m})$
and outputs $g$.
We prove that $\mathcal B$ wins $\mathsf{IND}\textsf{-}\mathsf{CPA}$ against $\Pi$.
Suppose $(\mathit{pk},\mathit{sk},\mathfrak m)$ is an output of $\mathsf{Gen}(\kappa)$ and $(m_{0,\iota},m_{1,\iota})$ is an output of $\mathcal B(\mathit{pk},\mathfrak{m},\kappa)$, where $m_0 = (m_{0,1}, \dots, m_{0,{\ell}})$ and $m_1 = (m_{1,1}, \dots,\allowbreak m_{1,{\ell}})$ are the vectors computed by $\mathcal A$. It is trivial to see that $\mathcal B(\mathit{pk},\mathfrak{m},\kappa)$ simulates the challenger in both $H_{\iota}$ and $H_{\iota+1}$ to $\mathcal A$. Further suppose $c_{\iota}$ is an output of $\mathsf{Enc}(\mathit{pk},m_\beta)$ for some bit $\beta$ and we run $\mathcal B(c_{\iota})$. Let $(c_1,\sigma_1,\dots,c_{\ell},\sigma_{\ell})$ be the ciphertext computed by $\mathcal B$ and input to $\mathcal A$. If $\beta = 0$, then $(c_1,\sigma_1,\dots,c_{\ell},\sigma_{\ell})$ simulates the ciphertext constructed by $\mathcal A$’s challenger in $H_{\iota}$, otherwise, it simulates the ciphertext in $H_{\iota+1}$, with overwhelming probability. Using a similar argument, the plaintexts computed by $\mathcal B$ and input to $\mathcal A$ simulate the plaintexts constructed by $\mathcal A$’s challenger in $H_{\iota}$ if $\beta=0$ and in $H_{\iota+1}$ otherwise, with overwhelming probability. Suppose $\mathcal B$ outputs $g$. Hence, either
- $\beta = 0$ and $\mathcal B(c_{\iota})$ simulates the challenger in $H_{\iota}$, thus $g=\beta$ with at least the probability that $\mathcal A$ wins $H_{\iota}$; or
- $\beta = 1$ and $\mathcal B(c_{\iota})$ simulates the challenger in $H_{\iota+1}$, thus, $g\not=\beta$ with at least the probability that $\mathcal A$ looses $H_{\iota+1}$ and, since $\mathcal A$ wins game $\mathsf{G}$, we have $g$ is a bit, hence, $g=\beta$.
It follows that $\mathsf{Succ}(\mathsf{IND}\textsf{-}\mathsf{CPA}(\allowbreak{}\Pi,\allowbreak \mathcal B,\allowbreak \kappa))$ is at least $\frac{1}{2} \cdot \mathsf{Succ}(H_{\iota}(\Gamma,\mathcal A,\kappa)) + \frac{1}{2} \cdot ( 1 - \mathsf{Succ}(H_{\iota+1}(\Gamma,\mathcal A,\kappa)))
= \frac{1}{2} + \frac{1}{2} \cdot (\mathsf{Succ}(H_{\iota}(\Gamma,\mathcal A,\kappa)) - \mathsf{Succ}(H_{\iota+1}(\Gamma,\mathcal A,\kappa)))$, hence, by ([eq:soundnessProof:hybrid]), we have $$\frac{1}{2} + \frac{1}{{\ell}} \cdot\mathsf{negl}(\kappa)< \mathsf{Succ}(\mathsf{IND}\textsf{-}\mathsf{CPA}(\allowbreak{}\Pi,\allowbreak \mathcal B,\allowbreak \kappa)),$$ thereby deriving a contradiction and concluding our proof.
## Proof of Theorem 4 (ballot secrecy)
Let $\Gamma = \mathsf{Helios}(\Pi,\Sigma_1, \Sigma_2, \Sigma_3, \mathcal H)$, where $\Pi$, $\Sigma_1$, $\Sigma_2$, $\Sigma_3$ and $\mathcal H$ satisfy the preconditions of Definition 14 such that $\Sigma_2$ uses subspace $\mathfrak M = \{0,1\}$. Suppose $\Pi$ satisfies $\mathsf{IND}\textsf{-}\mathsf{CPA}$ and is perfectly correct, and $\Sigma_1$ and $\Sigma_2$ satisfy special soundness and special honest verifier zero-knowledge. We prove that $\Gamma$ satisfies $\mathsf{Ballot}\textrm{-}\mathsf{Secrecy}$, which suffices for our result. Indeed, Helios’16 defines $\Pi$ as additively homomorphic El Gamal (Cramer, Gennaro, and Schoenmakers 1997, sec. 2), $\Sigma_1$ as the sigma protocol for proving knowledge of discrete logarithms by Chaum *et al.* (D. Chaum et al. 1987, Protocol 2), and $\Sigma_2$ as the sigma protocol for proving knowledge of disjunctive equality between discrete logarithms by Cramer *et al.* (Cramer et al. 1996, fig. 1). Hence, $\Pi$ satisfies $\mathsf{IND}\textsf{-}\mathsf{CPA}$ (Tsiounis and Yung 1998; Katz and Lindell 2007) and is perfectly correct, and $\Sigma_1$ and $\Sigma_2$ both satisfy special soundness and special honest verifier zero-knowledge (Bernhard, Pereira, and Warinschi 2012, sec. 4)
Let $\Pi = (\mathsf{Gen}_\Pi,\mathsf{Enc}_\Pi,\mathsf{Dec}_\Pi)$, $\mathsf{FS}(\Sigma_2,\mathcal H) = (\mathsf{ProveCiph}, \mathsf{VerCiph})$, and $\Gamma = (\mathsf{Setup},\allowbreak\mathsf{Vote},\allowbreak\mathsf{Tally},\allowbreak\mathsf{Verify})$. Moreover, let $\mathcal S$ be a simulator for $\mathsf{FS}(\Sigma_1,\mathcal H)$. Suppose $\Gamma$ does not satisfy $\mathsf{Ballot}\textrm{-}\mathsf{Secrecy}$. By Theorem 3, $\Gamma$ does not satisfy $\mathsf{IND}\textsf{-}\mathsf{CVA}$ either. (We have $\mathsf{HB}\textrm{-}\mathsf{Tally}\textrm{-}\mathsf{Soundness}$ by (Smyth 2018b; Smyth, Frink, and Clarkson 2017).) Hence, there exists an adversary $\mathcal A$ that wins $\mathsf{IND}\textsf{-}\mathsf{CVA}$ against $\Gamma$. Seeking a contradiction, we use $\mathcal A$ to construct an adversary $\mathcal B$ that wins $\mathsf{IND}\textsf{-}\mathsf{PA0}$ against our construction $\gamma$:
$\mathcal B(\mathit{pk},\mathfrak m,\kappa)$ overwrites $\mathfrak m$ with $\Pi$’s message space, computes $\rho \leftarrow\allowbreak \mathcal S((\kappa,\allowbreak\mathit{pk},\allowbreak\mathfrak m),\allowbreak\kappa);\mathit{pk}'\leftarrow(\mathit{pk},\allowbreak\mathfrak m,\allowbreak\rho);(v_0,v_1,\mathit{nc}) \leftarrow \mathcal A(\allowbreak\mathit{pk},\allowbreak\kappa)$, initialise ${\bf m}_0$ and ${\bf m}_1$ as zero-filled vector of length $\mathit{nc}-1$, assign $1$ to ${\bf m}_0[v_0]$ if $v_0 < \mathit{nc}$ and, similarly, assign $1$ to ${\bf m}_1[v_1]$ if $v_1 < \mathit{nc}$, and output $({\bf m}_0,{\bf m}_1)$.
$\mathcal B({\bf c})$ defines function $f$ such that $f({\bf c})$ parses ${\bf c}$ as $(c_1,\sigma_1,\dots,c_{\ell},\sigma_{\ell},\sigma)$ and outputs $(c_1,\dots,c_{\ell},\sigma_1,\dots,\sigma_{\ell},\sigma)$, computes ${\bf b} \leftarrow f({\bf c});\mathfrak{bb}\leftarrow \mathcal A({\bf b})$, derives the largest subset $\{b_1,\dots,b_k\}$ of $\mathfrak{bb}$ satisfying the conditions of algorithm $\mathsf{Tally}$, and outputs $(f^{-1}(b_1),\dots,f^{-1}(b_k))$.
$\mathcal B({\bf m})$ parses ${\bf m}$ as a vector $({\bf m}_1,\dots,{\bf m}_k)$, initialises $\mathfrak v$ as a vector of length $\mathit{nc}$, computes $\mathfrak v\leftarrow \Sigma_{i=1}^{k} ({\bf m}_i[1],\dots,{\bf m}_i[{\ell}],1-\sum_{j=1}^{{\ell}} {\bf m}_i[j]);\allowbreak g\leftarrow \mathcal A(\mathfrak v)$, and outputs $g$.
We prove that $\mathcal B$ that wins $\mathsf{IND}\textsf{-}\mathsf{PA0}$ against our construction $\gamma$.
Let $\gamma(\Pi,\mathsf{FS}(\Sigma_2,\mathcal H),{\ell}) = (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$, for some integer ${\ell}$ that we will specify later. Moreover, let $\mathfrak m$ be $\Pi$’s message space. Suppose $(\mathit{pk},\mathit{sk},\mathfrak m')$ is an output of $\mathsf{Gen}(\kappa)$ and $\rho$ is an output of $\mathcal S((\kappa,\allowbreak\mathit{pk},\allowbreak\mathfrak m),\allowbreak\kappa)$. Let $\mathit{pk}'= (\mathit{pk},\allowbreak\mathfrak m,\allowbreak\rho)$. Further suppose $(v_0,v_1,\mathit{nc})$ is an output of $\mathcal A(\allowbreak\mathit{pk},\allowbreak\kappa)$. Since $\mathcal S$ is a simulator for $\mathsf{FS}(\Sigma_1,\mathcal H)$, we have $\mathcal B$ simulates the challenger in $\mathsf{IND}\textsf{-}\mathsf{CVA}$ to $\mathcal A$. In particular, $\mathit{pk}'$ is a triple containing a public key and corresponding message space generated by $\mathsf{Gen}_\Pi$, and a (simulated) proof of correct key generation. Let us now specify that ${\ell}= \mathit{nc}-1$. Moreover, let $\beta \in \{0,1\}$. Suppose $({\bf m}_0,{\bf m}_1)$ is an output of $\mathcal B(\mathit{pk},\mathfrak m,\kappa)$ and ${\bf c}$ is an output of $\mathsf{Enc}(\mathit{pk},m_\beta)$. Let ${\bf b} = f({\bf c})$. Further suppose $\mathfrak{bb}$ is an output of $\mathcal A({\bf b})$. Ciphertext ${\bf b}$ is indistinguishable from an output of $\mathsf{Vote}(\mathit{pk},v_\beta,\mathit{nc},\kappa)$. Indeed, ${\bf b}$ is a tuple $(c_1,\dots,c_{\ell},\sigma_1,\dots,\sigma_{{\ell}},\sigma)$ such that $c_j = \mathsf{Enc}_\Pi(\mathit{pk},{\bf m}_\beta[j];r_j)$ and $\sigma_j$ is an output of $\mathsf{ProveCiph}((\mathit{pk},c_j,\{0,1\}),({\bf m}_\beta[j],r_j),j,\kappa)$ for some coins $r_j$ chosen uniformly at random, where $1\leq j \leq {\ell}$, and $\sigma$ is an output of $\mathsf{ProveCiph}((\mathit{pk},c_1\otimes\dots\otimes c_{\ell},\{0,1\}),({\bf m}_\beta[1]\odot\dots\odot {\bf m}_\beta[{\ell}],r_1\oplus\dots\oplus r_{\ell}),{\ell}+1,\kappa)$. Hence, $\mathcal B$ simulates the challenger in $\mathsf{IND}\textsf{-}\mathsf{CVA}$ to $\mathcal A$. Suppose $\mathcal B$ derives subset $\{b_1,\dots,b_k\}$ from $\mathfrak{bb}$ and outputs $(f^{-1}(b_1),\dots,f^{-1}(b_k))$, i.e., $\{b_1,\dots,b_k\}$ is the largest subset of $\mathfrak{bb}$ satisfying the conditions of algorithm $\mathsf{Tally}$. Let ${\bf m} = (\mathsf{Dec}(\mathit{sk},f^{-1}(b_1)),\dots,\mathsf{Dec}(\mathit{sk},f^{-1}(b_{k})))$. Further suppose $g$ is an output of $\mathcal B({\bf m})$. The following claim proves that $\mathcal B({\bf m})$ simulates the challenger in $\mathsf{IND}\textsf{-}\mathsf{CVA}$ to $\mathcal A$, hence, $g=\beta$, with at least the probability that $\mathcal A$ wins $\mathsf{IND}\textsf{-}\mathsf{CVA}$. Thus, $\mathcal B$ wins $\mathsf{IND}\textsf{-}\mathsf{PA0}$ against $\gamma(\Pi,\mathsf{FS}(\Sigma_2,\mathcal H),{\ell})$, deriving a contradiction (with respect to Theorem 2) and concluding our proof.
**Claim 1**. *Adversary $\mathcal B$’s computation of $\mathfrak v$ is equivalent to computing $\mathfrak v$ as $\mathfrak v\leftarrow \mathsf{Tally}(\mathit{sk},\mathfrak{bb},%\electoralroll,
\mathit{nc}, \kappa)$.*
Computation $\mathfrak v\leftarrow \mathsf{Tally}(\mathit{sk},\mathfrak{bb},%\electoralroll,
\mathit{nc}, \kappa)$ is equivalent to initialising $\mathfrak v$ as a zero-filled vector of length $\mathit{nc}$ and computing
$\mathfrak v[j] \leftarrow\mathsf{Dec}_\Pi(\mathit{sk},b_1[j] \otimes \dots \otimes b_k[j])$ $\mathfrak v[\mathit{nc}] \leftarrow k-\sum_{j=1}^{\mathit{nc}-1}\mathfrak v[j]$
By simulation sound extractability, there exists a message $m_{i,j}\in\{0,1\}$ and coins $r_{i,j}$ such that $b_i[j] = \mathsf{Enc}_\Pi(\mathit{pk},m_{i,j};r_{i,j})$, with overwhelming probability, where $1\leq i \leq k$ and $1 \leq j \leq \mathit{nc}-1$. Moreover, we have ${\bf m}[i] = (m_{i,1},\dots,m_{i,\mathit{nc}-1})$ by correctness of $\Pi$, where $1\leq i \leq k$. Since $\Pi$ is homomorphic, we have $b_1[j] \otimes \dots \otimes b_k[j]$ is a ciphertext, with overwhelming probability, where $1 \leq j \leq \mathit{nc}-1$. Moreover, although ciphertext $b_1[j] \otimes \dots \otimes b_k[j]$ may not have been constructed using coins chosen uniformly at random, we nevertheless have $\mathsf{Dec}_\Pi(\mathit{sk},b_1[j] \otimes \dots \otimes b_k[j]) = m_{1,j} \odot \dots \odot m_{k,j}$, because $\Pi$ is perfectly correct, where $1 \leq j \leq \mathit{nc}-1$. It follows that the above computation is equivalent to
$\mathfrak v[j] \leftarrow {\bf m}[1][j] \odot \dots \odot {\bf m}[k][j]$ $\mathfrak v[\mathit{nc}] \leftarrow k-\sum_{j=1}^{\mathit{nc}-1}\mathfrak v[j]$
Let $\mathit{mb}$ be the largest integer such that $\{0,\dots,\mathit{mb}\}\subseteq\{0\} \cup \mathfrak m$. Since $\mathcal A$ is a winning adversary, we have $k\leq \mathit{mb}$. Moreover, since $\odot$ is the addition operator in group $(\mathfrak m,\odot)$ and $m_{1,j},\dots,m_{k,j}\in\{0,1\}$, we have $m_{1,j} \odot \dots \odot m_{k,j} = \Sigma_{i=1}^k m_{i,j}$, where $1\leq j\leq \mathit{nc}-1$. It follows that the previous computation is equivalent to
$\mathfrak v\leftarrow (\Sigma_{i=1}^k {\bf m}[i][1],\dots,\Sigma_{i=1}^k {\bf m}[i][\mathit{nc}-1],k-\Sigma_{i=1}^k\Sigma_{j=1}^{\mathit{nc}-1} {\bf m}[i][j])$
which is equivalent to adversary $\mathcal B$’s computation of $\mathfrak v$, concluding our proof.
# References
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.
Alvarez, R. Michael, and Thad E. Hall. 2010. *Electronic Elections: The Perils and Promises of Digital Democracy*. Princeton University Press.
*American Convention on Human Rights, “Pact of San Jose, Costa Rica”*. 1969. Organization of American States.
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. 1996. “Verifiable Secret-Ballot Elections.” PhD thesis, Department of Computer Science, Yale University.
Benaloh, Josh Cohen, and Dwight Tuinstra. 1994. “Receipt-Free Secret-Ballot Elections.” In *STOC’94: 26th Theory of Computing Symposium*, 544–53. ACM Press.
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, David Galindo, Olivier Pereira, and Bogdan Warinschi. 2015. “SoK: A comprehensive analysis of game-based ballot privacy definitions.” In *S&p’15: 36th Security and Privacy Symposium*, 499–516. IEEE Computer Society.
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. 2012. “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.
Boneh, Dan, Ran Canetti, Shai Halevi, and Jonathan Katz. 2007. “Chosen-Ciphertext Security from Identity-Based Encryption.” *SIAM Journal on Computing* 36 (5): 1301–28.
Boneh, Dan, and Jonathan Katz. 2005. “Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption.” In *CT-RSA’05: The Cryptographers’ Track at the RSA Conference*, 3376:87–103. LNCS. Springer.
Bowen, Debra. 2007. “Secretary of State Debra Bowen Moves to Strengthen Voter Confidence in Election Security Following Top-to-Bottom Review of Voting Systems.” California Secretary of State, press release DB07:042 .
Boyen, Xavier, Qixiang Mei, and Brent Waters. 2005. “Direct chosen ciphertext security from identity-based techniques.” In *CCS’05: 12th ACM Conference on Computer and Communications Security*, 320–29. ACM Press.
Canetti, Ran, Shai Halevi, and Jonathan Katz. 2004. “Chosen-Ciphertext Security from Identity-Based Encryption.” In *EUROCRYPT’04: 23rd International Conference on the Theory and Applications of Cryptographic Techniques*, 3027:207–22. LNCS. Springer.
Chaum, David L. 1981. “Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms.” *Communications of the ACM* 24: 84–90.
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.
Chor, Benny, and Michael O. Rabin. 1987. “Achieving Independence in Logarithmic Number of Rounds.” In *PODC’87: 6th Principles of Distributed Computing Symposium*, 260–68. ACM Press.
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.
Cramer, Ronald, Matthew K. Franklin, Berry Schoenmakers, and Moti Yung. 1996. “Multi-Autority Secret-Ballot Elections with Linear Work.” In *EUROCRYPT’96: 15th International Conference on the Theory and Applications of Cryptographic Techniques*, 1070:72–83. LNCS. Springer.
Cramer, Ronald, Rosario Gennaro, and Berry Schoenmakers. 1997. “A Secure and Optimally Efficient Multi-Authority Election Scheme.” In *EUROCRYPT’97: 16th International Conference on the Theory and Applications of Cryptographic Techniques*, 1233:103–18. LNCS. Springer.
Cramer, Ronald, and Victor Shoup. 1998. “A Practical Public Key Cryptosystem Provably Secure Against Adaptive Chosen Ciphertext Attack.” In *CRYPTO’98: 18th International Cryptology Conference*, 1462:13–25. LNCS. Springer.
———. 2002. “Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption.” In *EUROCRYPT’02: 21st International Conference on the Theory and Applications of Cryptographic Techniques*, 2332:45–64. LNCS. Springer.
Damgård, Ivan, and Mads Jurik. 2001. “A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System.” In *PKC’01: 4th International Workshop on Practice and Theory in Public Key Cryptography*, 1992:119–36. LNCS. Springer.
Damgård, Ivan, Mads Jurik, and Jesper Buus Nielsen. 2010. “A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting.” *International Journal of Information Security* 9 (6): 371–85.
Desmedt, Yvo, Rosario Gennaro, Kaoru Kurosawa, and Victor Shoup. 2010. “A New and Improved Paradigm for Hybrid Encryption Secure Against Chosen-Ciphertext Attack.” *Journal of Cryptology* 23 (1): 91–120.
*Document of the Copenhagen Meeting of the Conference on the Human Dimension of the CSCE*. 1990. Organization for Security and Co-operation in Europe.
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.
Elkind, Edith, and Amit Sahai. 2002. “A Unified Methodology For Constructing Public-Key Encryption Schemes Secure Against Adaptive Chosen-Ciphertext Attack.” Cryptology ePrint Archive, Report 2002/042.
Fiat, Amos, and Adi Shamir. 1987. “How To Prove Yourself: Practical Solutions to Identification and Signature Problems.” In *CRYPTO’86: 6th International Cryptology Conference*, 263:186–94. LNCS. Springer.
Fujisaki, Eiichiro, and Tatsuaki Okamoto. 1999. “How to Enhance the Security of Public-Key Encryption at Minimum Cost.” In *PKC’99: Second International Workshop on Practice and Theory in Public Key Cryptography*, 1560:53–68. LNCS. Springer.
Gennaro, Rosario. 1995. “Achieving Independence Efficiently and Securely.” In *PODC’95: 14th Principles of Distributed Computing Symposium*, 130–36. ACM Press.
———. 2000. “A Protocol to Achieve Independence in Constant Rounds.” *IEEE Transactions on Parallel and Distributed Systems* 11 (7): 636–47.
Gonggrijp, Rop, and Willem-Jan Hengeveld. 2007. “Studying the Nedap/Groenendaal ES3B Voting Computer: A Computer Security Perspective.” In *EVT’07: Electronic Voting Technology Workshop*. USENIX Association.
Groth, Jens. 2004. “Efficient Maximal Privacy in Boardroom Voting and Anonymous Broadcast.” In *FC’04: 8th International Conference on Financial Cryptography*, 3110:90–104. LNCS. Springer.
Gumbel, Andrew. 2005. *Steal This Vote: Dirty Elections and the Rotten History of Democracy in America*. Nation Books.
Hao, Fao, Peter Y. A. Ryan, and Piotr Zieliński. 2010. “Anonymous voting by two-round public discussion.” *Journal of Information Security* 4 (2): 62–67.
Hirt, Martin. 2001. “Multi-Party Computation: Efficient Protocols, General Adversaries, and Voting.” PhD thesis, ETH Zurich.
———. 2010. “Receipt-Free *K*-out-of-*L* Voting Based on ElGamal Encryption.” In *Towards Trustworthy Elections: New Directions in Electronic Voting*, edited by David Chaum, Markus Jakobsson, Ronald L. Rivest, and Peter Y. A. Ryan, 6000:64–82. LNCS. Springer.
Katz, Jonathan, and Yehuda Lindell. 2007. *Introduction to Modern Cryptography*. Chapman & Hall/CRC.
Khader, Dalia, Ben Smyth, Peter Y. A. Ryan, and Feng Hao. 2012. “A Fair and Robust Voting System by Broadcast.” In *EVOTE’12: 5th International Conference on Electronic Voting*, 205:285–99. Lecture Notes in Informatics. Gesellschaft für Informatik.
Khazaei, Shahram, and Mehri Rezaei-Aliabadi. 2018. “A Rigorous Security Analysis of a Decentralized Electronic Voting Protocol in the Universal Composability Framework.” *Journal of Information Security and Applications* 43: 99–109.
Kiayias, Aggelos, and Moti Yung. 2002. “Self-Tallying Elections and Perfect Ballot Secrecy.” In *PKC’01: 3rd International Workshop on Practice and Theory in Public Key Cryptography*, 2274:141–58. LNCS. Springer.
Lijphart, Arend, and Bernard Grofman. 1984. *Choosing an electoral system: Issues and Alternatives*. Praeger.
Lindell, Yehuda. 2003. “A Simpler Construction of CCA2-Secure Public-Key Encryption Under General Assumptions.” In *EUROCRYPT’03: 22nd International Conference on the Theory and Applications of Cryptographic Techniques*, 2656:241–54. LNCS. Springer.
Michels, Markus, and Patrick Horster. 1996. “Some Remarks on a Receipt-Free and Universally Verifiable Mix-Type Voting Scheme.” In *ASIACRYPT’96: International Conference on the Theory and Application of Cryptology and Information Security*, 1163:125–32. LNCS. Springer.
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.
NIST. 2012. “Secure Hash Standard (SHS).” {FIPS PUB} 180-4. Information Technology Laboratory, National Institute of Standards; Technology.
Pfitzmann, Birgit. 1994. “Breaking Efficient Anonymous Channel.” In *EUROCRYPT’94: 11th International Conference on the Theory and Applications of Cryptographic Techniques*, 950:332–40. LNCS. Springer.
Pfitzmann, Birgit, and Andreas Pfitzmann. 1989. “How to Break the Direct RSA-Implementation of Mixes.” In *EUROCRYPT’89: 6th International Conference on the Theory and Applications of Cryptographic Techniques*, 434:373–81. LNCS. Springer.
Quaglia, Elizabeth A., and Ben Smyth. 2018a. “A Short Introduction to Secrecy and Verifiability for Elections.” arXiv, Report 1702.03168.
Quaglia, Elizabeth A, and Ben Smyth. 2018b. “Secret, Verifiable Auctions from Elections.” *Theoretical Computer Science* 730: 44–92.
Saalfeld, Thomas. 1995. “On Dogs and Whips: Recorded Votes.” In *Parliaments and Majority Rule in Western Europe*, edited by Herbert Döring. St. Martin’s Press.
Sahai, Amit. 1999. “Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security.” In *FOCS’99: 40th Annual Symposium on Foundations of Computer Science*, 543–53. IEEE Computer Society.
Sako, Kazue, and Joe Kilian. 1995. “Receipt-Free Mix-Type Voting Scheme: A practical solution to the implementation of a voting booth.” In *EUROCRYPT’95: 12th International Conference on the Theory and Applications of Cryptographic Techniques*, 921:393–403. LNCS. Springer.
Schoenmakers, Berry. 1999. “A Simple Publicly Verifiable Secret Sharing Scheme and Its Application to Electronic Voting.” In *CRYPTO’99: 19th International Cryptology Conference*, 1666:148–64. LNCS. Springer.
Shoup, Victor. 2004. “Sequences of Games: A Tool for Taming Complexity in Security Proofs.” Cryptology ePrint Archive, Report 2004/332.
Smyth, Ben. 2018a. “A Foundation for Secret, Verifiable Elections.” Cryptology ePrint Archive, Report 2018/225.
———. 2018b. “Ballot secrecy: Security definition, sufficient conditions, and analysis of Helios.” Cryptology ePrint Archive, Report 2015/942.
Smyth, Ben, and David Bernhard. 2013. “Ballot secrecy and ballot independence coincide.” In *ESORICS’13: 18th European Symposium on Research in Computer Security*, 8134:463–80. LNCS. Springer.
———. 2014. “Ballot secrecy and ballot independence: definitions and relations.” Cryptology ePrint Archive, Report 2013/235.
Smyth, Ben, Steven Frink, and Michael R. Clarkson. 2017. “Election Verifiability: Cryptographic Definitions and an Analysis of Helios and JCJ.” Cryptology ePrint Archive, Report 2015/233.
Smyth, Ben, Yoshikazu Hanatani, and Hirofumi Muratani. 2015. “NM-CPA secure encryption with proofs of plaintext knowledge.” In *IWSEC’15: 10th International Workshop on Security*. Vol. 9241. LNCS. Springer.
Springall, Drew, Travis Finkenauer, Zakir Durumeric, Jason Kitcat, Harri Hursti, Margaret MacAlpine, and J. Alex Halderman. 2014. “Security Analysis of the Estonian Internet Voting System.” In *CCS’14: 21st ACM Conference on Computer and Communications Security*, 703–15. ACM Press.
Tsiounis, Yiannis, and Moti Yung. 1998. “On the Security of ElGamal Based Encryption.” In *PKC’98: First International Workshop on Practice and Theory in Public Key Cryptography*, 1431:117–34. LNCS. Springer.
*Universal Declaration of Human Rights*. 1948. United Nations.
Wikström, Douglas. 2006. “Simplified Submission of Inputs to Protocols.” Cryptology ePrint Archive, Report 2006/259.
———. 2008. “Simplified Submission of Inputs to Protocols.” In *SCN’08: 6th International Conference on Security and Cryptography for Networks*, 5229:293–308. LNCS. Springer.
———. 2016. *Verificatum: How to Implement a Stand-alone Verifier for the Verificatum Mix-Net (VMN Version 3.0.2)*.
Wolchok, Scott, Eric Wustrow, J. Alex Halderman, Hari K. Prasad, Arun Kankipati, Sai Krishna Sakhamuri, Vasavya Yagati, and Rop Gonggrijp. 2010. “Security Analysis of India’s Electronic Voting Machines.” In *CCS’10: 17th ACM Conference on Computer and Communications Security*, 1–14. ACM Press.
Wolchok, Scott, Eric Wustrow, Dawn Isabel, and J. Alex Halderman. 2012. “Attacking the Washington, D.C. Internet Voting System.” In *FC’12: 16th International Conference on Financial Cryptography and Data Security*, 7397:114–28. LNCS. Springer.
[^1]: Ballot secrecy necessarily assumes that the tallier does not deviate from the prescribed tallying procedure, since ballots can be tallied individually to reveal votes. Distributing the tallier’s role permits ballot secrecy under the weaker assumption that at least one tallier does not deviate, but a trust assumption nonetheless remains. Ultimately, we would prefer not to trust talliers; unfortunately, this is only known to be possible for decentralised voting systems, e.g., (Schoenmakers 1999; Kiayias and Yung 2002; Groth 2004; Hao, Ryan, and Zieliński 2010; Khader et al. 2012; Khazaei and Rezaei-Aliabadi 2018), which do not scale.
[^2]: Quaglia & Smyth present a tutorial-style introduction to modelling ballot secrecy (Elizabeth A. Quaglia and Smyth 2018a), and Smyth provides a technical introduction (Smyth 2018a).
[^3]: , published c. 2012, accessed 18 Oct 2017. (Cached version: .)
[^4]: Helios’12 uses non-malleable ballots for two candidate elections and is proven to satisfy notions of ballot secrecy (Bernhard, Pereira, and Warinschi 2012; Bernhard et al. 2015), assuming the bulletin board and the communication channel are trusted. (See Smyth (Smyth 2018b) for further details.)
[^5]: *Our definition differs from Katz and Lindell’s original definition (Katz and Lindell 2007, Definition 10.1) in that we formally state the plaintext space.*
[^6]: *We shall implicitly bind ternary operators occasionally, i.e., we write *$\Gamma$ is a homomorphic asymmetric encryption scheme* as opposed to the more verbose *$\Gamma$ is a homomorphic asymmetric encryption scheme, with respect to ternary operators $\odot$, $\oplus$, and $\otimes$*.*
[^7]: *We write $X \circ_{\mathit{pk}} Y$ for the application of ternary operator $\circ$ to inputs $X$, $Y$, and ${\mathit{pk}}$. We occasionally abbreviate $X \circ_{\mathit{pk}} Y$ as $X \circ Y$, when ${\mathit{pk}}$ is clear from the context.*
[^8]: *Our definition of an asymmetric encryption scheme explicitly defines the plaintext space, whereas, Bellare *et al.* (Bellare et al. 1998) leave the plaintext space implicit; this change is reflected in our definition of $\mathsf{IND}\textsf{-}\mathsf{CPA}$. Moreover, we provide the adversary with the message space and security parameter. We adapt $\mathsf{IND}\textsf{-}\mathsf{PA0}$ similarly.*
[^9]: *Given a binary relation $R$, we write $((s_1,\allowbreak\dots,\allowbreak s_l),\allowbreak (w_1,\allowbreak\dots,\allowbreak w_k))\in R\Leftrightarrow\allowbreak P(s_1,\allowbreak\dots,\allowbreak s_l,\allowbreak w_1,\allowbreak\dots,\allowbreak w_k)$ for $(s, w) \in R \Leftrightarrow\allowbreak P(s_1,\allowbreak\dots,\allowbreak s_l,\allowbreak w_1,\allowbreak\dots,\allowbreak w_k) \wedge\allowbreak s =\allowbreak (s_1,\allowbreak\dots,\allowbreak s_l) \wedge\allowbreak w =\allowbreak (w_1,\allowbreak\dots,\allowbreak w_k)$, hence, $R$ is only defined over pairs of vectors of lengths $l$ and $k$.*
[^10]: *Random oracles can be *programmed* or *patched*. We will not need the details of how patching works, so we omit them here; see Bernhard et al. (Bernhard, Pereira, and Warinschi 2012) for a formalisation.*
[^11]: *We extend set membership notation to vectors: we write $x\in{\bf x}$ if $x$ is an element of the set $\{ {\bf x}[i] : 1 \leq i \leq |{\bf x}| \}$.*
[^12]: Shoup presents a brief tutorial on structuring proofs as sequences of games (Shoup 2004).
[^13]: All its proofs hold if $\mathsf{Verify}({(\mathit{pk},\allowbreak{\bf c}_i[1]\otimes\allowbreak{\bf c}_i[3]\otimes\allowbreak\dots\allowbreak\otimes\allowbreak {\bf c}_i[2 \cdot {\ell}- 1],\allowbreak \mathfrak M),\allowbreak{\bf c}_i[|{\bf c}_i|],\allowbreak{\ell}+1,\allowbreak\kappa})\wedge\bigwedge_{1\leq j \leq {\ell}}\mathsf{Verify}({(\mathit{pk},{\bf c}_i[2\cdot j - 1],\mathfrak M),{\bf c}_i[2 \cdot j],j,\kappa})$.