# How to create a decentralized secret ballot among a small group of people?

A small (< 100) group wants to implement an election. For that, each participant must vote in one of N candidates. After everyone has voted, they must be able to determine a winner; yet, nobody must be able to determine the vote of someone else. There is no trusted third party. You can assume there is a public list of public keys.

Is there a cryptographically secure way to solve this problem?

• Does the group trust each others public keys? – mat May 11 '17 at 8:26

Ignoring implementation-related security and just focusing on the underlying cryptographic techniques, perhaps the simplest method for such a small election with the number of voters $n < 100$, would be to use a linear secret sharing scheme, e.g. Shamir's. In Shamir's scheme, we may share a secret value $s$ in some large enough finite field $\mathbb F$ among $n$ players by selecting a uniformly random polynomial $f \in \mathbb F[X]$ of degree at most $t$ such that $f(0) = s$, and sending the value of $f(i)$ to player $i$. The parameter $t$ determines how many players are needed to reconstruct a secret from the shares: given $t+1$ players, they may jointly reconstruct $s$ by using Lagrange interpolation on their shares, but at most $t$ players obtain no information about the secret.
Suppose the parties have access to pairwise secure channels, and can be trusted to follow the protocol exactly, and not cheat by for example submitting a faulty vote. Each voter $V_i$ records their vote as a vector $\mathbf x_i = (x_{i1}, \dots, x_{iN}) \in \mathbb F^N$ where $x_{ik} = 1$ if $V_i$ wants to vote for candidate $k$, and $x_{ik}=0$ otherwise. Of course, only one element in $\mathbf x_i$ is allowed to be 1, and the rest should all be 0. $V_i$ then secret-shares their vote with all the other voters (e.g. using packed secret sharing [FY92] if $N$ is small enough, or if need be sharing each coordinate in the vector separately). Let $[\mathbf x_i]_j$ denote the share of voter $V_j$ for the secret vote vector $\mathbf x_i$ of $V_i$.
Every voter $V_j$ now has $n$ shares $[\mathbf x_1]_j, \dots, [\mathbf x_n]_j$. Since Shamir's scheme is linear, the players may add their $n$ shares to obtain a valid share of the total election result $\mathbf x_1 + \dots + \mathbf x_n$. Hence, they may jointly reconstruct this value, and determine the election's winner.
A similar result to this may be obtained using additively homomorphic encryption (which Helios uses), and distributed key generation and threshold encryption. Of course, in this scheme voters can easily cheat without being detected, by for example setting $x_{ik} = 2$ and $x_{ik'} = -1$, and more machinery is needed to make this work in the actively secure case, but I hope it gives a rough idea.