It is important to note that electronic voting is not a solution to problems of type demonstrated in Florida during the 2000 election. The ability to produce a clear ballot will not magically be granted to all who construct them online. The same layout issues will continue and will actually be compounded because a video monitor is less clear than a printed page at the same size of type. Some of the problems - stray marks, hanging chad, and over voting - will largely be eliminated, but selecting the wrong candidate will still count as vote for that person.
The most widely used form of secret ballot is the Australian ballot and is thus the touchstone for any electronic system. The Australian ballot's underlying assumption is all participants are out to defraud the system; from this, two key operating principals can be derived:
Building an electronic Australian ballot presents a number of difficulties, the largest being dependence on the external auditing features, because it is difficult to view electrons as they zip about computer systems. The rest of this paper will be devoted to building electronic voting systems of increasing complexity and scale-ability until we have created a system that could be used for an entire voting district. One problem that any electronic-voting system has is vulnerability to a rogue programmer. The discussion of this problem is left to the end of the paper.
Breaking this into modules we have:
The main weakness of this system is the ability of voters to smuggle votes in their sleeves. The sound of a large number of stones would indicate stuffing of the ballot box, the valid votes could not be sorted from the invalid. By changing from stones to pottery balls it is possible to mark each ballot and prevent the voter from seeing this mark. Thus it is impossible to determine how a single voter voted, but still possible to tell valid from invalid votes. This is accomplished by baking a serial number into the center of each ball at the time of manufacture; as the votes are counted, the balls are smashed. Any balls containing a serial number not issued to the polling station are invalid.
Conversion of this into an electronic voting system serves to illustrate some of the problems.
A first pass of the system would be:
This simplistic system however, fails to recognize the number of roles the pottery balls play. First, they provide a powerful check on the number of ballots cast. The duplication of this function is accomplished by adding a ballot store to the system. The ballot store is where ballots reside waiting for the voter. Only unused ballots remain in it after the polls are closed.
The system components are now:
The ballot store works in conjunction with the ballot box: When a voter enters the booth, a ballot is withdrawn from the store; when the vote is cast the ballot is deposited in the ballot box. To prevent the ballot box from being stuffed each ballot must have a unique serial number. However, the voter can never be allowed to learn the serial number because then it would be possible prove how a specific voter voted.
The revised process for voting is: A voter enters the booth and activates the front end. The ballot box requests a ballot from the ballot store. Upon receiving the ballot, the box removes the serial number from the ballot. The ballot store removes the serial number from the list of available ballots. The ballot box then passes the anonomyzed ballot to the front end. The voter is now offered the ballot and voting is possible. The voters select the way they wish to cast their ballot and then request that the ballot be deposited. The ballot box stores the ballot for latter counting. It is important to note that there should be no counting of the ballots until after the polls have closed.
The next role that the pottery balls serve is to prevent one person from casting multiple votes. This is accomplished by issuing a limited number of ballots and keeping only the moment of voting private. The voter's hand is hidden from view when the ball is dropped while the rest of the voter is visible. Thus the voters cannot start pulling extra ballots out of their tunics' without a number of people noticing. To provide this protection with an electronic ballot, the poll workers issue the voter a card with a unique number encoded. When the voter enters the voting booth, the card is deposited in a slot that checks for a valid number. If the number is valid the front end is activated and presents the ballot. The card is retained by the voting booth.
The system as it now stands:
Write-in candidates
Write-in candidates are handled by adding an option on the front end that presents the voter with the opportunity to type in the name of any person they wish. The front end makes no effort to check spelling, guard against common joke names such as Donald Duck, or even single letters. A notation is made on the ballot that the race has a write-in, the name typed is attached to the ballot and the ballot deposited in the ballot box.
When the ballots are counted all write-ins are printed out for hand counting along with the serial number of the ballot. The entire ballot should not be printed but the ballot must be query-able because it may be necessary to check and see if that candidate appears elsewhere in the ballot and has been voted for by the same participant.
Opening and closing a polling station
Before introducing any additional complexity, this is a good point to discuss the opening and closing procedures that must be followed to make the system functional. The opening and closing procedures have two equally vital functions. First, auditing the system to ensure that everything is accounted for and in the correct place, the ballot box is empty, the store has the correct number of ballots, and so on. The second function is the task that kept Dark Age kings, such as Offa of Mercia, continuously on the move. If you have seen the king, you know he exists; if you have seen the empty ballot box as the polls open, you know the box was not stuffed before the vote. However, if the king has not been by in a couple of years does he really exist? If no one ever sees that the ballot box is actual empty at the start of the polls, is it empty? Does the canvass really take place? Are those our votes? This is fodder for theorizing about conspiracy to disenfranchise. Additionally, having the public around to observe the opening of the polls and able to examine any documentation produced as the polls are opened works well in the paranoid, trust-only-yourself that underpins the Australian Ballot.
With the twin goals mentioned above, first let me present an opening and closing procedure for the jars and clay balls. The public is welcome to view these events. The obvious auditing functions are augmented by the official trappings of the proceedings to lend legitimacy, much as a doctor is expected to appear in a white lab coat with a stethoscope draped like a flea collar about their neck.
Opening
The same goals are displayed in the closing of the polls; where again multible officials should be involved at each step.
Closing and counting
When the polls close, the same ballot-counting procedure is run again. Each ballot box now reports the votes cast. The stores all report the number of ballots remaining, and the front ends report the number of votes that have passed through the system. If these numbers do not match, a closer examination is needed.
Two things are crucial to note: First, the same programs are run at the opening of the polls and at the closing. Second, no matter how many times the polls are opened and closed nothing changes in the counts because the programs are only reporting tools and not initialization tools.
There are two additional issues that must be addressed at this time: first, the problem of systems failure; and second, ensuring that the ballot deposited in the ballot box is an accurately represents the voters' markings. Both problems can be solved with minor changes to the ballot box and the addition of void-ballot tracking.
The void store holds ballots that have met one of three fates: voter void, system void, and challenge ballots. A voter-voided ballot is one where the voter has intentionally destroyed the ballot. These will not be counted. A system-void ballot is one where the system detected a flaw and presented the voter a new ballot. A challenge ballot is one where there is some question about the legitimacy of the voter. To accommodate these three conditions, the void ballot store has three chambers, one for each type of void and one for challenge ballots.
The next change is to ensure that the voting operation is atomic [Lampson1979]. An atomic transaction is one that either completes correctly recording all information or no information is stored. Returning to the clay balls: when the balls are dropped into the flagon, they either reach the bottom or an event rarely seen outside the sub-atomic world has taken place.
By dividing the ballot box into two chambers separated by a one-way trap door and altering the behavior this is feature is duplicated. The outer chamber is a holding space for incomplete ballots, the inner is reserved for completed ballots. The behavior of the ballot box is altered as follows: First, when a voter enters the booth and requests a ballot by putting their card into the machine the number of the card will now be transmitted to the ballot box. The ballot box will pair this number with the serial number of the ballot provided to the voter holding the combination in the outer chamber. Second, the act of voting will now be a two-stage process: when the voter selects "vote", the ballot is deposited in the outer holding area. The voter will then be asked to confirm the vote. If confirm is selected, the ballot will be dropped through the trap door into the inner chamber. After voting is finished, one step in closing the polls is to tell the ballot box to move all ballots from the outer chamber to the inner chamber because these are partial ballots that cannot be completed (voting is done), but they contain some partial information.
Thus the system now looks like:
The act of getting the confirmation of the vote appears to violate the principal of not being able to see marked ballots that have been deposited while the polls are open. This difficulty is resolved by using a one-way function. These are functions that are inexpensive to run forward but very difficult to unravel. For a given input these functions will always produce the identical output. When the ballot box request confirmation, it does not send back a plain copy but rather drops the ballot through a one way function (DES for example). The booth drops a copy of the ballot through the same function and compares its encrypted version with the copy from the ballot box. If the two match, it offers the user the opportunity to confirm the vote. If the two do not match it just retransmits the ballot and the confirmation process starts all over.
This also slightly changes the opening and closing procedure because now the void-ballot store must also be shown to be empty in the beginning and both chambers of the ballot box must be shown empty as well.
When the polls are closed, the following equations should hold true:
ballot box + voter void = voters
voters + system void = original number of ballots
ballot box + void + remaining ballots = original ballots
Note: all serial numbers of the original ballots should appear in exactly one of these spots: ballot store, ballot box, void store.
There are two ways to expand the above system in order to meet the needs of a multi-booth polling station. The first would be to drag a set of the stand-alone machines described above into the polling station; this would work but not provide any enhancement of the current voting methods. The second option is to modify the stand-alone arrangement such that the resources are shared. This is the direction that I will proceed in.
For this example all of the machines are assumed to be in the same building, and thus the network amongst them has no outside connections. The security is provided not by hiding the network away in the walls but rather draping by it about in full public view so that anyone tampering with the cabling must do so in full view of everybody.
The first advantage of networking the machines together is redundancy of modules. To take advantage of this, we will change the modules so they no longer look to a resource on the local machine for services. For example, when voters enter the voting booth and deposit their IDs, thus requesting a ballot, the front end broadcasts a request for a ballot on the network. The first machine to respond acts as the ballot box for that voter. The ballot box then goes on the net and requests a ballot from the first ballot store that responds. By allowing the front end and ballot box to search for the resources they need, the likelihood of a full ballot box or empty ballot store closing a voting booth is greatly reduced.
The second advantage is redundancy of hardware. Computing equipment suitable for shuffling about to polling stations is subject to the dreaded whine and grind of bearings going in a hard drive or, worse, the gentle metallic plinking of a read "/" write head plowing a furrow in a hard-drive and then breaking free to join the data as a pile of twisted metal at the bottom of the case.
Only two pieces of equipment are fatal if they fail before the final count: the ballot box and the void-ballot store. If a voter front end stops working, votes, have to wait a bit longer but no information is lost. If a ballot store fails, then the vote will not be halted because the other stores on the network are the backup, and the information can be reconstructed from the starting information, the ballot boxes, and the void-ballot store. However, the ballot box and the void-ballot store contain information that may only be recovered after the polls are closed, so they must have a dynamic continuous duplication of information.
The nature of the information stored within the ballot boxes and the void-ballot store precludes any other system looking at it, much less storing it, so each of these modules must be altered to provide their own backup.
The actual modifications are remarkably simple. When a front end contacts a ballot box requesting a ballot, the master ballot box contacts a second and third ballot box and requests that for the next transaction these boxes provide redundant storage by acting as passive slaves. The two slave boxes each read all information sent to the master ballot box as if the information was its own but are silent otherwise. When voting is complete, the relationship is broken. The same method works for the void-ballot store. When the ballots are reunited, the actual votes of all ballots should agree. If they do not the discrepancy needs to be explained. This duplication of ballots points up the need for changes in voting law to implement all electronic voting. This topic is disscussed in a section at the end of this paper.
When the votes are counted, the ballots must be reunited; because the serial numbers were stored, this task does not present a problem. However, the ability to track the life of a ballot is now impaired, so the voting process must be changed.
In the original scheme, where the voting booth was a monolithic structure, if a ballot serial number appeared in the ballot box, then it must have originated in the attached store. When the modules are placed on the network, it is impossible to know which front end worked with the ballot. Thus, the progress of one ballot through the system cannot be tracked.
This problem is fairly to rectify. Each front end is assigned a unique ID that is retained as part of the ballot after it has been deposited in the ballot box. The number on the voter ID card cannot be used because this would tie the ballot to a particular voter.
When the voter enters the voting booth, the front end passes the along its ID to the ballot box when it requests a ballot, and the serial number stored in the ballot box takes the form front end ID:serial number. If a number of ballots deposited in a particular ballot box are found to be different from their counterparts in the slave store, then the route of the ballots needs to be retraced. First the serial number is recovered and then the front end ID. At this point the complete path from ballot store to front end to ballot box can be reconstructed. This should make is possible to rule out ballots that make no sense because the equipment represented by the IDs were not all in the same precinct.
The voting process:
When the polls are closed and the votes are to be counted, another computer must be attached to the network to perform the amalgamation that yields the totals. When this information is gathered, care must be taken to ensure that none of the information about which bits of equipment touched the ballots is lost.
The steps of this program are listed below.
To accomplish this, a bank of phone lines is installed in the central area, each connecting to a single ballot box. This bank is represented as a single number to the outside world but the ballot box connected when calling is determined by a call distribution system. The setup is very similar to the systems used by catalog operations with 800 numbers, where any number of calls are handled simultaneously but all the customers called the same number. Each front end has a modem and a phone line. When a voter enters the booth, the front end connects to a random ballot box when the front end dials the central office. After that the transaction proceeds as described above.
The advantages of this system are
Any precinct with the voter load to require a number of voting booths can take advantage of the Internet as it now stands to report results electronically back to the central office in addition to printing them in the precinct. When IPv6 replaces IPv4 (the current protocol of the Internet), a precinct can be joined to the central office over the Internet with a few changes.
The IPv6 version of the Internet protocol will contain three crucial additional features for Internet voting that will allow the voting software to be assured of network connectivity without the use of proprietary technology. The first feature is the ability to tie disjoint networks together so they appear local with tunneling [Conta , rfc2473]. This is not an addition to any of the machines directly concerned with the vote but rather an addition to the routers. The Internet connection will appear the same to the machines concerned with the vote no matter how connections are dropped and reestablished. The second two features, security encapsulation [Kent, rfc2406] and authentication [Kent, rfc2402], together allow the networking software to assure the voting software that the machine on the far end is the one that it claims to be and also protect the connection from eavesdroppers. Even with these additional features however,provisions should still be made for each polling station to be able to continue without connections to the Internet, just as there are provisions inplace now for polling stations that burn down mid vote or suffer other disastrous events.
Satellite voting stations
Most satellite voting stations are small operations with limited access to telecommunications facilities. By using a cell phone to provided access to the connectivity however, they can take advantage of the Internet. The satellite voting station would consist only of the front end and a stack of voter cards. The process from the voter's point of view is the same; however, when the voter enters the booth and a ballot is requested, the voting booth dials in to the central office where the rest of the system is located. The chance that a given satellite station is not functional is acceptable because the voter will have another chance on the official voting day. The ballot boxes, void-ballot store, and ballot store that are used for pre-election satellite voting must not be used on polling day to collect additional votes because they have already collected votes and thus cannot be demonstrated empty at the start of polling. After the polls have closed on polling day, these stores are reconnected to the network and there votes added to the tally.
Jones, D., 2000.
Some Comments on the California Internet Voting Task Force Report of January 2000.
Lampson B. W. and Sturgis, 1979.
Crash recovery in a distributed data storage system. Unpublished technical report, Xerox Palo Alto Research Center,
June, 1979
Kent S. And Atkinson R. 1998
IP Authentication Header RFC 2402 RFC 2402 November 1998
Kent S. And Atkinson R. 1998
IP Encapsulation Security Payload RFC 2406 RFC 2406 November 1998
Deering S. and Hinden R. 1998
Internet Protocol Version 6 (IPv6) RFC 2460 RFC 2460 December 1998
Conta A. and Deering S. 1998
Generic Packet Tunneling in IPv6 RFC 2473 RFC 2473 December 1998
This page was last modified on .