# First-past-the-post suffices for ranked voting

Ben Smyth

September 11, 2017  
(Revised September 19, 2018)

## Abstract

This manuscript introduces a technique that enables first-past-the-post voting systems to be used for ranked voting and applies the technique to the Helios voting system.

# Introduction

Smyth, Frink & Clarkson (Smyth, Frink, and Clarkson 2017, sec. 2) investigate the class of voting systems that consist of the following four steps. First, a tallier generates a key pair and (optionally) a registrar generates credentials for voters. Secondly, each voter constructs and casts a ballot for their preferred candidate. Thirdly, the tallier tallies the ballots and announces a frequency distribution of candidate preferences. Finally, voters and other interested parties check that the distribution corresponds to preferences expressed in ballots. This class includes first-past-the-post voting systems.

#### Contribution.

This manuscript introduces a technique that enables first-past-the-post voting systems to be used for ranked voting (§<a href="#sec:technique" data-reference-type="ref" data-reference="sec:technique">2</a>) and applies the technique to the Helios voting system (§<a href="#sec:helios" data-reference-type="ref" data-reference="sec:helios">3</a>).

# Ranked voting from first-past-the-post

Rankings can be represented as candidates and voters can cast ballots for the candidate that represents their ranking.[^1] Such ballots can be tallied to derive the frequency distribution of rankings and the winner can be determined from this distribution. For instance, rankings $A{>}B{>}C$, $A{>}C{>}B$, $B{>}A{>}C$, $B{>}C{>}A$, $C{>}A{>}B$ and $C{>}B{>}A$ can be represented as candidates 1–6. Moreover, given two ballots for candidate $1$, one ballot for candidate $4$ and one ballot for candidate $6$, tallying produces frequency distribution $A{>}B{>}C{:}2$, $A{>}C{>}B{:}0$, $B{>}A{>}C{:}0$, $B{>}C{>}A{:}1$, $C{>}A{>}B{:}0$, $C{>}B{>}A{:}1$, from which candidate $A$ can be determined as the winner.

Rankings can always be mapped to candidates using this technique. However, the technique cannot be applied to all voting systems, because voting systems may bound the number of candidates. For instance, a voting system for referendums may implicitly bound the number of candidates to two, hence, that voting system cannot be used to rank three candidates, since the six possible rankings cannot be mapped to two candidates.

# Case study: Helios

Applicability of the technique, and complexity implications, can be shown by applying it to the Helios voting system in each of its two tallying modes.

## Tallying by homomorphic combinations

Helios with tallying by homomorphic combination of ciphertexts (Adida et al. 2009) works as follows.

1.  The tallier generates a key pair for an asymmetric additively-homomorphic encryption scheme, proves correct key generation in zero-knowledge, and outputs the public key coupled with the proof.

2.  A voter selects their preferred candidate $v$ from a list of candidates $1,\dots,\ell$ and computes ciphertexts $\mathsf{Enc}(\mathit{pk},m_1),\dots,\mathsf{Enc}(\mathit{pk},m_{\ell-1})$ such that if $v<\ell$, then plaintext $m_v$ is $1$ and the remaining plaintexts are all $0$, otherwise, all plaintexts are $0$. The voter also computes proofs $\sigma_1,\dots,\sigma_\ell$ so that this can be verified. The voter casts the ciphertexts and proofs as their ballot.

3.  The tallier forms a matrix of ciphertexts from ballots for which all proofs hold, homomorphically combines the ciphertexts in each column to derive the encrypted frequency distribution of candidate preferences, decrypts those homomorphic combinations to reveal the frequencies of candidates $1,\dots,\ell-1$, computes the frequency of candidate $\ell$ by subtracting the frequencies of other candidates from the number of rows in the matrix, and announces the frequencies, along with proofs demonstrating correct decryption.

4.  Voters and other interested parties recompute the homomorphic combination, check proofs, and accept the frequency distribution if these checks succeed.

Hence, in the context of the example given in Section <a href="#sec:technique" data-reference-type="ref" data-reference="sec:technique">2</a>, the technique leads to the following matrix of ciphertexts: $$\begin{aligned}
{5}
		&\mathsf{Enc}(\mathit{pk},1) &\hspace*{2\arraycolsep}
			& \mathsf{Enc}(\mathit{pk},0) &\hspace*{2\arraycolsep}
			& \mathsf{Enc}(\mathit{pk},0) &\hspace*{2\arraycolsep} 
			& \mathsf{Enc}(\mathit{pk},0) &\hspace*{2\arraycolsep} 
			& \mathsf{Enc}(\mathit{pk},0) \\
%
		&\mathsf{Enc}(\mathit{pk},0) 
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},0) \\
%
		&\mathsf{Enc}(\mathit{pk},0) 
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},1)
			&& \mathsf{Enc}(\mathit{pk},0) \\
%
		&\mathsf{Enc}(\mathit{pk},1) 
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},0)
%
\intertext{These ciphertexts will be homomorphically combined to derive ciphertexts} 
%
		&\mathsf{Enc}(\mathit{pk},2) 
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},0)
			&& \mathsf{Enc}(\mathit{pk},1)
			&& \mathsf{Enc}(\mathit{pk},0)
%
\intertext{and decrypted to reveal frequencies}
		&A{>}B{>}C{:}2 && A{>}C{>}B{:}0 && B{>}A{>}C{:}0 && B{>}C{>}A{:}1 && C{>}A{>}B{:}0, 
\end{aligned}$$ which permit the deduction of frequency $C{>}B{>}A{:}4-2-1$. This shows that the technique can be applied to derive a ranked voting system. However, ballots include $\ell!-1$ ciphertexts and $\ell$ proofs, where $\ell$ is the number of candidates. Moreover, tallying requires $(n-1)\cdot(\ell!-1)$ homomorphic combinations and $\ell!-1$ proofs, where $n$ is the number of ballots with valid proofs. Such complexity is avoided when applying the technique to Helios’s other tallying mode.

## Tallying by mixnet

Helios with tallying by mixnet (Adida 2008; Bulens, Giry, and Pereira 2011; Smyth 2018b) works as follows.

1.  As per the previous tallying mode, without requiring that the asymmetric homomorphic encryption scheme is additively-homomorphic.

2.  A voter encrypts their preferred candidate, proves correct ciphertext construction, and casts the ciphertext coupled with the proof as their ballot.

3.  The tallier discards any ballots for which proofs do not hold, mixes the ciphertexts in the remaining ballots, decrypts the ciphertexts output by the mix to reveal the frequency distribution of candidate preferences, and announces that distribution, along with proofs demonstrating correct decryption.

4.  Voters and other interested parties check the proofs and accept the frequency distribution if these checks succeed.

Hence, in the context of the example given in Section <a href="#sec:technique" data-reference-type="ref" data-reference="sec:technique">2</a>, the technique results in the following: $$\begin{aligned}
	\begin{array}{llll}
		\mathsf{Enc}(\mathit{pk},1) &     													 & \mathsf{Enc}(\mathit{pk},6) & C{>}B{>}A\\
		\mathsf{Enc}(\mathit{pk},6) & \multirow{2}{*}{\textrm{Mix}} & \mathsf{Enc}(\mathit{pk},1) & A{>}B{>}C\\
		\mathsf{Enc}(\mathit{pk},4) &    												   & \mathsf{Enc}(\mathit{pk},1) & A{>}B{>}C\\
		\mathsf{Enc}(\mathit{pk},1) &     												   & \mathsf{Enc}(\mathit{pk},4) & B{>}C{>}A\\
	\end{array}
\end{aligned}$$ This permits the frequency distribution of candidate preferences to be derived. Again showing that the technique can be applied to derive a ranked voting system. Moreover, the complexity of the previous application is avoided. Indeed, ballots include just a single ciphertext and a single proof.

# Security considerations

To enable first-past-the-post voting systems to be used for ranked voting, we represent rankings as candidates. No changes to the underlying voting system are required. Hence, ranked voting can be achieved with the same security as the underlying system. That is, any security statement that holds for all candidates, also holds for rankings, because rankings are represented as candidates and security statements must hold for all candidates. It follows, for instance, that a voting system satisfying the definition of ballot secrecy by Smyth (Smyth 2018a), assures that a voter’s ranking is not revealed to anyone (since candidates cannot be revealed). Moreover, a voting system satisfying definitions of universal and individual verifiability by Smyth, Frink & Clarkson (Smyth, Frink, and Clarkson 2017), assures that anyone can check whether an outcome corresponds to rankings expressed in collected ballots (since checks can be performed for candidates) and a voter can check whether their ballot is collected (since the statement is independent of candidates and rankings). Nonetheless, security guarantees beyond what can be derived from the underlying system might be desired. For example, it might be desired that relative rankings between losing candidates are not revealed, which is not possible in our context.

# Related work

Clarkson, Chong & Myers (Clarkson, Chong, and Myers 2007, sec. 8) propose an encoding of rankings as matrices such that cell $i,j$ is $1$ if candidate $i$ is favoured over candidate $j$ and $0$ otherwise. (Ties between candidates are expressed when cells $i,j$ and $j,i$ are equal.[^2]) This encoding allows intransitive preferences. E.g., a voter might express a preference for $A$ over $B$, $B$ over $C$, and $C$ over $A$. And an additional mechanism is required to avoid such intransitivity (zero-knowledge proofs are suggested). Clarkson, Chong & Myers explain how their encoding could be used to enable ranked voting with Civitas in a manner that avoids covert channels.

# Conclusion

This manuscript introduces a technique that enables first-past-the-post voting systems to be used for ranked voting. The technique involves representing rankings as candidates. Hence, the underlying voting system does not require redesign. Thereby permitting ranked voting with the same security as the underlying system.

# References

<div id="refs" class="references csl-bib-body hanging-indent" entry-spacing="0">

<div id="ref-Adida08" class="csl-entry">

Adida, Ben. 2008. “<span class="nocase">Helios: Web-based Open-Audit Voting</span>.” In *USENIX Security’08: 17th USENIX Security Symposium*, 335–48. USENIX Association.

</div>

<div id="ref-AdidaPereiraMarneffeQuisquater" class="csl-entry">

Adida, Ben, Olivier de Marneffe, Olivier Pereira, and Jean-Jacques Quisquater. 2009. “<span class="nocase">Electing a University President Using Open-Audit Voting: Analysis of Real-World Use of Helios</span>.” In *EVT/WOTE’09: Electronic Voting Technology Workshop/Workshop on Trustworthy Elections*. USENIX Association.

</div>

<div id="ref-Pereira11:HeliosMixnet" class="csl-entry">

Bulens, Philippe, Damien Giry, and Olivier Pereira. 2011. “<span class="nocase">Running Mixnet-Based Elections with Helios</span>.” In *EVT/WOTE’11: Electronic Voting Technology Workshop/Workshop on Trustworthy Elections*. USENIX Association.

</div>

<div id="ref-CCM08b" class="csl-entry">

Clarkson, Michael R., Stephen Chong, and Andrew C. Myers. 2007. “<span class="nocase">Civitas: Toward a Secure Voting System</span>.” 2007-2081. Cornell University.

</div>

<div id="ref-2014-Hawk-and-Aucitas-auction-schemes" class="csl-entry">

McCarthy, Adam, Ben Smyth, and Elizabeth A. Quaglia. 2014. “<span class="nocase">Hawk and Aucitas: e-auction schemes from the Helios and Civitas e-voting schemes</span>.” In *FC’14: 18th International Conference on Financial Cryptography and Data Security*, 8437:51–63. LNCS. Springer.

</div>

<div id="ref-Smyth15:Hawk" class="csl-entry">

Quaglia, Elizabeth A, and Ben Smyth. 2018. “Secret, Verifiable Auctions from Elections.” *Theoretical Computer Science* 730: 44–92.

</div>

<div id="ref-Smyth16:ballotSecrecy" class="csl-entry">

Smyth, Ben. 2018a. “<span class="nocase">Ballot secrecy: Security definition, sufficient conditions, and analysis of Helios</span>.” Cryptology ePrint Archive, Report 2015/942.

</div>

<div id="ref-Smyth18:HeliosMixnetVerifiability" class="csl-entry">

———. 2018b. “<span class="nocase">Verifiability of Helios Mixnet</span>.” In *Voting’18: 3rd Workshop on Advances in Secure Electronic Voting*. LNCS. Springer.

</div>

<div id="ref-Smyth15:ElectionVerifiability" class="csl-entry">

Smyth, Ben, Steven Frink, and Michael R. Clarkson. 2017. “<span class="nocase">Election Verifiability: Cryptographic Definitions and an Analysis of Helios and JCJ</span>.” Cryptology ePrint Archive, Report 2015/233.

</div>

</div>

[^1]: The idea of using candidates to represent more complicated data structures is not new. Indeed, candidates have been used to represent prices in auction schemes constructed from voting systems (McCarthy, Smyth, and Quaglia 2014; Quaglia and Smyth 2018).

[^2]: A variant of the encoding could disregard cells $j,i$ such that $j<i$ to avoid ties being expressed.