Voting machines used in Florida during the previous presidential elections were
not trusted by many electors. How can we
verify the results of a voting machine
and keep each elector's choice
private?
Our voting machine creates three different tables containing different kinds of information. Two tables will remain private and stored by a representant of the judiciary authority. One table will be made public after the election is completed.
How does our imaginary electronic voting machine work? Let's try it on the following election with candidates Bush and Kerry. We will limit ourselves to a very small village with only three inhabitants named Mike, Sarah and Zoe.
Mike votes for Bush. Sarah and Zoe for Kerry. The voting machine produces the following three tables.
Example 1 - simple electionTable 1: Mike Sarah Zoe
Table 2: 2 1 3
Table 3: Kerry Bush Kerry
When Mike votes, his name is added somewhere randomly in
Table 1 - in first position in our example. His vote is added somewhere randomly in
Table 3. In the above case it is in the second position of
table 3. The first position of
table 2 represents Mike's position of his vote in
table 3 - so that position is 2. The machine tells Mike his position is 2. Mike remembers this value and he can verify his vote later by himself when
table 3 is made public.
Sarah votes for Kerry. Here Sarah is in position two in
table 1. Her vote is stored in position 1 of
table 3. So the position two of
table 2 contains 1. She remembers the value 1 to verify her vote.
Zoe votes for Kerry. She is in position three in
table 1. Her vote is stored in position 3 of
table 3. Thus position three of
table 2 contains 3. She remembers the value 3.
After the election
tables 1 and 2 are kept secret under the justice authority.
Table 3 is made public. Everyone can verify how many votes occurred and how many votes each candidate received. Here three people voted, two for Kerry and one for Bush. But we don't know who voted for who so Mike, Sarah and Zoe's vote is kept private.
Mike examines
table 3 and can verify that position 2 is for Bush. That's his vote so he is satisfied. Sarah and Zoe can also verify their vote.
If Bush, Kerry, Mike, Zoe or Sarah contest the results, the justice authority can verify the integrity of the
tables 1, 2 and 3. They can verify each position in
table 3 corresponds to a unique elector. I.e. Mike, Zoe and Sarah voted only once and their votes are counted separately.
Example 2 - simple election with votes from unregistered users
Table 1: Mike Sarah Zoe
Table 2: 2 1 3
Table 3: Kerry Bush Kerry Bush Bush
The justice department verifies nobody voted for Bush in positions 4 and 5 of
table 3. The machine made an error or someone tampered the results. The election is invalid.
Example 3 - simple election with votes not countedTable 1: Mike Sarah Zoe
Table 2: 2 1 1
Table 3: Kerry Bush
The justice department detects position 2 and 3 of
table 2 refer to the same position in
table 3. Zoe's vote is erroneously counted with Sarah's one. So it looks like Kerry and Bush have the same number of votes when looking at
table 3 but that is incorrect. Election is invalid. Machine made a mistake or someone tampered the results.
ConclusionDid you thought creating an electronic voting machine was easy? There are plenty of additional details to take into account. Note
activity 1 from the book Fun Science With Your Computer describes how pseudo random numbers can be created. They would be used to randomly fill up the tables. We would not want Mike to guess Sarah's vote just because she voted right after him and the machine would simply store the votes in the same order...
