ContentsList of FiguresAcknowledgementsIntroductionElections: a unique security problemVoting machines in use todayObstacles to improving voting systemsPost-election investigationsRandom auditsLogging subsystemsMotivating election incidentsCuyahoga County, Ohio 2004Sarasota County, Florida 2006Humboldt County, California 2008ContributionsTransparency in random selection for auditsReplayable audit logs for DREsEfficient User-Guided Ballot Image VerificationThe Role of Dice in Election AuditsIntroductionBackgroundCaliforniaSample SelectionRequirementsPossible random sourcesCreating the sampleGeneral dice schemeAnalysisRelated WorkContributionsConclusionReplayable Voting Machine Audit LogsIntroductionProblem StatementOur ApproachDesignSimplicityIsolationCrafting a replayable audit logStoring the logs anonymouslyVote-buying and coercionImplementationIsolationThe logging subsystemCompressionHistory independent data structureAuthentication and integrity of the logReplay MechanismEvaluationSetupPerformance measurementsPracticality and costDiscussion of goalsRelated WorkConclusionEfficient User-Guided Ballot Image VerificationOptical scan systemsProblem statementSuperimposing ballot imagesMin-images and max-imagesUsing superimposed ballot images for verificationOverlay imagesVerifying elections using overlay imagesGrouping ballots into verifiable setsUser interface to verify ballot groupsDealing with anomaliesEvaluationDatasetImage analysisEvaluating verification efficiencyObservationsDiscussionTrust in ballot imagesApplicationsLimitationsAlternate overlay algorithmFuture work and open problemsRelated workConclusionConclusionBibliographyEnabling More Meaningful Post-Election InvestigationsbyArel Lee CorderoA dissertation submitted in partial satisfactionof the requirements for the degree ofDoctor of PhilosophyinElectrical Engineeing and Computer Sciencesin theGRADUATE DIVISIONof theUNIVERSITY OF CALIFORNIA, BERKELEYCommittee in charge:Professor David Wagner, ChairProfessor Jitendra MalikProfessor Deirdre MulliganFall 2010Enabling More Meaningful Post-Election InvestigationsCopyrightc 2010byArel Lee CorderoAbstractEnabling More Meaningful Post-Election InvestigationsbyArel Lee CorderoDoctor of Philosophy in Electrical Engineeing and Computer SciencesUniversity of California, BerkeleyProfessor David Wagner, ChairPost-election audits and investigations can produce more transparent, trustworthy, and se-cure elections. However, such investigations are limited in cases by inadequate tools andmethods, an absence of meaningful evidence, and high costs. In this dissertation, I addressthese concerns in the following three lines of research. First, I describe my research onverifiable and transparent random sample selection for post-election audits. I investigatehow counties have typically approached random sample selection, and I analyze the impli-cations and limitations of those approaches. I propose a sampling method that has sincefound use in counties across the country. Second, I describe a novel approach for loggingevents in direct recording electronic (DRE) voting systems. My approach gives investiga-tors more meaningful evidence about the behavior of DREs on election day. In particular, Ipropose to record interactions between the voter and the voting machine such that they canbe replayed by investigators while preserving the anonymity of the voter. Last, I describea novel process for efficiently verifying elections that use optical scan voting systems. Myprocess uses image superposition to let an investigator visualize the content of many ballotimages simultaneously while allowing individual treatment of anomalous ballots. I evaluatethis process and demonstrate an order of magnitude improvement in the time it takes to in-spect ballot images individually. This approach will let investigators more cost-effectivelyverify that all ballots have been accurately counted as intended by the voters.1For my parents, Carmen and Rogeliowho ingrained in me the sense of equality that democracy aspires toiContentsContents iiList of Figures vAcknowledgements xi1 Introduction 11.1 Elections: a unique security problem . . . . . . . . . . . . . . . . . . . . . 11.2 Voting machines in use today . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.1 Obstacles to improving voting systems . . . . . . . . . . . . . . . 51.3 Post-election investigations . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3.1 Random audits . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.3.2 Logging subsystems . . . . . . . . . . . . . . . . . . . . . . . . . 81.4 Motivating election incidents . . . . . . . . . . . . . . . . . . . . . . . . . 91.4.1 Cuyahoga County, Ohio 2004 . . . . . . . . . . . . . . . . . . . . 91.4.2 Sarasota County, Florida 2006 . . . . . . . . . . . . . . . . . . . . 101.4.3 Humboldt County, California 2008 . . . . . . . . . . . . . . . . . . 101.5 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5.1 Transparency in random selection for audits . . . . . . . . . . . . . 111.5.2 Replayable audit logs for DREs . . . . . . . . . . . . . . . . . . . 121.5.3 Efficient User-Guided Ballot Image Verification . . . . . . . . . . . 132 The Role of Dice in Election Audits 152.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.1 California . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17ii2.3 Sample Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3.1 Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.4 Possible random sources . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.5 Creating the sample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.5.1 General dice scheme . . . . . . . . . . . . . . . . . . . . . . . . . 232.5.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.7 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.8 Conclusion . . . . . . . . . . . . …