In this case we will use Discrete logarithms to create an election where it is not possible to view any of the votes, but so that everyone can compute the result:
A Fair and Open Election |
Outline
Our election processes are often archaic, where we still put a cross on a piece of paper and then wait for it to be manually counted. Then we must compile all the results from different voting stations and again wait for the result to be compiled. We must then hope that the whole infrastructure is fair and honest in the way that the votes are collected and counted.
But why shouldn't each citizen have their vote to be completely anonymous and after the votes have been cast, for every citizen to view the result? The instance the votes are finalised, every citizen could then view the result, without waiting for a government to count and process the votes. It might be possible for us to, to "peek" at the votes currently cast, without actually knowing who had currently voted.
Let's look at an example, where Bob, Alice and Eve want to vote but to keep their votes secret. Once all the votes have been cast, they should then be able to see the result, without actually revealing the voting intents (normally we would have a much larger population, of course, and the larger the population, the greater the anonymity will be):
In order to illustrate the voting process, I have created a simple example to illustrate using this [paper] and which was recently used by researchers at Newcastle University [paper] as part of The Economist Challenge of voting:
The maths involve a bit of understanding of discrete logarithms (please contact me if you want to learn a bit about his). Please also excuse the copy-and-paste graphics, as LinkedIn doesn't implement maths layout. The code that follows, though, is my own and is unique in illustrating a simple example.
Initially, we pick a safe value of g and a prime number p. I have selected g=2 and p=67 (if you want to see how to pick g, watch here). We then define a number of voters, who generate a random value (\(x_i\)). They then broadcast the value of:
\(Public_i = g^{x_i} \mod p \)
It should not be possible to determine \(x_i\) given \(Public_i\). Each voter keeps their \(x_i\) value secret, and will prove to Trent that they know it (using Zero Knowledge Proof - ZPF).
Next all the votes regenerate a set of new keys:
This is the multiplication symbol, where we multiply the values of \(g^{x_i}\) from 1 to i-1 and divide for i+1 to n. Within discrete logarithms, the divide operation is an inverse function. I appreciate that this big of maths look a bit strange so here is the Python code that I created:
# Bill Buchanan Code import random import math import sys import libnum g=2 p=67 nvoters = 5 voter = [int] * nvoters public = [int] * nvoters Y = [int] * nvoters make_votes = [int] * nvoters vote = [int] * nvoters vote[0]=0 vote[1]=0 vote[2]=0 vote[3]=0 vote[4]=0 print("Votes: ",vote[0],vote[1],vote[2],vote[3],vote[4]) print("----") for i in range(0,nvoters): voter[i] = random.randint(1, 30) for i in range(0,nvoters): public[i] = pow(g,voter[i], p) for i in range(0,nvoters): Y[i]=1 for j in range(0,i): Y[i] = (Y[i] * public[j]) % p for j in range(i+1,nvoters): Y[i] = Y[i] * libnum.invmod(public[j],p) % p for i in range(0,nvoters): print("Public value: ",public[i]) for i in range(0,nvoters): print("Y value: ",Y[i]) for i in range(0,nvoters): make_votes[i] = (Y[i]**voter[i])*(g**vote[i]) % p result = make_votes[0] for i in range(1,nvoters): result = (result *make_votes[i]) % p for i in range(0,nvoters): print("Vote ",make_votes[i]) print("---") print("Vote tally: ",math.log(result)//math.log(g))
Once ready, the voters then create:
\( g^{x_i y_i} g^{v_i} \mod p\)
and where \(v_i\) is the vote for voter i. In discrete logs:
\( g^{x_i y_i}\)
is the same as:
\( {g^{{x_i}^{y_i}}} \)
If you look at the code, this is coded as:
make_votes[i] = (Y[i]**voter[i])*(g**vote[i]) % p
Once all the votes are created we then compute:
and which results in:
\(g^{SumOfVotes}\)
We then just take the inverse log, and we can determine the votes:
print "Vote tally: ",math.log(result)/math.log(g)
Here is a test run for all No votes:
Votes: 0 0 0 0 0 ---- Public value: 36 Public value: 19 Public value: 23 Public value: 52 Public value: 64 Y value: 2 Y value: 28 Y value: 42 Y value: 49 Y value: 61 Vote 36 Vote 54 Vote 62 Vote 24 Vote 24 --- Vote tally: 0.0
and then for all "Yes":
Votes: 1 1 1 1 1 ---- Public value: 10 Public value: 8 Public value: 61 Public value: 43 Public value: 38 Y value: 59 Y value: 30 Y value: 34 Y value: 5 Y value: 63 Vote 57 Vote 65 Vote 22 Vote 16 Vote 60 --- Vote tally: 5.0
Presentation
References
- Hao, Feng, Peter YA Ryan, and P. ZieliĆski. "Anonymous voting by two-round public discussion." IET Information Security 4.2 (2010): 62-67. [paper]
- McCorry, Patrick, Siamak F. Shahandashti, and Feng Hao. "A Smart Contract for Boardroom Voting with Maximum Voter Privacy." IACR Cryptology ePrint Archive 2017 (2017): 110. [paper]