# Replay attacks that violate ballot secrecy in Helios
Ben Smyth
## Abstract
Helios 2.0 is a web-based end-to-end verifiable electronic voting system, suitable for use in low-coercion environments. In this paper we identify a vulnerability in Helios which allows an adversary to compromise the privacy of voters whom cast abstention votes. The vulnerability can be attributed to the absence of ballot independence and the use of homomorphic ElGamal encryption, in particular, these properties can be exploited by an adversary to construct a ballot related to an abstention vote cast by an honest voter and this ballot can be submitted by a corrupt voter to influence the election outcome, thereby introducing information that can be used to violate privacy. We demonstrate the attack by breaking privacy in a mock election using the current Helios implementation. It is unlikely that the vulnerability will be exploited in a real-world election and therefore our results are largely theoretical. Nonetheless, we cannot expect any computational proofs of ballot secrecy without fixing this vulnerability and, moreover, the attack methodology may be of interest – in particular, it could represent a viable threat to existing protocols in the literature – thus providing motivation to report these results.
# Introduction
Paper-based elections derive ballot independence from physical characteristics of the real-world, for example, ballots are constructed in isolation inside polling booths and complete ballots are deposited into locked ballot boxes. By comparison, in electronic voting protocols, ballots are sent using publicly readable communication channels and, in end-to-end verifiable elections, stored on a publicly readable bulletin board; this makes the provision of ballot independence difficult in a digital setting. Nevertheless, the provision of ballot independence is important to ensure privacy, as demonstrated by Cortier & Smyth (**Smyth10:Helios?**; **Smyth11:Helios?**; **Smyth11:ReplayAttacks?**) who exploit the absence of ballot independence to violate ballot secrecy in the following protocols: Helios 2.0 (**AdidaPereiraMarneffeQuisquater?**), two schemes presented at CRYPTO – namely, the protocols due to Sako & Kilian (**SK94:Voting?**) and Schoenmakers (**Schoenmakers99:PVSS?**) – and the scheme by Lee *et al.* (**Lee04?**).
Informally, ballot independence is characterised by Gennaro (**Gennaro95:Independence:SK-voting?**) as follows:
- *Ballot independence.* Observing another voter’s interaction with the election system does not allow a voter to cast a *related* vote.
Ballot independence is important due to the apparent relationship with privacy, in addition, it prohibits the voting system from influencing a voter’s behaviour, that is, observation of the voting system does not leak information that may affect a voter’s vote, for example, it prevents Bob from casting the same vote as Alice (possibly without learning Alice’s vote).
The concept of privacy for electronic voting systems has been informally defined by the following properties (**KR05:vote-privacy?**; **Backes08:Voting?**; **DKR08?**):
- *Ballot secrecy.* A voter’s vote is not revealed to anyone.
- *Receipt freeness.* A voter cannot gain information which can be used to prove, to a coercer, how she voted.
- *Coercion resistance.* A voter cannot collaborate, with a coercer, to gain information which can be used to prove how she voted.
The above properties are ordered by increasing strength and protocols satisfying the stronger privacy properties are typically more complex, hence, a scheme satisfying ballot secrecy, rather than coercion resistance, may be preferred due its relative simplicity.
Another desirable property of electronic voting systems is verifiability (**JCJ02?**; **DagstuhlAccord07?**; **Smyth10:ElectionVerifiability?**), which includes the following aspects:
- *Individual verifiability.* A voter can check that her own ballot is published on the election’s bulletin board.
- *Universal verifiability.* Anyone can check that all the votes in the election outcome correspond to ballots published on the election’s bulletin board.
The verifiability properties (also called *end-to-end verifiability* (**JCJ02?**; **ChaumRyanSchneider2005?**; **BenAdidaThesis?**)) allow voters and election observers to verify – independently of the hardware and software running the election – that votes have been recorded, tallied and declared correctly. In this paper, we revisit ballot secrecy in Helios 2.0.
#### Helios 2.0.
Helios (**AdidaPereiraMarneffeQuisquater?**) is an open-source web-based electronic voting system which uses homomorphic encryption. The scheme is claimed to satisfy ballot secrecy, but the nature of remote voting makes the possibility of satisfying stronger privacy properties difficult and Helios does not satisfy receipt freeness nor coercion resistance. In addition to ballot secrecy, the system provides individual and universal verifiability (cf. (**Smyth10:ElectionVerifiability?**; **Smyth10:ElectionVerifiabilityA?**) and (**Smyth10:thesis?**) for an analysis of verifiability in Helios). Helios is particularly significant due to its real-world deployment: the International Association of Cryptologic Research used Helios to elect its board members (**IACRHelios10b?**), following a successful trial in a non-binding poll (**IACRHelios10?**); the Catholic University of Louvain adopted the system to elect the university president (**AdidaPereiraMarneffeQuisquater?**); and Princeton University used Helios to elect the student vice president (**HeliosPrinceton10?**).
## Foundations: Homomorphic voting schemes
An additive homomorphic encryption function $E$ takes a key $K$, nonce $R$, and message $M$, and is such that $$E(K,R,M) \circ E(K,R',M') = E(K,R+R',M+M')$$ This homomorphic property is useful in electronic voting since an encrypted tally can be derived by combining encrypted votes and ballot secrecy can be ensured using a threshold encryption scheme (**Benaloh85?**; **Benaloh86?**; **SK94:Voting?**; **Benaloh96:Thesis?**; **HS00?**). In two candidate elections, a verifiable electronic voting protocol can be derived by coupling each encrypted vote with a signature of knowledge demonstrating that the ciphertext contains a plaintext $v \in\{0,1\}$. These proofs are necessary to prevent an adversarial voter casting the encryption of an integer $v \not\in \{0,1\}$ which could be combined with legitimate ballots to derive an election outcome in the voter’s favour, in particular, it allows the detection of ballots that could eliminate honest votes from the outcome and add multiple votes for the adversary’s preferred candidate.
Two candidate election systems can be generalised to multi-candidate election systems (**Benaloh86?**; **Hirt10:ThesisChap5?**; **Damgard10:MultCandidateElections?**) by running $\ell$ two candidate elections in parallel and proving that the homomorphic combination of ciphertexts contains the plaintext $1$. Moreover, Hirt (**Hirt01:Thesis?**; **Hirt10:ThesisChap5?**) proposes a generalisation to approval voting by adding *dummy candidates*: the voter computes a ciphertext on the plaintext $v_i = 0$ (disapprove) or the plaintext $v_i = 1$ (approve) for each candidate $i\in\{1,\dots,\ell\}$ and derives ciphertexts on the plaintexts $v_{\ell+1},\dots,v_{\ell+{\sf max}}\in\{0,1\}$ for the dummy candidates such that ${\sf max}= \sum_{i=1}^{\ell+{\sf max}} v_i$, in addition, the voter proves that each ciphertext contains plaintext $0$ or $1$ and the homomorphic combination of ciphertexts contains the plaintext ${\sf max}$, where ${\sf max}$ defines the maximum number of candidates a voter may approve. Concurrently, Damgård, Jurik & Nielsen (**Damgard01:MultCandidateElections?**; **Damgard10:MultCandidateElections?**) propose a similar construction using Paillier encryption. Damgård, Jurik & Nielsen also propose an optimisation to the scheme by Hirt which reduces the number of dummy ciphertexts to one: the voter computes a ciphertext $c_i$ on the plaintext $0$ or $1$ for each candidate $i\in\{1,\dots,\ell\}$, as before, and derives a ciphertext $c_{\ell+1}$ on the plaintext $v_{\ell+1} = {\sf max}- \sum_{i=1}^\ell v_i$ for the dummy candidate, in addition, the voter proves that each ciphertext $c_1,\dots,c_\ell$ contains plaintext $0$ or $1$, the dummy ciphertext $c_{\ell+1}$ contains a plaintext between $0$ and ${\sf max}$, and the homomorphic combination of ciphertexts $c_1,\dots,c_{\ell+1}$ contains the plaintext ${\sf max}$. In Helios the dummy candidate is removed and the voter proves that the homomorphic combination of ciphertexts contains a plaintext between $0$ and ${\sf max}$. Henceforth, we shall consider a setting where the voter must select at most one candidate and hence assume ${\sf max}= 1$, moreover, we shall refer to the case where a voter does not approve of any candidate as a vote for abstention. This setting can be adapted to elections where a voter must select exactly one candidate by reducing the length of the ballot to $\ell-1$ ciphertexts and modelling votes for candidate $\ell$ as votes for abstention.
### Exploiting privacy in schemes without independence.
Cortier & Smyth (**Smyth10:Helios?**; **Smyth11:Helios?**; **Smyth11:ReplayAttacks?**) have shown that replaying a voter’s ballot (without knowing the vote contained within that ballot) can be used to violate ballot secrecy. For example, consider an attack in an election with three voters – namely, Alice, Bob, and Mallory – as follows: if Mallory replays Alice’s ballot, then Mallory can reveal Alice’s vote by observing the election outcome and checking which candidate obtained at least two votes. Moreover, the vulnerability can be exploited in more realistic settings and Cortier & Smyth (**Smyth10:Helios?**; **Smyth11:Helios?**) highlight the feasibility of an attack in French legislative elections.
#### Variants exploiting ballot malleability.
In multi-candidate elections, Cortier & Smyth propose variants of their attack which abuse the malleability of ballots to ensure replayed ballots are distinct. For example, given a valid ballot as follows: $$\mathit{ciph}_1,\dots,\mathit{ciph}_{\ell},\mathit{spk}_1,\dots,\mathit{spk}_\ell,\mathit{spk}$$ where $\mathit{ciph}_i$ is a ciphertext containing the voter’s choice for the $i$th candidate and $\mathit{spk}_i$ demonstrates that the ciphertext $\mathit{ciph}_i$ contains plaintext $0$ or $1$ (that is, each candidate can receive at most one vote), and $\mathit{spk}$ demonstrates that the homomorphic combination of ciphertexts $\mathit{ciph}_1\circ\dots\circ\mathit{ciph}_{\ell}$ also contains plaintext $0$ or $1$ (that is, at most one candidate receives one vote), then the following ballot is also valid: $$\mathit{ciph}_{\pi(1)},\dots,\mathit{ciph}_{\pi(\ell)},\mathit{spk}_{{\pi(1)}},\dots,\allowbreak\mathit{spk}_{\pi(\ell)},\mathit{spk}$$ where $\pi$ is an arbitrary permutation over $\{1,\dots,\ell\}$. This makes identification of replayed ballots non-trivial since checking for exact duplicates is insufficient.
At the time of writing, the aforementioned attacks by Cortier & Smyth are the only theoretical attacks against Helios. (See Adida (**Adida10:HeliosAttacks?**) for a current list of attacks.)
## Contribution
This paper highlights a further attack against Helios. The attack works by exploiting the homomorphic properties of ElGamal. First, the adversary observes a ballot cast by an honest voter defined as follows: $$\mathit{ciph}_1,\dots,\mathit{ciph}_{\ell},\mathit{spk}_1,\dots,\mathit{spk}_\ell,\mathit{spk}$$ Secondly, the adversary computes the ciphertexts $\mathit{ciph} = \mathit{ciph}_1\circ\dots\circ\mathit{ciph}_{\ell}$ and $\widebar{\mathit{ciph}} = E(K,0,0)$, in addition, for all $2 \leq j \leq \ell$ the adversary computes a signature of knowledge $\widebar{\mathit{spk}}_j$ demonstrating that $\widebar{\mathit{ciph}}$ is a ciphertext containing $v \in \{0,1\}$. Thirdly, the adversary casts the following ballot: $$\mathit{ciph},\underbrace{\widebar{\mathit{ciph}},\dots,\widebar{\mathit{ciph}}}_{\ell-1 \textrm{ times}},\mathit{spk},\widebar{\mathit{spk}}_2,\dots,\widebar{\mathit{spk}}_\ell,\mathit{spk}$$ Finally, if the election outcome contains a vote for at most one candidate (that is, the remaining candidates do not have any votes), then the aforementioned honest voter did not vote for any candidate, that is, the honest voter abstained. The attack has been demonstrated by violating privacy in a mock election using the current Helios implementation. However, the practical threat to real-world elections is small and we consider the results largely theoretical. Nevertheless, we cannot expect any computational proofs of ballot secrecy without fixing this vulnerability and, moreover, the attack methodology may be of interest – in particular, the methodology could represent a viable threat to existing protocols in the literature – thereby providing motivation to report these results.
# Preliminaries: Helios 2.0
**\[tex2md\] this section could not be converted; its LaTeX follows verbatim:** `Error at (line 280, column 1): unexpected } expecting \end{document} \iffalse ^`
``` latex
\section{Preliminaries: Helios 2.0}\label{sec:helios}
%\ifPETS
This section presents a full description of Helios 2.0, this background material
has been largely taken from Cortier \& Smyth~\cite{Smyth10:Helios}.
%\else
% This section presents a full description of Helios 2.0.
%\fi
The Helios scheme
exploits the additive homomorphic~\cite{Schoenmakers94:Proof-of-ciphertext,CramerGennaroSchoenmakers97:AdditiveElGamal,Schoenmakers09:Chapter-on-Voting-Schemes} %Fontaine07:HomomorphicSurvey}
and distributed decryption~\cite{Pedersen91:ThresholdElGamal,Pedersen92} properties of ElGamal~\cite{ElGamal85}.
%In addition, signature proofs of knowledge are used to ensure integrity.
We will recall these cryptographic details before presenting the Helios protocol.
\subsection{Additive homomorphic ElGamal}\label{sec:back}
Given cryptographic parameters $(p,q,g)$ and a number $n\in\mathbb{N}$ of trustees, where $p$ and $q$ are large primes such that $q \mid p-1$ and $g$ is a generator of the multiplicative group $\mathbb{Z}^*_p$ of order $q$, the following operations are defined by ElGamal.
%Variants of the key generation and decryption algorithms exist to permit distributed decryption amongst $n$ trustees.
%\paragraph{Key generation.} Select a private key $x \in \mathbb{Z}_q^*$ and compute public key $h = g^x \bmod p$.
\paragraph{Distributed key generation.} Each trustee $i \in n$ selects a private key share $x_i \in_R \mathbb{Z}_q^*$ and computes a public key share $h_i = g^{x_i} \bmod p$. The public key is $h = h_1 \cdot \ldots \cdot h_n \bmod p$.
\paragraph{Encryption.} Given a message $m$ and a public key $h$, select a random nonce $r \in_R \mathbb{Z}_q^*$ and derive the ciphertext $(a,b) = (g^r \bmod p,\;g^m \cdot h^r \bmod p)$.
%\paragraph{Re-encryption.} Given a ciphertext $(a,b)$ and public key $h$, select a random nonce $r' \in_R \mathbb{Z}_q^*$ and derive the re-encrypted ciphertext $(a',b') = (a \cdot g^{r'} \bmod p,\; b \cdot h^{r'} \bmod p)$.
\paragraph{Homomorphic addition.} Given two ciphertexts $(a,b)$ and $(a',b')$, the homomorphic addition of plaintexts is computed by multiplication $(a \cdot a' \bmod p,\; b \cdot b' \bmod p)$.
%\paragraph{Decryption.} Given a ciphertext $(a,b)$ and private key $x$, derive $M = b/a^x \bmod p$ and recover plaintext $m = \log_g M$.
\paragraph{Distributed decryption.} Given a ciphertext $(a,b)$, each trustee $i\in n$ computes the partial decryption $k_i = a^{x_i}$. The plaintext $m = \log_g M$ is recovered from $M = b/(k_1 \cdot \ldots \cdot k_n) \bmod p$. \\
\noindent The computation of a discrete logarithm $\log_g M$ is hard in general. However, if $M$ is chosen from a restricted domain, then the complexity is reduced; for example, if $M$ is an integer such that $0 \leq M \leq n$, then the complexity is $O(n)$ by linear search or $O(\sqrt n)$ using the baby-step giant-step algorithm~\cite{Shanks69} (see also~\cite[\S3.1]{Lenstra90}).
For secrecy, each trustee $i\in n$ must demonstrate knowledge of a discrete logarithm $\log_g h_i$, that
is, they prove that $h_i$ has been correctly constructed;
this prevents, for example, a trustee constructing their public key share $h_i = h$.
For integrity of decryption, each trustee $i\in n$ must demonstrate equality between
discrete logarithms $\log_g h_i$ and $\log_a k_i$;
this prevents, for example, a trustee constructing the public key share $h_i = g^{m+x_i}$ and providing the partial decryption $k_i = a^{x_i}$. These proofs can be achieved using signatures of knowledge (see Appendix~\ref{app:spk} for details).
In addition, the voter must demonstrate that a valid vote has been encrypted and we describe a suitable
proof technique in the following section using a signature of knowledge scheme and a SHA-256 hash function denoted by $\hash$.
\subsection{Disjunctive proof of equality between discrete logs}\label{sec:spk}
Given the aforementioned cryptographic parameters $(p,q,g)$, a signature of knowledge demonstrating that a ciphertext $(a,b)$ contains either $0$ or $1$ (without revealing which), can be constructed by proving that either $\log_g a = \log_h b$ or $\log_g a = \log_h b/g^{m}$; that is, a signature of knowledge demonstrating a disjunct proof of equality between discrete logarithms~\cite{Schoenmakers94:Proof-of-ciphertext,Schoenmakers09:Chapter-on-Voting-Schemes}. Observe for a valid ciphertext $(a,b)$ that $a\equiv g^r \bmod p$ and $b\equiv h^r \cdot g^m \bmod p$ for some nonce $r\in\mathbb{Z}_q^*$; hence the former disjunct $\log_g g^r = \log_h h^r \cdot g^m$ is satisfied when $m = 0$, and the latter $\log_g g^r = \log_h ( h^r \cdot g^m ) / g^{m}$ when $m = 1$.
%\textcolor{red}{Need to check if $\Min$ is possible.}
This technique is generalised by~\cite{AdidaPereiraMarneffeQuisquater} to allow a signature of knowledge demonstrating that a ciphertext $(a,b)$ contains message $m$, where $m\in\{\Min,\dots,\allowbreak\Max\}$ for some system parameters $\Min,\Max\in\mathbb{N}$ such that $\Min \leq \Max$. Formally, a signature of knowledge demonstrating a disjunct proof of equality between discrete logarithms can be derived, and verified, as follows~\cite{AdidaPereiraMarneffeQuisquater,Schoenmakers94:Proof-of-ciphertext,Schoenmakers09:Chapter-on-Voting-Schemes}.
\paragraph{Sign.} Given ciphertext $(a,b)$ such that $a\equiv g^r \bmod p$ and $b\equiv h^r \cdot g^m \bmod p$ for some nonce $r\in\mathbb{Z}_q^*$, where plaintext $m\in\{\Min,\dots,\Max\}$. For all $i \in \{\Min,\dots,m-1,m+1,\dots,\Max\}$, compute challenge $c_i \in_R \mathbb{Z}_q^*$, response $s_i \in_R \mathbb{Z}_q^*$ and witnesses $a_i = g^{s_i} / a^{c_i} \bmod p$ and $b_{i} = h^{s_i} /(b / g^i)^{c_i} \bmod p$. Select a random nonce $w \in_R\mathbb{Z}_q^*$. Compute witnesses $a_m = g^w \bmod p$ and $b_m = h^w \bmod p$, challenge $c_m = \hash(a_\Min,b_\Min,\dots,a_\Max,b_\Max) - \sum_{i\in\{\Min,\dots,m-1,m+1,\dots,\Max\}} c_i \pmod q$ and response $s_m = w + r\cdot c_m \bmod q$.
\paragraph{Verify.} Given $(a,b)$ and $(a_\Min,\allowbreak b_\Min,\allowbreak c_\Min,\allowbreak s_\Min,\allowbreak \dots,\allowbreak a_\Max,\allowbreak b_\Max,\allowbreak c_\Max,\allowbreak s_\Max)$, for each $\Min\leq i \leq \Max$ check $g^{s_i} \equiv a_i \cdot a^{c_i} \pmod p$ and $h^{s_i} \equiv b_i \cdot (b/g^i)^{c_i} \pmod p$. Finally, check $\hash(a_\Min,b_\Min,\dots,a_\Max,b_\Max) \equiv \sum_{\Min\leq i \leq \Max} c_i \pmod q$.\\
\noindent A valid proof asserts that $(a,b)$ is a ciphertext containing the message $m$ such that $m\in\{\Min,\dots,\Max\}$.
\subsection{Protocol description}\label{sec:protocol}
An election is created by naming an election officer, selecting a set of trustees, and generating a distributed public key pair. The election officer publishes, on the bulletin board, the public part of the trustees' key (and proof of correct construction), the candidate list $\tilde{t} = (t_1,\dots,t_{\candidates}) \cup \{\epsilon\}$ (where $\epsilon$ represents a vote of abstention), and the list of eligible voters $\widetilde{id} = (id_1,\dots,id_n)$; the officer also publishes the \emph{election fingerprint}, that is, the hash of these parameters. Informally, the steps that participants take during a run of Helios are as follows.
\begin{enumerate}
\item The voter launches a browser script that downloads the election parameters
and recomputes the election fingerprint. The voter should verify that the
fingerprint corresponds to the value published on the bulletin board.
% (This ensures that the script is using the trustees' public key;
% in particular, it helps prevent encrypting a vote
% with an adversary's public key. Such attacks have been discussed in the
% context of Direct Anonymous Attestation by Rudolph~\cite{Rudolph07:DAAFlaw};
% although, the vulnerability was discounted, in the trusted computing setting,
% by Leung, Chen \& Mitchell~\cite{Chen08:PossibleFlaw}.)
\item\label{step:ballot} %To cast a vote, the voter runs a browser script that inputs her
The voter inputs her
vote $v\in\tilde {t}$ to the browser script, which
creates a ballot consisting of her vote encrypted by the
trustees' public key, and a proof that the
ballot represents a permitted vote. %(this is needed because the ballots are
% never decrypted individually, in particular, it prevents multiple
% votes being encoded as a single ballot).
The ballot is displayed to the voter.
\item The voter can audit the ballot to check if it really represents a
vote for her chosen candidate; if she decides to do this, then the script
provides her with the random data used in the ballot creation. She
can then independently reconstruct her ballot and verify that it
is indeed well-formed.
%, but the ballot is now invalid. (Invalidating
%audited ballots provides some practical resistance against vote selling.)
% The script provides some practical resistance
% against vote selling by refusing to cast audited ballots.
% See Benaloh~\cite{Benaloh06:BallotAudit,Benaloh07:BallotAudit} for further details on ballot auditing.
\item\label{step:submit} When the voter has decided to cast her ballot, the script
submits it to the election officer. The election officer authenticates the
voter and checks that she is eligible to vote. The election officer
also verifies the proof and checks that the ballot does not
contain a ciphertext that already exists on the bulletin board\footnotemark.
If these checks succeed, then the voter's ballot is published on the bulletin board, appended with the
voter's identity $id$.
\footnotetext{Checking ballots for ciphertexts that already exist on the bulletin board
was proposed by Cortier \& Smyth~\cite{Smyth10:Helios,Smyth11:Helios} to defend against
the attacks discussed in the introduction (Section~\ref{sec:intro:CortierSmyth}), this check is not part of the original Helios
specification~\cite{AdidaPereiraMarneffeQuisquater}.}
% \sout{ The election officer also publishes the hash of the ballot. }
% (In practice, the election officer also publishes the hash of the ballot,
% we omit this detail for brevity.)
\item Individual voters can check that their ballots appear on the
bulletin board and, by verifying the proof, observers are assured that
ballots represent permitted votes.
\item After some predefined deadline, the election officer homomorphically combines the ballots and publishes
the encrypted tally on the bulletin board. Anyone can check that tallying is performed
correctly.
\item
Each of the trustees publishes a partial decryption of the
encrypted tally, together with a signature of knowledge proving
the partial decryption's correct construction.
Anyone can verify these proofs.
\item
The election officer decrypts the tally and publishes the result. Anyone can
check this decryption.
\end{enumerate}
Formally, Step~\ref{step:ballot} is defined in Figure~\ref{fig:ballot}. Checking voter eligibility (Step~\ref{step:submit}) is beyond the scope of Helios and Adida \emph{et al.}~\cite{AdidaPereiraMarneffeQuisquater} propose the use of existing infrastructure. The remaining steps follow immediately from the application of cryptographic primitives (see Sections~\ref{sec:back} \& \ref{sec:spk} for details).
%(this figure implicitly assume parameters $\Min = 0$ and $\Max = 1$ are used for signatures of knowledge demonstrating a disjunct proof of equality between discrete logarithms).
%(For simplicity the ballot construction algorithm in Figure~\ref{fig:ballot} considers a vote $v\in\tilde {t}$, this can be generalised~\cite{AdidaPereiraMarneffeQuisquater} to consider a vote $\tilde v \subseteq \tilde t$.)
% Checking voter eligibility (Step~\ref{step:submit}) is beyond the scope of Helios and Adida \emph{et al.}~\cite{AdidaPereiraMarneffeQuisquater} propose the use of existing infrastructure.
%the remaining steps follow immediately from the application of cryptographic primitives (see Sections~\ref{sec:back} \& \ref{sec:spk} for details).
\begin{figure}
\begin{description}
\item{Input:} Cryptographic parameters $(p,q,g)$, public key $h$, candidate list $\tilde{t} = (t_1,\allowbreak\dots,t_{\candidates})\mathrel\cup\{\epsilon\}$ and vote $v$.
\item{Output:} Encrypted vote $(a_1,b_1),\dots,(a_{\candidates},b_{\candidates})$, signatures of knowledge $(\bar a_1,\bar b_1,\bar c_1,\allowbreak\bar s_1,\allowbreak \bar a'_1,\allowbreak\bar b'_1,\allowbreak\bar c'_1,\allowbreak\bar s'_1), \dots,\allowbreak (\bar a_{\candidates},\allowbreak\bar b_{\candidates},\allowbreak\bar c_{\candidates},\allowbreak\bar s_{\candidates},\bar a'_{\candidates},\bar b'_{\candidates},\bar c'_{\candidates},\bar s'_{\candidates})$ and signature of knowledge $(\bar a,\allowbreak\bar b,\allowbreak\bar c,\allowbreak\bar s,\allowbreak\bar a',\bar b',\bar c',\bar s')$.
\end{description}
\begin{enumerate}
\item If $v \not\in \tilde{t}$ then the script terminates.
\item Encode the vote $v$ as a bitstring. For all $1 \leq i \leq \candidates$, let
\[
m_i = \left\{\begin{array}{lcl}
1 &\quad& \textrm{if $v = t_i$}\\
0 & & \textrm{otherwise}
\end{array}\right.
\]
\item The bitstring representing the vote is encrypted. For all $1 \leq i \leq \candidates$, let
\[
(a_i,b_i) = (g^{r_i} \bmod p,\;g^{m_i} \cdot h^{r_i} \bmod p)
\]
where $r_i \in_R \mathbb{Z}_q^*$.
\item For all $1 \leq i \leq \candidates$, let $(\bar a_i,\bar b_i,\bar c_i,\bar s_i,\bar a'_i,\bar b'_i,\bar c'_i,\bar s'_i)$ be a signature of knowledge demonstrating that the ciphertext $(a_i,b_i)$ contains either $0$ or $1$. %, that is, each candidate can receive at most one vote.
\item Let $(\bar a,\bar b,\bar c,\bar s,\bar a',\bar b',\bar c',\bar s')$ be a signature of knowledge demonstrating that the ciphertext $(a_1 \cdot \ldots\cdot a_{\candidates}, \; b_1 \cdot\ldots\cdot b_{\candidates})$ contains either $0$ or $1$.%, that is, at most one candidate receives one vote.
\end{enumerate}
\caption{Ballot construction by the browser script}
\label{fig:ballot}\label{fig:ballotConstruction}
\end{figure}
%\textcolor{blue}{26/01/2011: I have just realised that we permit the voter to cast an empty ballot. } \textcolor{blue}{\it I have revised the paper, it is probably worth checking the following paragraph}
%\paragraph{Generalised voting scheme}
%For simplicity, the ballot construction algorithm (Figure~\ref{fig:ballot}) considers a vote $v\in\tilde {t}$. This can be generalised to a vote $\tilde v \subseteq \tilde t$ (where if $\epsilon\in\tilde v$, then $\tilde{v} = \{\epsilon\}$), by modifying
%Step~5 of the ballot construction algorithm to use a signature of knowledge $(\bar a_\Min, \bar b_\Min, \bar c_\Min, \bar s_\Min, \ldots,\allowbreak \bar a_\Max, \bar b_\Max, \bar c_\Max, \bar s_\Max)$, rather than $(\bar a,\bar b,\bar c,\bar s,\bar a',\bar b',\bar c',\bar s')$, where $\Min$ and $\Max$ are system parameters determining the minimum and maximum number of candidates a voter is allowed to select. In particular, this allows us to consider the case where a voter must vote for at least one candidate, that is, where abstention is forbidden.
\iffalse
\subsubsection{Software implementation\ifPETS.\fi}
Helios 3.0 is an extension of Helios 2.0 which adds numerous practical features,
including: integration of authentication with various web-services (for example,
Facebook, GMail and Twitter), bulk voter registration using pre-existing electoral rolls,
and simplification of administration with multiple trustees. Helios 3.0 has been implemented
and is publicly available: \url{http://heliosvoting.org/}.
%, the source code is also public \url{https://github.com/benadida/}.
\fi
```
# Attacking ballot secrecy
Ballot secrecy means “a voter’s vote is not revealed to anyone." We show that Helios does not satisfy this definition by presenting an attack which allows an adversary to reveal a voter’s vote. Intuitively, an adversary may identify a voter’s ballot on the bulletin board (using the voter’s $id$) and cast a related ballot by corrupting a dishonest voter, this will leak information in the tally and the adversary can exploit this knowledge to violate the voter’s privacy. A description of the attack will now be presented in the case of three eligible voters.
## Attack description
Let us consider an election with candidates $t_1,\dots,t_{\ell}$ and three eligible voters who have identities $id_1$, $id_2$ and $id_3$. Suppose that voters $id_1$ and $id_2$ are honest, and $id_3$ is a dishonest voter controlled by the adversary. Further assume that the honest voters have cast their ballots. The bulletin board entries are as follows: $$\begin{array}{c}
id_1, ciph_{1,1},\dots,ciph_{1,\ell}, spk_{1,1}, \dots, spk_{1,\ell}, spk'_1 \\
id_2, ciph_{2,1},\dots,ciph_{2,\ell}, spk_{2,1}, \dots, spk_{2,\ell}, spk'_2 \\
\end{array}$$ where for all $i\in\{1,2\}$ and $j\in\{1,\dots,\ell\}$ we have $$\begin{array}{lcl}
ciph_{i,j} &=& (a_{i,j},b_{i,j})\\
spk_{i,j} &=& (\bar a_{i,j},\bar b_{i,j},\bar c_{i,j},\bar s_{i,j},\bar a'_{i,j},\bar b'_{i,j},\bar c'_{i,j},\bar s'_{i,j})\\
spk'_i &=& (\bar a_i,\bar b_i,\bar c_i,\bar s_i, \bar a'_i,\bar b'_i,\bar c'_i,\bar s'_i)
\end{array}$$ The value $ciph_{i,j}$ is the $i$th voter’s encrypted vote for the candidate $t_j$ (that is, $ciph_{i,j}$ is a ciphertext containing the plaintext $1$ if the voter voted $t_j$, and $0$ otherwise), $spk_{i,j}$ demonstrates that the ciphertext $ciph_{i,j}$ contains either $0$ or $1$ (that is, the voter has assigned at most one vote to each candidate), and $spk'_i$ demonstrates that $(a_{i,1} \cdot\ldots\cdot a_{i,\ell}, \; b_{i,1} \cdot\ldots\cdot b_{i,\ell})$ contains either $0$ or $1$ (that is, the voter has voted for at most one candidate).
#### Constructing a related ballot.
The adversary observes the bulletin board and selects $ciph_{k,1},\dots,ciph_{k,\ell}, spk_{k,1}, \dots, spk_{k,\ell}, spk'_k$ such that $id_k$ is the voter under attack, where $k\in\{1,2\}$. The adversary submits the following related ballot: $$(a_{k,1} \cdot\ldots\cdot a_{k,\ell}, \; b_{k,1} \cdot\ldots\cdot b_{k,\ell}),\underbrace{(1,1),\dots,(1,1)}_{\textrm{$\ell-1$ times}},
spk'_k, \widebar{spk}_2,\dots,\widebar{spk}_{\ell}, spk'_k$$ such that for all $2 \leq j \leq \ell$ we have $\widebar{spk}_j = (\hat a_{j},\hat b_{j},\hat c_{j},\hat s_{j},\hat a'_{j},\hat b'_{j},\hat c'_{j},\hat s'_{j})$ where $\hat c'_{j},\hat s'_{j}, \hat s_{j}\in_R \mathbb{Z}_q^*$ and $$\begin{array}{lcl}
\hat a_{j} &=& g^{\hat s_{j}} \bmod p \\
\hat a'_{j} &=& g^{\hat s'_{j}} \bmod p \\
\hat b_{j} &=& h^{\hat s_{j}} \bmod p \\
\hat b'_{j} &=& h^{\hat s'_{j}} \cdot g^{\hat c'_{j}} \bmod p \\
\hat c_{j} &=& \mathcal{H}(\hat a_{j},\hat b_{j},\hat a'_{j},\hat b'_{j}) - \hat c'_{j} \bmod q
\end{array}$$ It is trivial to witness that $spk'_k$ is a valid proof for $(a_{k,1} \cdot\ldots\cdot a_{k,\ell}, \; b_{k,1} \cdot\ldots\cdot b_{k,\ell})$ and, therefore, $spk'_k$ is a valid proof for the homomorphic combination of ciphertexts encapsulated in the adversary’s ballot. Moreover, the following lemma demonstrates that for all $2 \leq j \leq \ell$ we have $\widebar{spk}_j$ is valid proof for $(1,1)$.
The signature $(\bar a,\bar b,\bar c,\bar s,\bar a',\bar b',\bar c',\bar s')$ is valid for $(1,1)$, where $\bar c',\bar s', \bar s\in_R \mathbb{Z}_q^*$, $\bar a = g^{\bar s} \pmod p$, $\bar a' = g^{\bar s'} \pmod p$, $\bar b = h^{\bar s} \pmod p$, $\bar b' = h^{\bar s'} \cdot g^{\bar c'} \pmod p$, and $\bar c = \mathcal{H}(\bar a,\bar b,\bar a',\bar b') - \bar c' \pmod q$.
*Proof.* Suppose the signature $(\bar a,\bar b,\bar c,\bar s,\bar a',\bar b',\bar c',\bar s')$ is defined above and let $(a,b) = (1,1)$. We must show that $(a,b)$ and $(\bar a,\bar b,\bar c,\bar s,\bar a',\bar b',\bar c',\bar s')$ satisfy the conditions of the verification algorithm described in Section
[sec:spk]. Since $a^{\bar c} = 1$ and $(b/g^0)^{\bar c} = 1$, we trivially derive $g^{\bar s} \equiv \bar a\cdot a^{\bar c} \pmod p$ and $h^{\bar s} \equiv \bar b\cdot (b/g^0)^{\bar c} \pmod p$. Moreover, since $a^{\bar c'} = 1$ and $(b/g^1)^{\bar c'} = g^{-\bar c'}$, it follows that $g^{\bar s'} \equiv \bar a'\cdot a^{\bar c'} \pmod p$ and $h^{\bar s'} \equiv \bar b' \cdot (b/g^1)^{\bar c'} \pmod p$. Finally, recall $\bar c = \mathcal{H}(\bar a,\bar b,\bar a',\bar b') - \bar c' \pmod q$ and therefore $\mathcal{H}(\bar a,\bar b,\bar a',\bar b') \equiv \bar c + \bar c' \pmod q$, concluding our proof. ◻
It follows that the adversary’s ballot will be accepted by the bulletin board, hence, we have informally shown a technique to violate ballot independence in Helios: observing another voter’s interaction with the election system allows a voter to cast a *related* vote, in particular, if a voter cast an abstention vote, then the *same* vote can be cast (otherwise, a vote for candidate $t_1$ can be cast). The absence of ballot independence will now be exploited to violate privacy.
#### Violating privacy.
The homomorphic addition of ballots reveals the encrypted tally $(a_{1,1} \cdot a_{2,1} \cdot a_{k,1} \cdot\ldots\cdot a_{k,\ell},\;b_{1,1} \cdot b_{2,1} \cdot b_{k,1} \cdot\ldots\cdot b_{k,\ell}),
(a_{1,2} \cdot a_{2,2},\;b_{1,2} \cdot b_{2,2})
\dots,
(a_{1,\ell} \cdot a_{2,\ell},\;b_{1,\ell} \cdot b_{2,\ell})$ and, given the partial decryptions, these ciphertexts can be decrypted to reveal the number of votes for each candidate. If the tally contains two votes for abstention, then the voter with identity $id_k$ cast a vote for abstention and hence privacy is not preserved. Moreover, the vote of the remaining honest voter will also be revealed.
If there exists $r$ such that $g^1\cdot h^r =
b_{1,1} \cdot b_{2,1} \cdot b_{k,1} \cdot \ldots \cdot b_{1,\ell} \cdot b_{2,\ell} \cdot b_{k,\ell}$, then the following conditions hold:
1. $b_{k,u} = g^0\cdot h^{\hat r}$ for all $u\in\{1,\dots,\ell\}$; and
2. $b_{k',w} = g^1\cdot h^{\hat r}$ for some $\hat r$ and $w\in\{1,\dots,\ell\}$, where $k' \in \{1,2\} \backslash \{k\}$.
We stress that the precondition of Theorem [thm] is a trivial consequence of the tally containing two votes for abstention and one vote for some candidate. Postcondition (1) asserts that the voter with identity $id_k$ abstained and Postcondition (2) asserts that the remaining voter voted for candidate $t_w$. The theorem does not consider cases where the election outcome is unanimous – for example, when the tally contains three votes for abstention – since, in this instance, all votes are revealed.
## Discussion
The attack is largely theoretical since the adversary is restricted to casting one related ballot (any subsequently cast related ballots will be rejected because they contain ciphertexts that already exist on the bulletin board), accordingly, there is no motivation to generalise the attack for elections with more than three voters. Nonetheless, the results are of theoretical importance, in particular, fixing this vulnerability is a prerequisite for any computational proof of ballot secrecy.
In Appendix [app:variant] we present a variant of our attack which violates the privacy of voters that cast votes for exactly one candidate, that is, voters that do not cast abstention votes. This attack has not previously been described in the literature, but would be thwarted by the additional checks – namely, checking that ballots do not contain ciphertexts that already exist on the bulletin board – proposed by Cortier & Smyth (**Smyth11:Helios?**), nevertheless, the attack methodology may be of interest.
# Solutions
The attack exploits a distinction between ballots cast for abstention and ballots cast for particular candidates: the homomorphic combination of ciphertexts inside a ballot for abstention contains the plaintext $0$ whereas the homomorphic combination of ciphertexts inside a ballot for a particular candidate contains the plaintext $1$. By comparison, in the electronic voting protocol by Hirt (**Hirt01:Thesis?**; **Hirt10:ThesisChap5?**) the dummy candidate ensures that the homomorphic combination of ciphertexts inside a ballot contains the plaintext $1$ and since such a homomorphic combination cannot be used to leak information, Hirt’s scheme is not vulnerable to this style of attack. Further work could consider whether the addition of a dummy candidate is sufficient for ballot secrecy in Helios, moreover, the cost of this revision could be considered; similarly, ballot secrecy could be evaluated in Hirt’s scheme, since no security proof has been published. (We stress that an extension of Helios using a dummy candidate is not an instance of Hirt’s scheme, because the signatures of knowledge used by these protocols are different.)
Cortier & Smyth (**Smyth10:Helios?**; **Smyth11:Helios?**) propose *ballot weeding* – namely, a ballot should not contain a ciphertext that already exists on the bulletin board – as a sufficient condition for ballot secrecy in Helios and successfully verify the security of their solution in the applied pi calculus. This analysis appears to be sound, but the model is incomplete, in particular, the homomorphic combination of an ElGamal ciphertext $(a,b)$ with $(1,1)$ is not captured. Omitting this detail can perhaps be justified by the requirement that “ciphertexts and signatures of knowledge should have a unique representation as *group elements*" (**Smyth11:Helios?**) (emphasis added), however, in hindsight, modelling this detail would have been useful.
Bernhard *et al.* (**Smyth11:HeliosProvableSecure?**) present a computational security proof demonstrating that any variant of Helios using an IND-CCA2 secure encryption scheme provides ballot secrecy and, more concretely, propose a variant using the Naor-Yung paradigm (**Naor90:ElGamal-PoK?**) to derive an IND-CCA2 secure encryption scheme from ElGamal. In this setting, each ciphertext must be supplemented with an additional signature of knowledge, however, it is sufficient to provide a single signature of knowledge for the homomorphic combination of ciphertexts contained in a ballot; it follows that the adversary cannot successfully submit a ballot derived from the homomorphic combination of a voter’s ciphertexts because the supplementary signature of knowledge cannot be constructed, therefore, the vulnerability highlighted in this paper cannot be exploited in the variant of Helios proposed by Bernhard *et al.* Intuitively, the use of ElGamal and a suitable signature of knowledge scheme allows us to derive an IND-CCA2 secure encryption scheme; indeed, Tsiounis & Yung (**Tsiounis98:ElGamal-PoK?**) and Schnorr & Jakobsson (**Schnorr00:ElGamal-PoK?**) provide some evidence to support this hypothesis, however, these results are presented in the generic group model and proving this result under weaker assumptions is an open problem (**Shoup98:ElGamal-PoK?**; **Shoup02:ElGamal-PoK?**). Nonetheless, it appears that a more efficient provably secure variant of Helios can be derived and future work could consider whether it is sufficient to revise ballot weeding as follows: a ballot should not contain a signature of knowledge that already exists on the bulletin board (Bernhard (**Bernhard12:private?**) and, independently, Clark (**Clarke12:private?**) suggest it is sufficient to check the challenges, moreover, Bernhard argues that it is necessary).
In principle, work in parallel by Bernhard, Pereira & Warinschi (**Bernhard11:Helios?**) supports the aforementioned proposal that the revised ballot weeding solution is sufficient for ballot secrecy: Bernhard, Pereira & Warinschi prove that an IND-CPA encryption scheme and a suitable signature of knowledge can be combined to derive NM-CPA security, and the *minivoting scheme* (**Smyth11:HeliosProvableSecure?**) is shown to satisfy ballot secrecy for any NM-CPA secure encryption scheme. Bernhard, Pereira & Warinschi argue that the minivoting scheme forms the basis of Helios and claim that Helios is therefore secure since the transformation from minivoting to Helios does not affect ballot secrecy. However, the minivoting scheme only considers ballots containing a single ciphertext, so any result in this restricted context is not sufficient to prove that Helios satisfies ballot secrecy, indeed, this paper demonstrates the contrary in the general case.
In a different direction, Gennaro (**Gennaro95:Independence:SK-voting?**), Cramer, Gennaro & Schoenmakers (**CramerGennaroSchoenmakers97:AdditiveElGamal?**) and Damgård, Jurik & Nielsen (**Damgard01:MultCandidateElections?**; **Damgard10:MultCandidateElections?**) enforce ballot independence by including the voter’s identity in signatures of knowledge, and Groth (**Groth04:VotingUC?**) analyses such protocols. However, Benaloh (**Benaloh06:BallotAudit?**; **Benaloh07:BallotAudit?**) argues that the ballot encryption device should not know the voter’s identity, since this information can be used to influence the behaviour of the ballot encryption device. The electronic voting protocol proposed by Juels, Catalano & Jakobsson (**JCJ05?**) – which has been implemented by Clarkson, Chong & Myers (**CCM08?**; **CCM08b?**) as Civitas – partially resolves this problem by binding ballots to private voter credentials, which cannot be linked to voters’ identities. Moreover, their solution provides *eligibility verifiability* (**Smyth10:ElectionVerifiability?**): anyone can check that each ballot published on the bulletin board was cast by a registered voter and at most one ballot is tallied per voter. It is likely that eligibility verifiability enforces ballot independence, but the provision of eligibility verifiability appears to be expensive, in particular, Juels, Catalano & Jakobsson and Clarkson, Chong & Myers assume the existence of an infrastructure for voter credentials. Accordingly, alternative solutions should be sought.
# Related work
The vulnerability highlighted in this paper is partly due to the lack of ballot independence in Helios. The concept of independence was introduced by Chor *et al.* (**Chor85:Independence?**) and the possibility of compromising security properties due to the lack of independence has been considered, for example, by (**Chor87:Independence?**; **Dolev91:Nonmalleable?**; **Dolev00:Nonmalleable?**; **Gennaro00:Independence?**). In the context of electronic voting, Gennaro (**Gennaro95:Independence:SK-voting?**) demonstrates that the application of the Fiat-Shamir heuristic in the Sako-Kilian electronic voting protocol (**SK94:Voting?**) violates ballot independence, and Wikström (**Wikstrom06:Independence?**; **Wikstrom08:Independence?**) studies non-malleability for mixnets to achieve ballot independence. By comparison, we focus on the violation of ballot secrecy rather than fairness, and exploit the absence of ballot independence to compromise privacy. Similar results have been shown against mixnets (**Pfitzmann94:MixnetAttack?**).
Our attack is also dependent upon the homomorphic properties of ElGamal which allow the adversary to derive a ballot related to an abstention vote cast by an honest voter, that is, the vulnerability is partly due to the possibility of constructing a ballot as a function of an honest voter’s ballot. In related work, Benaloh (**Benaloh96:Thesis?**) demonstrates that a simplified version of his voting scheme allows the administrator’s private key to be recovered by an adversary who constructs (and casts) a ballot as a function of other voters’ ballots.
Estehghari & Desmedt (**Estehghari10-Helios-attack?**) claim to present an attack which undermines privacy and end-to-end verifiability in Helios. However, their attack is dependent on compromising a voter’s computer, a vulnerability which is explicitly acknowledged by the Helios specification (**AdidaPereiraMarneffeQuisquater?**): *“a specifically targeted virus could surreptitiously change a user’s vote and mask all of the verifications performed via the same computer to cover its tracks."* Accordingly, (**Estehghari10-Helios-attack?**) represents an exploration of known vulnerabilities rather than an attack.
Other studies of Helios have also been conducted, in particular, Langer *et al.* (**Langer10:thesis?**; **Langer10:PrivacyTaxonomy:Helios?**) and Volkamer & Grimm (**Volkamer09:Helios?**) study privacy in Helios. Langer *et al.* propose a taxonomy of informal privacy requirements (**Langer10:thesis?**; **Langer10:PrivacyTaxonomy:Helios?**; **Langer09:PrivacyTaxonomy?**) to facilitate a more fine-grained comparison of electronic voting systems, this framework is used to analyse Helios and the authors claim ballot secrecy is satisfied if the adversary only has access to public data (**Langer10:thesis?**; **Langer10:PrivacyTaxonomy:Helios?**). Volkamer & Grimm introduce the *$k$-resilience* metric (**Volkamer09:Helios?**; **Volkamer09:VotingBook?**) to calculate the number of honest participants required for ballot secrecy in particular scenarios, this framework is used to analyse Helios and the authors claim ballot secrecy is satisfied if the software developers are honest and the key holders do not collude (**Volkamer09:Helios?**). Contrary to these results, we show an attack against privacy. We believe the erroneous results reported by Langer *et al.* were due to the use of informal methods, and the approach by Volkamer & Grimm failed because only some particular scenarios were considered.
# Conclusion
This paper identifies a vulnerability in the Helios 2.0 electronic voting protocol which can be used to violate ballot secrecy and an attack has been demonstrated against the current Helios implementation. Although the vulnerability does not pose a realistic threat to real-world elections, the results are of theoretical interest, in particular, resolving this vulnerability is a prerequisite to proving ballot secrecy in the computational model. In addition, the attack methodology may be of interest, since it could represent a viable threat against existing protocols in the literature.
# Acknowledgements
I am grateful to David Bernhard, Jeremy Clark and Olivier Pereira for their careful reading of draft versions of this paper and subsequent discussions; their feedback helped improve the paper.
# Signatures of knowledge
Helios is reliant on signatures of knowledge to ensure secrecy and integrity of the ElGamal scheme, and this appendix presents suitable cryptographic primitives.
## Knowledge of discrete logs
Given the aforementioned cryptographic parameters $(p,q,g)$, a signature of knowledge demonstrating knowledge of a discrete logarithm $h = \log_g g^x$ can be derived, and verified, as defined by (**Chaum86?**; **Chaum87?**; **Schnorr89:ProofDLog?**).
#### Sign.
Given $x$, select a random nonce $w \in_R \mathbb{Z}_q^*$. Compute witness $g' = g^w \bmod p$, challenge $c = \mathcal{H}(g') \bmod q$ and response $s = w + c \cdot x \bmod q$.
#### Verify.
Given $h$ and signature $g',s$, check $g^s \equiv g'\cdot h^c \pmod p$, where $c = \mathcal{H}(g') \bmod q$.
A valid proof asserts knowledge of $x$ such that $x = \log_g h$; that is, $h \equiv g^x \bmod p$.
## Equality between discrete logs
Given the aforementioned cryptographic parameters $(p,q,g)$, a signature of knowledge demonstrating equality between discrete logarithms $\log_f f^x$ and $\log_g\allowbreak g^x$ can be derived, and verified, as defined by (**Pedersen91:ThresholdElGamal?**; **Pedersen92?**).
#### Sign.
Given $f,g,x$, select a random nonce $w \in_R \mathbb{Z}_q^*$. Compute witnesses $f' = f^w \bmod p$ and $g' = g^w \bmod p$, challenge $c = \mathcal{H}(f',g') \bmod q$ and response $s = w + c \cdot x \bmod q$.
#### Verify.
Given $f,g,h,k$ and signature $f',g',s$, check $f^s \equiv f'\cdot h^c \pmod p$ and $g^s \equiv g'\cdot k^c \pmod p$, where $c = \mathcal{H}(f',g') \bmod q$.
A valid proof asserts $\log_f h = \log_g k$; that is, there exists $x$, such that $h \equiv f^x \bmod p$ and $k \equiv g^x \bmod p$.
For our purposes, given a ciphertext $(a,b)$, each trustee would derive a signature on $g,a,x_i$, where $x_i$ is the trustee’s private key share. The $i$th trustee’s signature $g'_i,a'_i,c_i,s_i$ would be verified with respect to $g,a,h_i,k_i$, where $h_i$ is the trustee’s share of the public key and $k_i$ is the trustee’s partial decryption; that is, the proof asserts $\log_g h_i = \log_a k_i$, as required for integrity of decryption.
# A variant of our attack
This appendix presents a variant of the attack described in Section [sec:privacy] which violates the privacy of voters in the original Helios scheme, but is thwarted by the solution proposed by Cortier & Smyth (**Smyth11:Helios?**). Let us suppose the bulletin board is given in Section [sec:attack:description] and the adversary selects $ciph_{k,1},\dots,ciph_{k,\ell}, spk_{k,1},\allowbreak \dots, spk_{k,\ell}, spk'_k$ such that $id_k$ is the voter under attack, where $k\in\{1,2\}$. The adversary selects integer $v\in\{1,\dots,\ell\}$ and the attack proceeds as follows.
#### Constructing a related ballot.
The adversary constructs the following related ballot: $$\begin{gathered}
\underbrace{(1,1),\dots,(1,1)}_{\textrm{$v-1$ times}},
(a_{k,v}, b_{k,v}),
\underbrace{(1,1),\dots,(1,1)}_{\textrm{$\ell-v$ times}},\\
\widebar{spk}_1,\dots,\widebar{spk}_{v-1},spk_{k,v},\widebar{spk}_{v+1},\dots,\widebar{spk}_{\ell}, spk_{k,v}
\end{gathered}$$ where for all $j \in\{1,\dots,v-1,v+1,\dots,\ell\}$ the signature $\widebar{spk}_j$ is constructed in accordance with the definition given in Lemma [lem]. It follows immediately for all $j \in\{1,\dots,v-1,v+1,\dots,\ell\}$ that $\widebar{spk}_j$ is a valid proof for $(1,1)$. Moreover, it is trivial to witness that $spk_{k,v}$ is a valid proof for $(a_{k,v}, b_{k,v})$ and, therefore, $spk_{k,v}$ is a valid proof for the homomorphic combination of ciphertexts encapsulated in the adversary’s ballot. Accordingly, the adversary’s ballot will be accepted by the bulletin board, hence, we have informally shown another technique to violate ballot independence in Helios: observing another voter’s interaction with the election system allows a voter to cast a *related* vote, in particular, if a voter votes for candidate $t_v$ or $\epsilon$, then the *same* vote can be cast, otherwise, a *different* vote (namely, $\epsilon$) can be cast. The absence of ballot independence will now be exploited to violate privacy.
#### Violating privacy.
The homomorphic addition of ballots reveals the encrypted tally $(A_1,B_1),\dots,(A_\ell,B_\ell)$ defined as follows: $$\begin{gathered}
(a_{1,1} \cdot a_{2,1},\;b_{1,1} \cdot b_{2,1}),\dots,
(a_{1,v-1} \cdot a_{2,v-1},\;b_{1,v-1} \cdot b_{2,v-1}),\\
(a_{1,v} \cdot a_{2,v} \cdot a_{k,v},\;b_{1,v} \cdot b_{2,v} \cdot b_{k,v}),\\
(a_{1,v+1} \cdot a_{2,v+1},\;b_{1,v+1} \cdot b_{2,v+1}),\dots,
(a_{1,\ell} \cdot a_{2,\ell},\;b_{1,\ell} \cdot b_{2,\ell})
\end{gathered}$$ Given the partial decryptions, the tally can be decrypted to reveal the number of votes for each candidate. If the tally contains two votes for some candidate, one vote for some other candidate, and no votes for abstention, then the honest voter with identity $id_k$ cast a vote for the candidate with two votes and hence privacy is not preserved. Moreover, the vote of the remaining honest voter will also be revealed.
If $g^2\cdot h^r \in \{B_1,\allowbreak\dots,B_\ell\}$ and there exists $w\in\{1,\dots,\ell\}$ such that $B_w = g^1\cdot h^s$ for some $r$ and $s$, then the following conditions are satisfied:
1. $b_{k,v} = g^1\cdot h^{\hat r}$ for some $\hat r$; and
2. $b_{k',w} = g^1\cdot h^{\hat s}$ for some $\hat s$, where $k'\in\{1,2\}\backslash\{k\}$.
The precondition of Theorem [thmm] is an immediate consequence of the tally containing two votes for some candidate, one vote for some other candidate, and no votes for abstention. Postcondition (1) asserts that the voter with identity $id_k$ voted for candidate $t_v$ and Postcondition (2) asserts that the remaining voter voted for the candidate $t_w$.