Imagine an Electronic Voting Machine

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 election
Table 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 counted
Table 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.

Conclusion

Did 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...