An electronic voting system works as follows: before voting, a voter must first communicate with a registration authority, who provides the voter with a token. This token is used to vote: it is given to the party in charge of tabulation.

At the end, the tabulation states the results and gives a proof.

Goals:

1. Correctness:

• Only authorized parties can vote, i.e. registered voters

• No voter votes more than once

• No voter can replace votes

• The party in charge of tabulation cannot change the outcome

2. Verifiability: universal or private

3. User anonymity

4. Receipt-freeness

We shall show how to build such a system using basic cryptographic primitives (in particular, blind signatures, cryptographic counters and mix nets).

Method 1: Using blind signatures (Chaum, Okamoto-Fujisaki-Ohta): We assume that communication is anonymous and secure (e.g. it is done through SSL and via FreedomNet or an internet cafe).

• The registration authority publishes its public key $PK$.

• The voter picks a random number that becomes their ID, and appends this to the end of every candidate’s name (e.g. "Bush" || ID, "Gore" || ID) in order to construct a token for each cnadidate.

• The voter sends their personal information (whatever is required for authentication) along with blinded versions of the tokens. They also submit a zero-knowledge proof that the tokens have been correctly constructed, i.e. the ID’s are the same, and each candidate appears exactly once (this can be done by cut-and-choose for example).

• The registration authority blind signs all the voter’s messages after verifying that they have been correctly constructed.

• The voter unblinds all the signatures. To vote, the voter submits one of the tokens along with the corresponding registration authority’s signature to the tabulation authority.

Unfortunately, receipts are needed in this scheme.

Method 2: Cryptographic counters

Definition: A $B$-cryptographic counter consists of three algorithms

• Gen: generates $(PK,SK,S_0) \in \{0,1\}^*$. $S_0$ is the initial state of the encrypted counter.

• Decrypt: $Dec(S,SK)$ outputs one of $0,...,B$, and $Dec(S_0, SK) = 0$.

• Increment: $Inc(S)$ satisfies $Dec(Inc(S)) = Dec(S) + 1$ ($PK, SK$ have been omitted for clarity.)

Definition: A $B$-counter is $(t,\epsilon)$-secure if for all $t$-time algorithms $A$,

$Pr[A(PK,S)=Dec(S,SK)| (PK,SK,S_0)\leftarrow Gen, i\leftarrow\{0,...,B\}, S\leftarrow Inc^i (S_0) ] \le \epsilon$

Note that we must have $\epsilon \gt 1/B$.

Example: Additively homomorphic encryption: [Paillier '97]: $E(m) = g^m h^N (\mod N^2)$ for $h \leftarrow \mathbb{Z}^*_{N^2}$

• Gen: choose $h \leftarrow \mathbb{Z}^*_{N^2}$, output $PK = N=pq, SK=(p,q), S_0 = h^N (\mod N^2)$

• Inc: choose $h_0 \leftarrow \mathbb{Z}^*_{N}$, output $S' = S g h_0^N (\mod N^2)$

• Dec: The idea is to put $S$ into $\mathbb{Z}_N$ so we can take its discrete log. Recall $S = g^x h^N \mod N^2$ and we wish to recover $x$. This can be done by noticing

$\frac{(S^{\phi(N)} -1)/N}{(g^{\phi(N)} - 1)/N)} = x \mod N$

Note $\mathbb{Z}_{N^2}^* = \mathbb{Z}_N \times \mathbb{Z}_{\phi(N)}$ and we can represent one of these subgroups by $\{a N + 1 | a = 0 ,..., N-1 \}$. Discrete log is easy since $(a N + 1)^x = a x N + 1 (\mod N^2)$.

The security of the scheme relies on the $N$th residuosity assumption, i.e. that the distribution $\{x|x\leftarrow\mathbb{Z}^*_{N^2}\}$ is $(t,\epsilon)$-indistinguishable from $\{x^N|x\leftarrow\mathbb{Z}^*_{N^2}\}$

We can increment this counter by $k$ in time $O(\lg k)$.

Example [Ostrovski-Katz]: this scheme is based on the quadratic residuosity assumption, i.e. assuming that the distribution $\{x|x\leftarrow\mathbb{Z}^*_{N}, (\frac{x}{N}) = 1\}$ is $(t,\epsilon)$-indistinguishable from $\{x^2|x\leftarrow\mathbb{Z}^*_{N}, (\frac{x}{N}) = 1 \}$.

In fact, this is more general than a counter: it is a Linear Feedback Shift Register. In other words: it implements a $k$-bit register, such that given a pivot set $P \subseteq \{1,...,k\}$, every iteration it will XOR all the bits in the pivot set and perform a left shift, inserting the result of the XOR into the rightmost position.

• Gen: output $PK = N = pq, SK = (p,q)$, $S_0 = [r_1^2, ...,r_{k-1}^2,r_k^2 x] (= 0...01)$ where $r_i \leftarrow \mathbb{Z}_N^*$, $x\in \mathbb{Z}^N^*$ is nonquadratic residue.

• $Inc(S = [A_1,...,A_k])$: output $[A_2 r_2^2, ..., A_k r_k^2, (\prod_{i\in P} A_i ) r_1^2 ]$, where $r_i \leftarrow \mathbb{Z}^*_N$.

• $Decrypt(SK=(p,q), S=[A_1,...,A_k])$: using $p,q$ test if $A_i$ is a quadratic residue to give a bitstring $[b_1,...,b_k] \in \{0,1\}^k$

To use this as a counter, one can choose $P$ carefully so that it will have a cycle length of $B = 2^{k-1}$.

Counters for voting: the tabulation authority runs the Gen algorithm of a cryptographic counter, then passes the state to the first voter. The first voter either increments it or randomizes it (so actually this scheme requires counters that can be randomized too), and gives a ZK proof that this has been done, before passing the state to the next voter. After all voters have had a chance to increment it or randomize it, the state is passed back to the tabulation authority who decrypts it and provides a proof that this has been done correctly.

This scheme is quite inflexible

Method 3: Mix nets

In this scheme, each user encrypts their vote (using the public key of a decryption authority) and gives it to a mixer. The mixer then outputs a permutation of the encrypted votes, along with a proof that it has been mixed correctly (but without revealing what the permutation was). The decryption authority then decrypts all the votes to tabulate the results.

For extra security, several mixers can be used, i.e. the first mixer passes its output to a second mixer, who passes its output to a third mixer and so on.

Using a Neff mix, the proof requires about $8n$ exponentiations, where $n$ is the number of voters.