A New Approach to Voting: An Accessible Voter Verifiable Paper Ballot Except where reference is made to the work of others, the work described in this thesis is my own or was done in collaboration with my advisory committee. This thesis does not include proprietary or classi ed information. Jerome McClendon Certi cate of Approval: Christa Slaton Full Professor Political Science Juan E. Gilbert, Chair Full Professor Computer Science and Software Engi- neering Cheryl Seals Associate Professor Computer Science and Software Engi- neering George T. Flowers Dean Graduate School A New Approach to Voting: An Accessible Voter Verifiable Paper Ballot Jerome McClendon A Thesis Submitted to the Graduate Faculty of Auburn University in Partial Ful llment of the Requirements for the Degree of Master of Science Auburn, Alabama December 18, 2009 A New Approach to Voting: An Accessible Voter Verifiable Paper Ballot Jerome McClendon Permission is granted to Auburn University to make copies of this thesis at its discretion, upon the request of individuals or institutions and at their expense. The author reserves all publication rights. Signature of Author Date of Graduation iii Vita Jerome McClendon, son of Herman and Barbara McClendon, was born on June 13, 1984 in Phoenix, Arizona. In 2002, Jerome graduated from Brewbaker Technology Magnet High School in Montgomery, Alabama and the following fall enrolled in and attended Auburn University in Auburn, Alabama. He received a Bachelor of Science degree in Computer Science in May of 2007. That same year Jerome entered the Computer Science Graduate Program at Auburn University. iv Thesis Abstract A New Approach to Voting: An Accessible Voter Verifiable Paper Ballot Jerome McClendon Master of Science, December 18, 2009 (B.S., Auburn University, 2007) 51 Typed Pages Directed by Juan Gilbert The 2000 U.S. Presidential Election brought national attention to electronic voting when an estimated 50,000 ballots were discarded and not counted [12]. The body of research presented in this thesis will describe a method that solves electronic voting issues entitled the Accessible Voter Veri able Paper Ballot(AVVPB), which prints a barcode image containing voters? selections made on an electronic voting system, Prime III. Once done printing, voters scan the barcode and through a multimodal user interface voters can either view their vote selections printed on the ballot or listen to their vote selections as it is read back to them by the computer. The multimodality of AVVPB allows voters with various disabilities, e.g. visual impairments, hearing impairments, physical impairments, etc, to independently verify their ballot. Essentially, everyone can be ensured that their vote will be cast as intended, regardless of their ability or disability. v Acknowledgments First and foremost, I would like to thank Jesus Christ, my Lord and Savior; for all things are possible through Him. Secondly, I would like to thank my parents, my sister and Jamese Yarber who encouraged me to keep pursing my master?s degree. Additional thanks must be given to Dr. Juan Gilbert who has assisted me in time and resources and has served as a mentor to me. I also wish to thank the rest of my thesis committee, Dr. Christa Slaton and Dr. Cheryl Seals, for their reviewing and advising e orts. vi Style manual or journal used Journal of Approximation Theory (together with the style known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (speci cally LATEX) together with the departmental style- le aums.sty. vii Table of Contents List of Figures ix 1 Introduction 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Literature Review 3 2.1 Voting Technology and Voting Systems . . . . . . . . . . . . . . . . . . . . . 3 2.1.1 Punch Card . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1.2 Optical Scan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1.3 Direct Recording Electronics . . . . . . . . . . . . . . . . . . . . . . 5 2.1.4 AutoMark Voter Assist Terminal . . . . . . . . . . . . . . . . . . . . 5 2.1.5 Voter Ver able Paper Audit Trail . . . . . . . . . . . . . . . . . . . . 7 2.1.6 Voter Ver able Video Audit Trail . . . . . . . . . . . . . . . . . . . . 7 2.1.7 Statistical Audit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Problem 10 3.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Background 18 4.1 Prime III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5 Approach 23 5.1 Barcode Ballots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.1.1 Pre-Election . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 5.1.2 Voting Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6 Implementation 34 6.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 6.2 Software Design and Construction . . . . . . . . . . . . . . . . . . . . . . . 35 6.2.1 Access Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 6.2.2 Generation and Scanning of Barcodes . . . . . . . . . . . . . . . . . 36 6.2.3 Tally Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7 Conclusion and Future Work 38 7.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Bibliography 40 viii List of Figures 2.1 Punch Card [23] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Optical Scan [37] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 AutoMark Voter Assist Terminal [13] . . . . . . . . . . . . . . . . . . . . . . 6 2.4 VVPAT Ballot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.5 Figure 1: Statistical Power of a 10% Audit vs. an Audit of 60 Precincts [41] 9 3.1 Butter y Ballot [22] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Hanging Chad [24] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Pregnant Chad [24] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 Pollworker examing punch card ballots [1] . . . . . . . . . . . . . . . . . . . 14 3.5 Minnesota Challenge Ballot [40] . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.6 Minnesota Challenge Ballot [40] . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.1 Prime III Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.2 First Ver cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 Second Ver cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.1 XML Ballot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 Ballot Creation Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.3 Scanning interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.4 \View Winners" output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.5 \View Complete Tally " output . . . . . . . . . . . . . . . . . . . . . . . . . 32 6.1 Access Frame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 ix Chapter 1 Introduction 1.1 Introduction From the very rst election to present day, elections have always been determined by the tallying of votes. The only things that have changed over time are the methods and technology which we use to carry out the tally. In the early days, elections were determined through the tallying of votes by hand and therefore were susceptible to human error [35] [23]. To protect voters from election fraud and to reduce the rate of human error; new methods and machines were introduced such as mechanical levers, punch cards, optical scan, and computers [23]. These machines attempted to eliminate human error by decreasing the role of humans during an election, but in doing so, new errors were introduced relating to the operation of the various machines. The objective of this research is to reduce the errors previously mentioned by creating an approach that is usable, accessible, accurate, and also increases voters? con dence in the election process. In this paper we introduce the Accessible Voter Veri able Paper Ballot(AVVPB) that works in conjunction with the electronic voting system, (Prime III), to achieve this goal. AVVPB does so by printing and scanning ballots containing barcodes made of voters selections, that will ultimately be used for the tallying of votes at the end of the election. The rest of this thesis is organized as follows: Chapter 2 contains a literature survey, which will give a brief description of voting technology, actual voting systems, audit trail methods and introduction into barcodes. In Chapter 3 the research problem is de ned. Chapter 4 gives a brief synopsis of the Prime III electronic voting system. Chapter 5 introduces AVVPB and gives a detailed description of how AVVPB is carried out from 1 start to nish. The implementation of the current hardware and software used in AVVPB is discussed in Chapter 6. Future works and conclusions are presented in Chapter 7 2 Chapter 2 Literature Review 2.1 Voting Technology and Voting Systems In 1892 Jacob H. Myers introduced the lever voting machine, the rst voting machine to be used in an election [23]. Since then punch cards, optical scan machines, and computers have all been used in elections. In the following sections, brief overviews are given of the recent and current trends in voting technology. 2.1.1 Punch Card The use of pre-scored punch cards to tally votes dates back to the 1960?s with the creation of the Votomatic voting system (Figure 2.1) [35]. During the voting process, voters use a stylus to punch holes next to their selections on the ballot, removing a square or round piece of paper known as a chad from that position [23] [24]. When a voter is done making their selections, their ballot is inserted into the voting system and is then processed with the punch card reader where the presnce of a hole represents a vote [23]. 3 Figure 2.1: Punch Card [23] 2.1.2 Optical Scan Optical scan ballots, also known as mark sense ballots, were rst used in California in 1962 (Figure 2.2) [23]. In a 2006 report done by Election Data Services it was found that 40.79 % of registered voters in the United States were using optical scan voting systems [9]. When using optical scan, voters make their selections using a marking device to darken an oval next to the items of their choice. Once done, they can take their ballot to a scanner which records their vote using \dark mark logic", which recognizes the darkest mark for a given set [7]. One bene t of opitical scan is that voters do not have to learn a new voting system, but simply use pen and paper to make their selections. With 40.79 % of people 4 now voting on optical scan, the technology?s imperfections have become visible and have led to the research of Direct Recording Electronics(DRE?s). Figure 2.2: Optical Scan [37] 2.1.3 Direct Recording Electronics DRE?s, developed in the late 19th century, use touch screens that list the names of the candidates and issues [23]. The voter votes by touching the name or issue on the screen for whom s/he wishes to cast a vote for. Touch screens developed in the 1970?s had been widely used in many domains from banking applications to public information displays. It was not until 2006 did they see wide use in elections, with 66.6 million registered voters now using DRE?s [9]. As of the 2006 elections, jurisdictions with 63% of the nation?s registered voters changed their voting system, marking the largest shift in voting equipment in history [9]. The switch made by many jurisdictions from Punchcards to DRE?s, can be credited to the Help America Vote Act(HAVA), a federal law passed in October of 2002 [20]. HAVA required all states to replace Punch Card systems with new voting systems that allowed for an accurate and e cient election and also allowed people with disabilities the opportunity to cast their ballot secretly and independently for the rst time [44]. 2.1.4 AutoMark Voter Assist Terminal The AutoMARK Voter Assist Terminal, considered more of a hybrid voting system, falls into the category of both DRE and optical scan. The hardware consists of touch 5 Figure 2.3: AutoMark Voter Assist Terminal [13] screens found in DRE?s, as well as, scanners found in optical scan (Figure 2.3) [10]. Voters make their selections by touching their choice on the screen. After the voter has nished making their selections and casting their ballot, their ballot is then printed with computer generated marks, placed directly alongside their selections [10]. This is for voters with motor disabilities who are completely unable to make marks themselves, or for those who are unable to make marks that are readable by the optical scanner. Once the ballot has been printed the voter then takes the printed ballot and places it in the ballot scanner where it scans the vote. Before placing the ballot in the scanner for tallying, the voter has the option to verify their ballot by placing it in the scanner that is attached to the AutoMark [10]. This will read back the voter?s selections, by only reading the choices that were marked, verifying their ballot was printed as intended. After the voter has made his/her selections and has placed their ballot into the scanner, the Automark will check to see if there were any under votes present. If under votes were present the Automark will notify the voter through a visual message that a race has been left blank [6]. Using the DRE and optical scanner together allows voters with physical impairments or language barriers to verify their printed ballots before being counted. 6 Figure 2.4: VVPAT Ballot 2.1.5 Voter Ver able Paper Audit Trail Voter-Ver able Paper Audit Trail (VVPAT) is an independent veri cation system used for the manual recount of votes casted on DRE?s [17]. Votes are printed onto a receipt roll, similar to the one as seen in Figure 2.4, where they are used by poll workers to hand count the votes recorded. VVPAT gives the voter the ability to verify that his/her ballot was accurately cast and tallied and also leaves a paper trail for post-election audits or recounts [17]. 2.1.6 Voter Ver able Video Audit Trail Printing paper ballots is not the only method of independent veri cation. Voter Veri- able Video Audit Trail replaces the paper receipts used in VVPAT with video surveillance of the machine. Video recorders attached to each machine record all screen interactions done by the voter but do not record the individual voting [7]. In the case of a recount or audit the election administrator takes each video recorder and assigns a single poll worker the duty of navigating through video. Using a remote control the poll worker advances from ballot to ballot while the remaining poll workers records the results on their tally sheet. 7 2.1.7 Statistical Audit Dopp and Stenger, the authors of the paper \The Election Integrity Audit", state that the most accurate voting systems, include both an electronic count of votes and a manual paper count of votes done by an outside source and should not include vendors, poll workers or election administrators [8]. The purpose of the manual paper count is to verify that the results produced by the voting systems were accurate, but counting every ballot during a manual count can become expensive [33]. A statistical audit of the election cuts down these expenses by only requiring a random amount of ballots to be counted by the outside team, thus, guaranteeing a certain level of \con dence" that the voting process was not corrupted by machine malfunctions or election fraud [19] [33] [41]. This number of random ballots needed is known as the sample size. When calculating the sample size there are many di erent methods that can be taken. In Connecticut a law was passed requiring random audits of only 10 % of voting precincts [41]. However the authors of \Percentage-based vs. SAFE Vote Tabulation Auditing: A Graphic Comparison", argue that percentage-based audits like the ones done in Connecticut are either ine cient (too large) or ine ective (too small). Instead the authors recommend the SAFE auditing method that is based on the size of the sample not the fraction of precincts sampled. Figure 2.5 shows a comparision of the two aforementioned methods. As stated earlier there are many di erent statistical auditing methods, with each one possessing the capibility of verifying election results along with detecting errors that are caused by the problems discussed in the following chapter. 8 Figure 2.5: Figure 1: Statistical Power of a 10% Audit vs. an Audit of 60 Precincts [41] 9 Chapter 3 Problem 3.1 Problem Statement As mentioned previously, HAVA was passed in 2002 with the goal of correcting the problems of voting machines, speci cally requiring voting machines to have an error rate of 1 in 10,000,000 (0.00001%) or less, in order to be used in a federal election [20]. Despite this requirement, many current voting systems do not meet these standards for accuracy, with poor usability being the reason for a large number of these errors [32]. Dr Juan E. Gilbert, a professor in the Computer Science and Software Engineering Department at Auburn University has been quoted as saying, \If you could build perfect security into an electronic voting system, but it lacked usability, then it would be useless, usability matters" [16]. Having a product that has been deemed usable means the product has been designed in a matter that is easy and e ective to use that no problems exist when capturing the intent of the user [11]. These same guidelines also need to apply to voting systems; therefore when tallying ballots during and after the election, less confusion will exist regarding the voter?s intent. But this was not the case in the 2000 elections in Florida , when punch card systems were the cause of both a miscount of votes and thousands of ballots being thrown out [12]. One of the well known cases took place in Palm Beach County Florida, where poor ballot design led to voters making incorrect selections or the wrong amount of selections. The ballot was designed such that candidates? names were placed on both sides of the ballot and in the middle. The ballot included holes that the voter was to punch in order to make selections [39]. Refer to the ballot in Figure 3.1. If a voter wanted to vote for the Democratic candidate he or she punched the third hole. In actuality it was found that some voters punched the second hole, thinking that the second 10 hole represented the Democratic candidate. This occured when voters read the ballot from top to bottom instead of left to right. There were also 120,000 ballots found containing over votes, where voters selected more than one candidate for an o ce [3]. This was caused by voters punching the hole placed directly next to their selection along with punching the hole directly under their selection. In doing so, voters were under the assumption that they were selecting their candidate?s running mate [39]. When these ballots were tallied it could not be determined who the voter actually wanted to vote for hence, the voters? intent was lost. 11 Figure 3.1: Butter y Ballot [22] The hanging and pregnant chad incident that occured in Florida was another case in which voter intent was lost [25]. Problems occured when voters did not completely punch out their selection leaving what is called a hanging chad, as seen in Figure 3.2 [23]. Ballots could also be found containing chads that were not displaced at all by the stylus, leaving 12 an indentation instead [23]. These were known as pregnant chads as seen in Figure 3.3. Both pregnant and hanging chads were not tallied by the Votoamic punch card system leading to the hand count of several votes. As seen in Figure 3.4, it was hard for election administrators to distinguish a selection from a non selection [25]. Figure 3.2: Hanging Chad [24] Figure 3.3: Pregnant Chad [24] 13 Figure 3.4: Pollworker examing punch card ballots [1] In a recent election in Minnesota, several ballots were challenged due to the o cials confusion over voter?s intent. Figure 3.5 shows a challenge ballot where the voter marked one side of the ballot and the ink bled through the other side. In an attempt to correct the mistake the voter scribbled over the marks, leaving election o cals confused as to the intent of the voter [40]. Figure 3.5: Minnesota Challenge Ballot [40] From the Minnesota election it was illustrated that when given a pen or pencil it was possible for anything to show up on the ballot. Figure 3.6 shows a ballot where a voter 14 wrote their explanation for selecting a candidate. There were several other ballots found similar to this one where voters underlined and scratched out candidate names causing a massive debate in the state of Minnesota [40]. Using a marking device such as a pen or pencil does not limit the possibility of the voter, but instead opens up more possibilites. As a result making it harder for election o cials to determine intent of the voters. Figure 3.6: Minnesota Challenge Ballot [40] Unlike optical scanners or punch card systems, when using DRE?s, voters do not have to use any type of marking or punching device; thereby reducing the amount of problems encountered when analyzing the voter?s intent. This also poses a concern, since there is no paper to mark or punch, there is also no paper trail in some DRE?s, leaving voters feeling less con dent in the election results. Advocates of DRE?s would state that even when a paper trail is present election results can be incorrect. In a study done at Rice University on VVPAT, in which participants had to count two races from a spool of 120 complete VVPAT ballots, only 57.5% of the participants? counts were the correct election results [17]. This still does not dispute the fact that machines that use paper create a more con dent feeling amongst voters during the voting process. In a study performed in 2007 by the Secretary of State of Georgia, it was found that voter?s con dence increased from 86.9% to 89.4%, when voters used DRE?s that printed their ballot(VVPAT) compared to 15 DRE?s that didn?t print their ballot [15]. An increase in voters? con dence could be due to their familiarity with paper over that of computers. With paper based voting systems, malfunctions and malicious attacks are easier to recognize because more voters and poll workers are used to dealing with paper and feel comfortable when using it [21]. With DREs, users are dealing with computers and the notion that a special skill set is required. A skill that neither the average voter nor poll worker possess. Hence they are left feeling that if there was a malfunction or breach within the system it would go undetected by many, a ecting the integrity of the election. The authors of the book, Voting Technology discuss voter?s con dence in paper based systems, arguing that nearly every voter has interacted with paper through their lives, therefore increasing their con dence in voting systems that use paper. They also mention that marks on paper, unlike DRE?s, are tangible and visible throughout the election process [21]. Voters having con dence in their vote being counted as cast is important, in order to sustain a democratic society. Yet do all voters have a chance to receive this same level of con dence? Due to various disabilities, many members of the voting community do not share the same privileges. According to the American Association of People with Disabilities, in the United States there are 37.5 million disabled people who are eligible to vote [34]. There are only a few voting systems that allow voters with disabilities to verify their ballot was cast correctly. VVPAT systems provide a printed receipt of the voter selections, but do not provide an accessible method of veri cation for those who are visually impaired or illiterate. The AutoMark voting system is one voting system that does provide a veri cation method for those who are visually impaired or illiterate by giving them the option to scan and then listen to their selections read back to them. However, with the scanner being built into the voting machine the principle of independence has been violated. The machine that veri es or tallies the ballots should remain seperate and independent from the machine the voter used to cast their ballot [30]. Currently, there is no one voting technology that meets the required accuracy of HAVA, while remaining both easy and e ective to use, along with infusing con dence to all voters 16 that their ballot was cast as intended. In order to incorporate all of these missing com- ponents into one voting system, the Accessible Voter Veri able Paper Ballot(AVVPB) was created. The hypothesis is that AVVPB will achieve what previous voting systems could not through a multimodal user interface that makes it accessible and a barcode scanner that simpli es and increases the accuracy of vote tallying. 17 Chapter 4 Background 4.1 Prime III Prime III is a third generation voting system that delivers the necessary accuracy, e ciency, and user satisfaction to the voter; regardless of their ability [7]. All of this is accomplished through its interactive system that involves the use of multimodality. For humans the natural process of conveying and receiving information usually involves the use of multiple channels simultaneously. When a person points to someone and refers to them by name, the simultaneous use of both voice and pointing helps one person to convey the directions while helping another person to receive the directions. Multimodal systems try to duplicate this type of interaction by incorporating multiple human communication channels; Prime III accomplishes multimodality through the use of touch and voice. The actual voting process begins when a poll worker enters an access code to start a Prime III system. After entering the code, the poll worker then escorts a voter to that system and presents him/her with a headset that he or she can choose to wear. While in the booth, the voter must navigate and make selections using either touch, voice, or both. If the user chooses to touch, s/he will use a simple interaction style, where the voter can simply touch the button to make a selection. Referring to gure 4.1, notice the candidates are displayed in a single column showing only one race at a time. In the paper entitled, \Prime III: One Machine, One Vote for Everyone" the single column designed was compared to the displaying of multiple o ces per screen [7]. The authors in the paper stated that displaying multiple o ces per screeen was simply copying the paper ballot to the screen, which has proven to be a bad design decision and more confusing to the voter than displaying one race at a time . 18 Figure 4.1: Prime III Interface For those with disabilities such as visual impairments and lack of motor skills, making a selection using a touch screen can prove to be di cult if not impossible. In these cases the Automatic Speech Detector (ASD) is used for navigation and making selections in Prime III. When a voter uses the ASD, they are prompted with the same ballot options via the headset that are being displayed on the touch screen. If the choices are Democrat, Republican, and Libertarian Party, Prime III will prompt the user with something similar to \to vote for the democratic party, say vote to vote for the Republican Party say vote to vote for the libertarian party say vote ". The voter will simply say \vote" after the option that they would like to select has been read by Prime III [7]. The ASD can also be used as a sip and pu device allowing the voter to blow into the microphone to make a selection. This allows voters who are unable to use the touchsreen or say the word \vote" to make selections. 19 After the voter is done making selections s/he must complete a two step veri cation process beginning with a screen where the voter must choose to make changes or select \Continue" (Figure 4.2). If the voter chooses to make changes s/he selects the race or amendment he/she wish to change. Whereas if the voter chooses to cast his/her nal ballot, s/he is asked to select the \Continue" option on the rst screen seen in Figure 4.2 and then select the \Cast Your ballot" option seen in Figure 4.3 . For voters using headphones the nal ballot can also be heard. It should be noted that throughout the process the voter is allowed to make changes. Because no marking or punching device is used, when voters make mistakes they don?t have to worry about getting another ballot or trying to correct their mistake causing further damage. The second veri cation step requires the voter to cast his/her nal ballot, thereby causing Prime III to encrypt the voter?s selection and write the contents to a PDF le that is saved in the election folder. Along with the voter?s selection being saved and encrypted, imposter les are created and saved in imposter folders. Imposter les are ballots that have been created by randomly selecting candidates and amendments from the xml ballot le and storing them randomly throughout the system in imposter folders. Imposter folders are regular folders which are created before the election using a program that generates hundreds of folders with unique folder names. Within these folders are hundreds of other folder each with a unique name. In Prime III, there only exist one folder that contains all the real ballots and this folder is known as the election folder. 20 Figure 4.2: First Ver cation Once all ballots have been cast and the precinct has been closed, the election admin- istrator and poll workers will gather the results from each machine. The votes are tallied using Prime III rst by locating the election folder where the actual ballot les are stored and then decrypting the contents of each PDF in that folder. After the contents of the PDF have been decrypted and turned back into a readable ballot, Prime III uses that information to tally the votes. If there is need for a manual recount or audit the video recorders attached to each system can be used to replay the sequence of interactions on that system capturing voters? intent [7]. In the next chapter a detailed explanation is given of the approach that was used to intergrate Prime III with the entire AVVPB solution. 21 Figure 4.3: Second Ver cation 22 Chapter 5 Approach 5.1 Barcode Ballots Advocates of electronic voting have made strong arguments in favor of the use of optical scan voting systems, stating that optical scan systems provide a complete set of features as well as outperforming their counterparts in many categories [28]. But as we have seen in Minnesota, optical scan systems have their faults which led to this research of barcodes placed onto printed ballots. A barcode can be de ned as data that has been coded into a digital format using a series of black lines and white spaces that can be deciphered by a barcode scanner [43]. Barcodes and optical scan are similar in that they both rely on optical technology to read coded data but barcodes have been proven to be more accurate [14] [38]. In elections, optical scan systems have been tested to have error rates varying from 0.10% to 11.43% or more, while barcodes outperform the HAVA error rate requirements even in the worst case scenario [38]. In a study done at Ohio University, researchers constructed an automated system capable of scanning multiple barcodes in order to test the accuracy of PDF417 and DataMatrix coding technique used in the creation of barcodes [14]. Each barcode in the study contained between 50 and 350 characters, and in all, there were a total of 94 million characters decoded with no errors being found. In their next step, researchers calculated the expected accuracy when using PDF417 and DataMatrix by creating con dence intervals based on a con dence level of 95%. The results showed that both PDF417 and DataMatrix had a worst-case scenario error rate of 1 in 10.5 million (0.0000095%) and a best-case scenario error rate of 1 in 612 million (0.00000016%) [14]. 23 In a paper written by the National Institute of Standards and Technology(NIST) sub- committee on voting technology, it was concluded that the scanning of barcodes during an election exceeds a hand count of ballots in both accuracy and in speed and could be used in an election if voters were able to verify their ballot [27]. Accessible Voter Veri able Paper Ballot(AVVPB) attempts to keep the accuracy and speed of barcode ballots while adding a veri cation method. 5.1.1 Pre-Election Before the election starts, a ballot must be created by the election adminstrator to be used by Prime III and AVVPB during and after the election. Extensible Markup Lan- guage(XML), a computer language designed to give computer devolpers the ability to create custom documents through a series of elements known as tags, is used when creating the ballot le [5]. As an example, Figure 5.1 shows the rst tag in the xml le is labeled \Ballot" and under that tag follows the \Race" tag. The \Race" tag contains the \O ce Name" tag, where the title of the race is entered. After the \O ce Name" tag there is the \Candidate" tag which contains one or more \Candidate Name" tags depending on the number of peo- ple running for that o ce. The \id" tag is a unique two digit number that each candidate and ammendment has for tallying purposes. The nal tag, the \Party Name" tag , lists the political party the candidate belongs to. To create the ballot the user does not have to know XML or even understand it; as they can simply use the Ballot Creation Tool to produce the ballot. 24 President Optimus Prime 01 Transformers Bugs Bunny 02 Looney Tunes Mickey Mouse 03 Disney Vice President BumbleBee 07 Transformers Elmer Fudd 08 Looney Tunes Donald Duck 09 Disney Figure 5.1: XML Ballot 25 The Ballot Creation Tool was designed to make the creation of ballots simple and fast by allowing information to be entered using a graphical user interface (Figure 5.2). The person using the tool enters the o ce, candidate, and party name into the text boxes. After the user has completed a race, they can advance to the next race by pressing the \Next Race" button. Once the user has completed all races, they save the ballot by pressing the \Save Ballot" button. Figure 5.2: Ballot Creation Tool After the ballot has been created the election administrator then runs the Election Key program which prompts the election administrator to enter an access code, this is a series of numbers that will be encrypted and written to a text le labeled \password". For security purposes, the election administrator will be the only person with this access code and will use it to start the actual scanning of barcodes . Without the administrator entering the access code no ballots can be scanned, making it di cult for anyone to stu the ballot 26 anytime during the election. After the access code has been created, each barcode scanner used in the election must be tested before actual use during the election. For each barcode scanner in the precinct there is a stack of fake ballots that were printed out by election o cials before the election. The fake ballots have already been correctly tallied by an outside source, with each stack having a di erent outcome. The election administrator is the only person present during the test who knows the results from each stack. Each stack of ballots is assigned to a random barcode scanner during the test and the poll worker scans each ballot in the stack assigned to that scanner. When all the stacks have been scanned the election administrator goes to each scanner and veri es whether the results match what has been previously recorded. 5.1.2 Voting Process Once the election process has begun the election administrator enters their access code to start each scanning station and the poll workers begin to escort the voters to voting booths where they will use Prime III to cast their ballot. While in the booth voters have the option of either touching their selection on the screen or using speech to make the appropriate selection. The selection process in Prime III was designed to limit the amount of actions a voter has when making a selection, therefore leaving the voter with little room to make an error. This is not true in paper-based systems. As stated earlier in this paper there have been punch card ballots found with too many punched holes or holes that have been partially punched. When using optical scan systems, voters have scratched out names and have even written sentences on ballots [39] [25] [40]. In Prime III all ballots follow a standard format because of the limited amount of actions a voter can perform when making a selection. Since the ballots follow a standard format, there should be no uncertainty when examining voters? intent. After the voter has nished making their selections and has veri ed their nal ballot on screen twice, a paper ballot is printed. Figure 5.1.2 shows a sample ballot that has been printed with candidate names and amendments. The only candidates? names that appear 27 on the ballot are those that have been voted for. All the amendments? and propositions? titles appear on the printed ballot but only a vote \for" or \against" will appear with it, depending on the voters? selection. Printing only the selections made by voters simpli es the manual recount of ballots, thereby making it easier to count votes by hand. 28 As discussed earlier, each candidate and amendment has his or her own unique two- digit identi cation number. The identi cation number of each candidate and amendment that was selected by the voter is printed beside each selection and is combined to form one long number that is encoded into the barcode, as well as, printed below the barcode (Figure 5.1.2). Once the ballot has been printed, the voter takes the ballot from the printer and walks to a scanning station where they will scan their ballot. If the voter is visually impaired or has a disability that hinders them from handling the ballot, a poll worker will 29 assist the voter in getting the ballot out of the printer using a privacy sleeve to cover the voter?s selections. The scanning station, an independent system seperate from Prime III, consists of a touch screen monitor, a barcode scanner, and a computer that is locked in a cabinet to ensure security. When a voter arrives s/he places the ballot face down on the scanning bed and presses the \Scan Ballot" button to begin scanning his/her ballot. If the voter is visually impaired, the voter will give his/her ballot to a poll worker at one of the scanning stations to scan. The poll worker never ips over the voter?s ballot and voter privacy is never compromised. Before the barcode has been scanned for tallying, the voter can verify their ballot is correct by pressing the "Review Ballot" button and listen as their votes are read back to them through a set of headphones. This allows voters who are visually impaired to verify their ballot. Figure 5.3 shows the scanning station interface. Figure 5.3: Scanning interface 30 If there were no problems with the voter?s ballot then the barcode on top of the ballot is written to a text le and the voter?s ballot is placed in a bin before leaving the polling station. Once all of the ballots have been scanned and the polling station has been closed the election administrator can begin to tally the votes on each machine. Before tallying the votes the election adminstrator must rst enter the correct tally code which will display the tally window. In the tally window the election administrator is presented with the \View Winners" and \View Complete Tally" buttons. The \View Winners" button displays the winners from each race with the amount of votes received. To see the number of votes that each candidate and amendment received, the election administrator would press the \View Complete Tally" button. Figure 5.4 shows the output when the \View Winners" button was pressed and Figure 5.5 shows output when \View Complete Tally " button was pressed. Figure 5.4: \View Winners" output 31 Figure 5.5: \View Complete Tally " output After the election administrator has gathered the results from each race, a statistical audit must take place to verify those results. An outside source gathers all the ballots at the end of the election and pulls from the stack the number of random ballots needed to guarantee that the electronic results were correct. The number of random ballots needed is calculated using a sampling formula. If the results from the statistical audit do not match the results from the scanning stations then a manual recount of all ballots must take place. Through a combination of di erent technologies and methods, AVVPB simpli es the voting process for both voters and poll workers making it easy, e ective, and accurate. The Prime III interface makes the selection of items less di cult, and the ballots created by Prime III follow a standard format. Therefore eliminating the confusion poll workers might face when trying to determine the voter?s intent. The barcodes provide the accuracy required by a voting machine, as well as providing all voters with an opportunity to verify their ballot. A statistical audit held at the end of the election validates the integrity of 32 the election proving that there was no malfunction within the system or malicious attacks against the system. 33 Chapter 6 Implementation 6.1 Hardware The installation and maintenanence cost of current voting systems have many election o cials debating over whether they are the solution that they were said to be originally [36]. The state of Maryland has paid at least $97.5 million to Diebold on statewide machines with $44 million of the total amount going towards operation and maintenance costs alone [45]. The hardware and software platforms used in the current implementation of AVVPB was designed with price and installation in mind. During an actual election, several Prime III voting systems and barcode scanning sta- tions would be used in the precinct. For this reasons it is important to keep the hardware price relatively low. The current version of Prime III consists of: Touch screen monitors Headphones with an attached microphone Printer Printing paper Laptop computer The hardware for the barcode station consists of primarily the same items as Prime III; only replacing the printer used in Prime III with a barcode scanner and no longer requiring the voter to use a microphone attached to the headset. The current hardware implementation of AVVPB has some advantages over other vot- ing systems in that: 34 None of the equipment is specialized Installing the equipment should be a quick and easy No constant attention is required Since the equipment is not specialized, it does not have to be purchased from one particular company. This in essence causes the price of the machine to decrease because now the equipment can be purchased from anywhere. Competition created amongst the manufactures to buy their product will also cause the prices to decrease. The setup and operation of the machines on election day should prove to be no di cult task. In a mock election held on Prime III by the National Counsel of Independent Living, people with various disabilities were able to setup and operate the equipment for Prime III after being trained only a few minutes before the actual election. 6.2 Software Design and Construction A design goal when creating AVVPB was not to limit the implementation to one oper- ating system, but to have the ability to run on multiple operating systems without changing the code. Through the Java programming language, we were able to create software that was independent of any platform. AVVPB has been successfully tested on both Linux and Windows operating systems. In conjunction with the Java programming language we used the Java Free Text to Speech library to create the voice prompts and the Barbeque library to generate the barcode. Both of these libraries are also platform independent. 6.2.1 Access Frame As discussed in Chapter 5 the access code is to provide an extra layer of security to the scanning station by requesting a password to start the scanner and to view the election results. Figure 6.1 shows a screenshot of the access frame interface where the access code is entered. The election administrator enters his/her password by pressing the numeric buttons and then pressing enter. Once s/he has pressed a number, it is compared to a 35 number saved in the \password.txt" le. The number in the password le was created during the pre election setup using the Election Key program. The Election Key program prompts the election administrator to enter a numeric password that will be encrypted using Advanced Encryption Standards(AES) encryption and written to \password.txt". The Access Frame decrypts the password and compares it to what was just entered. If the number was incorrect, it then compares the number to the tally code for viewing election results and the exit code for exiting the program. If the number entered did not match the last two, then the Access Frame noti es the user that the password was incorrect. Figure 6.1: Access Frame 6.2.2 Generation and Scanning of Barcodes Once the voter has nished casting their ballot Prime III goes through each selection on the ballot and takes the two digit unique identi cation number of each selection and combines them into one long number. This long number is then sent to a function that uses 36 the Barbeque library to create a barcode image. After the barcode image has been created, it is then printed along with the human readable form of the voters? selection. When a voter scans the printed barcode, the number below the barcode which repre- sents the voters? selections, is written to the \vote.txt" le. If a voter chooses to review their ballot by pressing \review your ballot" button, the number just scanned is parsed using a parsing function. The parsing function works by taking that number and looping through it two digits at a time. Using the current two digits, the function looks for the item on the xml ballot that has the same two digit identi cation number. If it is a match, that item is read back to them using the Free Text to Speech library. 6.2.3 Tally Frame If election results need to be reviewed, entering the tally access code will display the tally frame. This is where o cials can view the winning selection of each race or they can see the complete tally sheet. When the tally frame is rst loaded the software loops through each barcode number stored in the \vote.txt" le and using the same parsing function discussed in the above section, matches each two digit number in that barcode with an item on the xml ballot. Once a match has been made, the number of votes received for that item is then incremented and stored. When the \View Winners" button has been pressed, the software goes through each race and displays the item with the greatest amount of votes along with the number of votes the item received. If the \View Complete Tally" button is pressed, the software goes through each race displaying all items under that race along with the number of votes each item received. The aforementioned hardware and software combined has made great strides in ensuring con dence in the results of an election by creating a solution that is usable, secure, easy to install and maintain, as well as cost e cent. 37 Chapter 7 Conclusion and Future Work 7.1 Conclusion The systems in which we use to vote have constantly evolved over time [35]. Each new voting system has been deemed the nal solution until an improvement over its predecessors was created. The creation of DRE?s were to provide the accessibility that paper based systems were missing the development of optical scan systems were to provide the paper trail that DRE?s were missing. Eventually DRE?s and optical scan problems were revealed, leaving not one system that included the accuracy, usability, accessibility, or veri cation needed in the voting process. The goal of this research is to add the previous properties to the current voting process through a combination of methods and technologies. AVVPB accomplishes this through the generation of barcodes ballots that encode the voter selection within the barcode. Barcodes were chosen, because when tested, they had an expected worst case error rate of 1 in 10.5 million when given a con dence level of 95%, which is far better than optical scan [14] [38]. If a voter wanted to verify their ballot, the AVVPB multimodal approach with the help of the barcode gives every voter, regardless of their ability, an opportunity to verify their ballot; either through voice or sight. If there is any uncertainty pertaining to the scanning and tallying of the barcode ballots; the statistical audit held at the end of voting process removes any speculation of tampering or malfunctions during the voting process. Each one of these components of AVVPB instills con dence within the voter by creating a voting process that is accurate, usable, accessible, and veri able. 38 7.2 Future Work The research in this paper focuses on the printing of generated barcode ballots that could be scanned and used for tallying during an election. Even though AVVPB has been implemented, there are still minor improvements to be made. The Ballot Creation Tool should be redesigned, making it intuitive, so the poll worker does not have to learn a new tool. The software used in future versions of AVVPB needs to run o of a DVD, making it harder for someone to circumvent the system. Implementing the aforementioned improvments will likely result in a veri able voting process that will become the base for future evolvement of voting technology. 39 Bibliography [1] Aplf. (2007). [Online].http://www.airplanelanding eld.org/images/random/hanging chad orida.jpg [2] Bellis M. BarCodes. [Online].http://inventors.about.com/library/inventors/blbar code.htm [3] Bra , S.(2003).The Florida Overvote: Tragic Mistake, or Katharine Harris with Tweez- ers? http://archive.democrats.com/view.cfm?id=1730 [4] California Secretary of State.(2009).California Secretary of State Debra Bowens Report to the Election Assistance Commission Concerning Errors and De ciencies in Diebold/Premier GEMS Version 1.18.19 . [Online].http://www.eac.gov/program- areas/research-resources-and-reports/copy of docs/sos-humboldt-report-to-eac-03-02- 09.pdf-1/attachment download/ le [5] Carey P.(2004). New Perspectives XML. [6] Champaign County Clerk.(2009). November 2006 Undervote Analysis http://blog.champaigncountyclerk.com/2009/07/01/november 2006 undervote analysis/ [7] Cross, E.V., Rogers, G., McClendon, J., Mitchell, W., Rouse, K., Gupta, P., et al. (2007). Prime III: One Machine, One Vote for Everyone. VoComp 2007, Portland, OR. [Online].http://www.vocomp.org/papers/primeIII.pdf [8] Dopp K and Stenger F. (2006).The Election Integrity Au- dit. [Online].http://electionmathematics.org/ucvAnalysis/US/paper- audits/ElectionIntegrityAudit.pdf [9] Election Data Services Inc. (2006). 2006 Voting Equipment Study. [On- line].http://www.edssurvey.com/images/File/ve2006 nrpt.pdf [10] ES&S.Product and Services ES&S Automark. [On- line].http://www.essvote.com/HTML/products/automark.html [11] Preece J., Rogers Y. and Sharp H. (2003). Interaction Design: Beyond Human Com- puter Interaction [12] Everett, S. (2007) . The Usability of Electronic Voting Machines and How Votes Can Be Changed Without Detection. [13] FlatPanels. (2009) [Online].http://www. atpanels.com/photo gallery/photo gallery.htm [14] Fritz J. and Russ D. DATAMATRIX AND PDF417 DATA INTEGRITY TEST. [On- line].http://www.ent.ohiou.edu/autoid/datam417.pdf 40 [15] Georgia O ce of the Secretary of State Elections Division . (2007) . VOTER VERI- FIED PAPER AUDIT TRAIL Pilot Project Summary Report [16] Gilbert, Juan. Personal interview. 2007. [17] Goggin, S. N. and Byrne, M. D. (2007). An Examination of the Auditability of Voter Veri ed Paper Audit Trail (VVPAT) Ballots. Proceedings of the 2007 USENIX/ACCURATE Electronic Voting Technology Workshop. Boston, MA. [On- line].http://www.usenix.org/events/evt07/tech/full papers/goggin/goggin.pdf [18] Greenson T. (2008).Software glitch yields inaccurate election results. [On- line].www.votersunite.org/info/AccuracyIgnored.asp [19] Hall J. (2007). A Quick Primer on The Mathematics of Post-Election Audit Con dence. [Online].http://www.josephhall.org/eamath/eamath.pdf [20] HAVA (HELP AMERICA VOTE ACT). (2002). PUBLIC LAW 107-252, 107TH CONGRESS, UNITED STATES. [21] Hernson P. , Niemi R. , Hammer M. , Bederson B. , Conrad R. and Traugott M. (2008).Voting Technology The Not-So-Simple Act of Casting a Ballot. Washington , D.C. : Brookings Institution Press [22] IndyStar. (2003). [Online].http://www2.indystar.com/library/fact les/gov/politics/election2000/img/prezrace/butter y large.jpg [23] Jones, D. (2002). A Brief Illustrated History of Voting. [On- line].http://www.cs.uiowa.edu/~jones/voting/pictures/ [24] Jones, D. Chad From waste product to headline. [On- line].http://www.cs.uiowa.edu/~jones/cards/chad.html [25] Levine S.(2008).Hanging Chads: As the Florida Recount Implodes, the Supreme Court Decides Bush v. Gore . [Online].http://www.usnews.com/articles/news/politics/2008/01/17/the-legacy- of-hanging-chads.html [26] National Institute of Standards and Technology. General Information. [On- line].http://www.nist.gov/public a airs/general2.htm [27] National Institute of Standards and Technology .(2006).VVPR Issues and STS Rec- ommendations for the TGDC [28] N.C. Coalation for Ver ed Voting,. Introduction to the Argument FOR the Optical Scan/Ballot Marking Solution . [Online].http://www.ncvoter.net/opticalscan.html [29] Optical scan voting systems [Online].http://en.wikipedia.org/wiki/Optical scan voting system [30] Runyan N. (2007) . Improving Access to Voting [31] Premiere Elections Solutions. [Online].http://www.premierelections.com/ 41 [32] Quesenbery W. (2001).Voting and Usability: Lessons from the 2000 Presidential Elec- tion. [Online].http://www.wqusability.com/articles/voting-nv.html [33] Rivest R. (2006). On Estimating the Size of a Statis- tical Audit. [Online].http://people.csail.mit.edu/rivest/Rivest- OnEstimatingTheSizeOfAStatisticalAudit.pdf [34] Schorow S. (2006) . Selker honored for aiding voting for disabled. [On- line].http://web.mit.edu/newso ce/2006/voting.html [35] Selker, T. (2004). Fixing the Vote. [36] Sinnottm R. ,Selker T. , Lewis B , et al.Evaluation of Voting Machine, Peripherals and Software [37] State of Michigan. (2004). http://www.michigan.gov/images/markscan lg 40050 7.jpg [38] Theisen E. (2008).Federal Vote-Counting Accuracy Mandate Is Ignored. [On- line].www.votersunite.org/info/AccuracyIgnored.asp [39] The Butter y Ballot: Anatomy of a Disaster. [On- line].http://www.asktog.com/columns/042Butter yBallot.html [40] Tibbetts T. and Mullis S.(2008).Challenged ballots: You be the judge. [On- line].http://minnesota.publicradio.org/features/2008/11/19 challenged ballots/ [41] (2007). Voter Veri ed Voting .Percentage-based vs. SAFE Vote Tabulation Auditing: A Graphic Comparison. [Online].http://www.veri edvoting.org/downloads/SAFE- Auditing-Nov-2-Final4.pdf [42] Washington Secretary of State.(1998).REPORT OF THE SECRETARY OF STATE ON THE EXAMINATION AND EVALUATION OF MODIFICA- TIONS TO AN OPTICAL SCAN ELECTRONIC VOTE TALLYING SYSTEM. [Online].http://www.secstate.wa.gov/documentvault/GlobalElectionSystemsnowDieboldOSGEMSAccuvote1998- 1065.pdf [43] What is a Bar Code? [Online].http://www.dataid.com/whatisbarcode.htm [44] Zetter K.(2004). E-Voting Fans: The Disabled. [On- line].http://www.wired.com/politics/security/news/2004/10/65206 [45] Zetter K. (2008). The Cost of E-Voting [Online].http://blog.wired.com/27bstroke6/2008/04/the- cost-of-e-v.html 42