15
$\begingroup$

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?

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

Electronic voting schemes constitute a big area of cryptographic research. The problem is complicated and multifaceted, and there are still no end-to-end secure schemes that provide desirable properties like verifiability and coercion resistance and that have good usability and performance for a large number of voters. See for example this survey from 2017 for the state-of-the-art. One scheme with implementation that's relatively popular is Helios (website) (Usenix paper, 2008), which foregoes coercion resistance, and instead mostly focuses on auditability in the case of malicious voting machines.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.