# 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 a digital setting, ballots are sent using publicly readable communications channels and, in end-to-end verifiable elections, stored on a publicly readable bulletin board. Nevertheless, the provision of ballot independence is important to ensure privacy, as demonstrated in our earlier work (**Smyth10:Helios?**; **Smyth11:Helios?**) who exploit the lack of ballot independence in Helios 2.0 (**AdidaPereiraMarneffeQuisquater?**) to violate ballot secrecy.

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.

In addition to the apparent relationship between ballot independence and privacy, ballot independence is important because it prohibits the voting system from influencing a voter’s behaviour; more formally, this requires that observation of the voting system (that is, observing interaction between participants) does not leak information that may affect a voter’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.

Other desirable properties of electronic voting systems include verifiability (**JCJ02?**; **DagstuhlAccord07?**; **Smyth10:ElectionVerifiability?**).

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.

Eligibility verifiability.  
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.

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.

We (**Smyth10:Helios?**; **Smyth11:Helios?**) have shown in Helios 2.0 it is possible to replay a voter’s ballot (without knowing the vote contained within that ballot). This immediately violates ballot secrecy in an election with three voters. For example, consider the electorate Alice, Bob, and Mallory; 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.

#### Contribution.

We take two schemes presented at CRYPTO – namely, the protocols due to Sako & Kilian (**SK94:Voting?**) and Schoenmakers (**Schoenmakers99:PVSS?**) – that are known not to satisfy ballot independence and show that these protocols are both vulnerable to replay attacks that violate privacy.

The study of Sako & Kilian (**SK94:Voting?**) is interesting because it was one of the first electronic voting protocols to adopt the Fiat-Shamir heuristic to derive non-interactive proofs (this evolution was key for the development of end-to-end verifiable electronic voting systems). However, we will show that the application of the Fiat-Shamir heuristic compromises ballot secrecy. In particular, the interactive nature of zero-knowledge proofs guarantees ballot independence; whereas, non-interactive proofs, derived using the Fiat-Shamir heuristic, do not assure independence. This can be exploited by a replay attack to violate ballot secrecy.

In earlier work (**Smyth10:Helios?**; **Smyth11:Helios?**), we acknowledge that our attack against Helios may not be practical in large-scale elections, but it is particularly well suited to small-scale elections. The scheme by Schoenmakers (**Schoenmakers99:PVSS?**) was explicitly designed for small-scale elections (for example, boardroom elections) and, hence, we find it interesting to study the possibility of violating ballot secrecy in this setting. Once again, we violate privacy using a replay attack.

#### Related work.

The concept of independence was introduced by Chor *et al.* (**Chor85:Independence?**) and the possibility of compromising security properties due to lack of independence has been considered, for example, by Chor & Rabin (**Chor87:Independence?**), Dolev, Dwork & Naor  (**Dolev91:Nonmalleable?**; **Dolev00:Nonmalleable?**) and Gennaro (**Gennaro95:Independence:SK-voting?**; **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 ballot independence.

# Sako-Kilian voting protocol

The Sako & Kilian (**SK94:Voting?**) electronic voting scheme capitalises upon advances in cryptography to improve the Banaloh & Yung protocol (**Benaloh86?**). In particular, the Fiat-Shamir heuristic is adopted to derive non-interactive proofs of knowledge.

## Protocol description

The scheme is based upon a pair of *partially compatible homomorphic encryption* functions, that is, a pair of functions $f_{1},f_{2}$ over $\mathbb{Z}_q$, where $q$ is prime, such that for all $i,j\in\{1,2\}$ the following properties are satisfied:

- $f_{i}(x+y) = f_{i}(x) \cdot f_{i}(y)$, where $x,y\in\mathbb{Z}_q$

- Distributions $(f_{i}(x),f_{j}(y))$ and $(f_{i}(x),f_{j}(x))$ are computationally indistinguishable, where $x$ and $y$ are chosen uniformly in $\mathbb{Z}_q$.

The Sako-Kilian voting protocol is defined for $m\in\mathbb{N}$ voters as follows.

#### Setup.

Talliers $\mathcal{T}$ and $\mathcal{T}'$ publish public keys $k$ and $k'$ for a public key encryption scheme $E$ (which need not be homomorphic).

#### Voting.

Given vote $v_i\in\{-1,1\}$, the voter generates nonces $x_i,x'_i\in\mathbb{Z}_q$ such that $v_i = x_i + x'_i$ and constructs her ballot as follows: $$\begin{array}{lcl}
	Y_i &=& f_{1}(x_i)\\
	Y'_i &=& f_{2}(x'_i)\\
	Z_i &=& E(k,x_i)\\
	Z'_i &=& E(k',x'_i)
\end{array}$$ In addition, the voter is required to prove $x_i + x'_i \in \{1,-1\}$ in zero-knowledge. However, to avoid an interactive proof, the Fiat-Shamir heuristic is applied to derive a signature of knowledge $\sigma_i$. (For brevity we omit the construction of $\sigma_i$, see (**SK94:Voting?**) for details.)

#### Tallying.

Given ballots $Y_1,Y'_1,Z_1,Z'_1,\sigma_1,\dots,Y_n,Y'_n,Z_n,Z'_n,\sigma_n$, tallier $\mathcal{T}$ decrypts each $Z_i$ to recover $\hat x_i$ and checks $Y_i = f_{1}(\hat x_i)$, similarly, tallier $\mathcal{T}'$ decrypts $Z'_i$ to recover $\hat x'_i$ and checks $Y'_i = f_{1}(\hat x'_i)$; the talliers also check the signature of knowledge $\sigma_i$. The talliers publish $V = \sum_{i=1}^m \hat x_i$ and $V' = \sum_{i=1}^m \hat x'_i$, and the result is $T = V + V'$, which can be verified by checking $f_{1}(V) = \prod_{i=1}^m Y_i$ and $f_{2}(V') = \prod_{i=1}^m Y'_i$.

## Attacking ballot secrecy

Ballot secrecy means a voter’s vote is not revealed to anyone. We show that Sako-Kilian voting protocol does not satisfy this definition of ballot secrecy, by presenting a replay attack which allows an adversary to reveal a voter’s vote.

Intuitively, an adversary may observe the ballot posted by a particular voter and recast this ballot by corrupting dishonest voters. The multiple occurrences of the voter’s ballot will leak information in the tally and the adversary can exploit this knowledge to violate the voter’s privacy. An informal description of the attack will now be presented in the case of three eligible voters.

### Attack description.

Let us consider an election with three eligible voters who have identities $id_1$, $id_2$ and $id_3$. Suppose that voters $id_1$, $id_2$ are honest and $id_3$ is a dishonest voter controlled by the adversary. Further assume that the adversary has observed the ballot $$Y_k,Y'_k,Z_k,Z'_k,\sigma_k$$ being cast by the voter whose privacy will be compromised.

#### Exploiting the absence of ballot independence.

As shown by Gennaro (**Gennaro95:Independence:SK-voting?**), an adversary can replay the ballot $Y_k,Y'_k,Z_k,Z'_k,\sigma_k$, thereby violating ballot independence. (The violation of ballot independence is due to the adversary’s ability to cast the *same* vote as the honest voter.) Since the ballot was constructed by an honest voter, it is trivial to see that it will be considered valid by the talliers. We will now show how the lack of ballot independence can be exploited to violate privacy.

#### Violating privacy.

The bulletin board will be constructed as follows $$Y_1,Y'_1,Z_1,Z'_1,\sigma_1,Y_2,Y'_2,Z_2,Z'_2,\sigma_2,Y_k,Y'_k,Z_k,Z'_k,\sigma_k,V,V'$$ where $k\in\{1,2\}$, $V = x_1 + x_2 + x_k$ and $V' = x'_1 + x'_2 + x'_k$. It follows from the protocol description that $v_i = x_i + x'_i$, where $i\in\{1,2,k\}$, and the result $T = V + V' = v_1 + v_2 + v_k$. Since there will be at least two votes for the candidate voter $id_k$ voted for, the voter’s vote can be revealed: if $T \geq 2$, then $v_k = 1$; otherwise $v_k = -1$. It follows that the voter’s privacy has been compromised; moreover, the vote of the remaining honest voter is $T - 2 \cdot v_k$.

# Schoenmakers’s voting protocol

The electronic voting scheme by Schoenmakers (**Schoenmakers99:PVSS?**) is based upon (**CramerFranklinSchoenmakersYung96?**; **CramerGennaroSchoenmakers97:AdditiveElGamal?**) and aims to provide efficient small-scale elections. Ballot independence is explicitly not provided (**Schoenmakers99:PVSS?**).

## Protocol description

Given cryptographic parameters $(G_q,g,h)$ and hash function $\mathcal{H}$, where $G_q$ is a group of prime order $q$ such that computing discrete logarithms is infeasible and $g,h$ are distinct generators of $G_q$, let us recall the scheme for $n\in\mathbb{N}$ talliers and $m\in\mathbb{N}$ voters using some threshold $t\leq n$.

#### Setup.

Each tallier $i\in n$ selects a private key $x_i \in_R \mathbb{Z}_q^*$ and computes the public part $y_i = h^{x_i}$.

#### Voting.

The voter selects coefficients $\alpha_0,\dots,\alpha_{t-1}\in_R \mathbb{Z}^*_q$ and constructs the polynomial $\rho$: $$\rho(x) = \alpha_0 \cdot x^0 + \dots + \alpha_{t-1}\cdot x^{t-1}$$ Given vote $v\in\{0,1\}$, the ballot consists of the following components:

- Vote: $U = h^{\alpha_0+v}$.

- Commitments: $C_j = g^{\alpha_j}$, where $0\leq j \leq t-1$.

- Random shares: $Y_i = y_i^{\rho(i)}$, where $1 \leq i \leq n$.

In addition, the ballot includes a signature proof of knowledge (**Pedersen91:ThresholdElGamal?**; **Pedersen92?**) demonstrating the correct construction of encrypted shares and a signature proof of knowledge (**Schoenmakers94:Proof-of-ciphertext?**) demonstrating that $v\in\{0,1\}$:

- Proof of correct construction. Let $X_i = \prod_{j=0}^{t-1} (C_j)^{i^j}$, where $1 \leq i \leq n$. For all $1 \leq i \leq n$, select a random nonce $w_i \in_R \mathbb{Z}_q^*$ and compute witnesses $a_i = g^{w_i}$, $b_i = y_i^{w_i}$. Derive the common challenge $c = \mathcal{H}(X_1,Y_1,a_1,b_1,\dots,X_n,Y_n,a_n,b_n)$, and for all $1 \leq i \leq n$ compute response $r_i = w_i - {c \cdot \rho(i)}$.

- Proof of valid vote. Compute challenge $\hat c_{1-v} \in_R \mathbb{Z}_q^*$, response $\hat r_{1-v} \in_R \mathbb{Z}_q^*$ and witnesses $\hat a_{1-v} = g^{r_{1-v}} \cdot C_0^{\hat c_{1-v}}$ and $b_{1-v} = h^{r_{1-v}} \cdot (U/ h^{1-v})^{\hat c_{1-v}}$. Select a random nonce $\hat w \in_R\mathbb{Z}_q^*$. Compute witnesses $\hat a_v = g^w$ and $\hat b_v = h^w$, challenge $\hat c_v = \mathcal{H}(\hat a_0,\hat b_0,\hat r_0, \hat a_1,\hat b_1, \hat r_1) - \hat c_{1-v}$ and response $r_v = w - {\alpha_0\cdot \hat c_v}$.

To prevent a voter casting multiple ballots, the ballots are assumed to be associated with the voter’s identity on the bulletin board.

#### Verification.

For each ballot $U,C_0,\dots,C_{t-1},Y_1,\dots,Y_n$ and associated proofs $a_1,b_1,r_1\dots,a_n,b_n,r_n$ and $\hat a_1,\hat b_1,\hat c_1,\hat r_1,\hat a_2,\hat b_2,\hat c_2,\hat r_2$, check for all $1 \leq i \leq n$ and $v\in\{0,1\}$ that $$\begin{array}{lcl c lcl c lcl}
	a_i &=& g^{r_i} \cdot X_i^c & \qquad &
		b_i &=& y_i^{r_i} \cdot Y_i^c & \qquad\\
	\hat a_v &=& g^{\hat r_v} \cdot C_0^{\hat c_v} & &
		\hat b_v &=& h^{\hat r_v} \cdot (U/h^{v})^{\hat c_v} & &
	\hat c_0 + \hat c_1 &=&  \mathcal{H}(\hat a_0,\hat b_0,\hat a_1,\hat b_1) 
\end{array}$$ where $X_i = \prod_{j=0}^{t-1} (C_j)^{i^j}$ and $c = \mathcal{H}(X_1,Y_1,a_1,b_1,\dots,X_n,Y_n,a_n,b_n)$. (Observe $X_i = g^{\sum_{j=0}^{t-1} \alpha_j \cdot i^j} = g^{\rho(i)}$.)

#### Tallying.

Given encrypted shares $Y_{1,1},\dots,Y_{1,n},\cdots,Y_{m,1},\dots,Y_{m,n}$ of $m$ voters, the homomorphic combination of encrypted shares $Y^*_i$ is derived, where $1\leq i\leq n$: $$Y^*_i = \prod_{j=1}^m Y_{j,i}$$ Let $\rho_j$ denotes the $j$th voter’s secret polynomial. For all $1\leq i \leq n$, each tallier derives the partial decryption $V_i = (Y_i^*)^{1/x_i}$; since $Y^*_i = y_i^{\sum_{j=1}^m \rho_j(i)} = h^{x_i \cdot \sum_{j=1}^m \rho_j(i)}$, it follows that $V_i = h^{\sum_{j=1}^m \rho_j(i)}$. The talliers must also prove correctness of decryption; it is sufficient to prove equality between discrete logarithms $\log_{h} y_i$ and $\log_{V_i} Y^*_i$, we omit these details.

Given partial decryptions $V_{1},\dots,V_{t}$ from $t$ talliers, we can compute $V = h^{\sum_{j=1}^{m} \alpha_{j,0}}$ as shown below, where $\alpha_{j,0}$ is the $j$th voter’s first coefficient and, for simplicity, $t = n$. Let Lagrange coefficient $\lambda_i = \prod_{l\in\{1,\dots,i-1,i+1,\dots,n\}} \frac{l}{l-i}$, where $1\leq i \leq n$. $$\prod_{i=1}^n V_i^{\lambda_i}
		= \prod_{i=1}^n \left(h^{\sum_{j=1}^m \rho_j(i)}\right)^{\lambda_i}
		= h^{\sum_{j=1}^{m}\left(\sum_{i=1}^n\rho_j(i)\cdot\lambda_i\right)}
		= h^{\sum_{j=1}^{m}\rho_j(0)}
%		= h^{\sum_{j=1}^{m} \alpha_{j,0}}  
		= V$$ The result $T = \sum_{j=1}^m v_j$ can be derived as follows, where $v_j$ is the $j$th voter’s vote. $$\log_h \prod_{j=1}^m U_j - \log_h V 
		= \log_h h^{\sum_{j=1}^m \alpha_{j,0} + v_j} - \log_h h^{\sum_{j=1}^{m} \alpha_{j,0}}
		= \log_h h^{\sum_{j=1}^m v_j}
		= T$$ Although the computation of discrete logarithms is hard in general, given the restricted domain $[0,m]$, the result $T$ can be computed efficiently; for example, the complexity is $O(m)$ by linear search or $O(\sqrt m)$ using the baby-step giant-step algorithm (**Shanks69?**) (see also (**Lenstra90?**)).

## Attacking ballot secrecy

We show that Schoenmakers’s voting protocol does not satisfy ballot secrecy, by presenting a replay attack which allows an adversary to reveal a voter’s vote. Intuitively, an adversary may identify a voter’s ballot on the bulletin board (since it is linked to the voter’s identity) and recast this ballot by corrupting dishonest voters. As previously discussed, the multiple occurrences of the voter’s ballot will leak information in the tally and the adversary can exploit this knowledge to violate the voter’s privacy. An informal description of the attack will now be presented in the case of three eligible voters.

### Attack description.

Let us consider an election with $n$ talliers and three eligible voters who have identities $id_1$, $id_2$ and $id_3$. Suppose that voters $id_1$, $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, e_1, spk_1, spk'_1\\ 
id_2, e_2, spk_2, spk'_2\\
\end{array}$$ where for $i\in\{1,2\}$ we have $$\begin{array}{lcl}
	e_i &=& U_i,C_{i,0},\dots,C_{i,t-1},Y_{i,1},\dots,Y_{i,n} \\
	spk_i &=& a_{i,1},b_{i,1},r_{i,1}\dots,a_{i,n},b_{i,n},r_{i,n} \\
	spk'_i &=& a_{i,1},\hat b_{i,1},\hat c_{i,1},\hat r_{i,1},\hat a_{i,2},\hat b_{i,2},\hat c_{i,2},\hat r_{i,2}
\end{array}$$ That is, $e_i$ contains the $i$th voter’s vote $U_i$, commitments $C_{i,0},\dots,C_{i,t-1}$ and random shares $Y_{i,1},\dots,Y_{i,n}$; $spk_i$ demonstrates that the random shares are correctly formed; and $spk'_i$ demonstrates that $U_i$ contains either $0$ or $1$.

#### Exploiting the absence of ballot independence.

The adversary observes the bulletin board and selects $e_k,spk_k,spk'_k$ where $k\in\{1,2\}$ and $id_k$ is the voter whose privacy will be compromised. The adversary submits the ballot $e_k,spk_k,spk'_k$ and it immediately follows that the bulletin board is composed as follows: $$\begin{array}{c}
	id_1, e_1, spk_1, spk'_1 \\
	id_2, e_2, spk_2, spk'_2 \\
	id_3, e_k, spk_k, spk'_k \\
\end{array}$$ It is trivial to see that each bulletin board entry is valid; that is, $spk_1, spk'_1, spk_2,\allowbreak spk'_2, spk_k, spk'_k$ are all valid signatures of knowledge. We have shown that the protocol does not satisfy ballot independence (observing another voter’s interaction with the election system allows a voter to cast the *same* vote), and this will now be exploited to violate privacy.

#### Violating privacy.

The partial decryptions of the homomorphic combination of encrypted shares can be used to reveal the result $T = \log_h h^{v_1 + v_2 + v_k}$, where $k \in \{1,2\}$ and $v_1$, $v_2$ are the votes of honest voters. Since there will be at least two votes for the candidate voter $id_k$ voted for, the voter’s vote can be revealed: if $T \geq 2$, then $v_k = 1$; otherwise $v_k = 0$. It follows that the voter’s privacy has been compromised; moreover, the vote of the remaining honest voter is $T - 2 \cdot v_k$.

# Discussion

We have informally shown that the protocols due to Sako & Kilian (**SK94:Voting?**) and Schoenmakers (**Schoenmakers99:PVSS?**) are vulnerable to a replay attack which violates ballot secrecy. In this section we briefly discuss how application of the Fiat-Shamir heuristic may erode privacy, examine how the attacks can be extended beyond the three voter setting, and explore the attacks in the context of standard security definitions.

#### Independence and the Fiat-Shamir heuristic.

The interactive nature of zero-knowledge proofs guarantees independence; by comparison, non-interactive proofs, derived using the Fiat-Shamir heuristic, do not assure independence. As a consequence, application of the Fiat-Shamir heuristic may compromise the security of cryptographic protocols and this paper has shown how ballot secrecy in electronic voting schemes can be violated.

#### Generalised attacks against ballot secrecy.

Our attacks demonstrate that the ballot of an arbitrary voter can be replayed by any other voter. In general, this does not reveal the voter’s vote. However, some information is leaked, and colluding voters can replay sufficiently many ballots to leak the voter’s vote. Moreover, we have previously shown that there is a realistic threat from a small coalition of dishonest voters (**Smyth10:Helios?**; **Smyth11:Helios?**).

#### Violating standard definitions of ballot secrecy.

Intuitively, it should follow that the protocols due to Sako & Kilian (**SK94:Voting?**) and Schoenmakers (**Schoenmakers99:PVSS?**) cannot satisfy ballot secrecy in formal settings defined by Kremer *et al.* (**KR05:vote-privacy?**; **DKR08?**) and Backes, Hriţcu & Maffei (**Backes08:Voting?**). These privacy definitions consider two voters $\mathcal{A}$, $\mathcal{B}$ and two candidates $t$, $t'$. Ballot secrecy is captured by the assertion that an adversary (controlling arbitrary many dishonest voters) cannot distinguish between a situation in which voter $\mathcal{A}$ votes for candidate $t$ and voter $\mathcal{B}$ votes for candidate $t'$, from another one in which $\mathcal{A}$ votes $t'$ and $\mathcal{B}$ votes $t$. This can be expressed by the following equivalence. $$\mathcal{A}(t)\mid\mathcal{B}(t') \approx \mathcal{A}(t')\mid\mathcal{B}(t)$$ Formally proving that these protocols do not satisfy these definitions is beyond the scope of this paper. However, informally this result can be trivially witnessed and we deduce either: these definitions are too strong, or there are indeed weaknesses in the protocols we have studied.