class: blueBack ## Evidence-Based Elections and Risk-Limiting Audits ### Philip B. Stark #### Department of Statistics, University of California, Berkeley #### http://www.stat.berkeley.edu/~stark @philipbstark ### .white[University of Melbourne] ### Melbourne, Australia, 17 April 2019 --- .medium[NSW just announced election results.] -- + How do we know whether the reported winners really won? -- + NSW wrote its own software to tally the votes -- - Code is not public -- - Why should voters trust that NSW's code is correct? -- - Even if the code is correct, how can voters know whether that code was used? -- - Even if that code is used, how can voters know whether input data truly reflects votes? -- + Involves optical character recognition from scanned, handwritten text ---
---
--- + The election included votes cast online via iVote, provided by Scytl. -- - Why should voters trust Scytl? ---
---
---
---
--- .medium.red[NSW is "marketing" their Scytl/iVote system to other states.] -- Western Australia has bought in. I understand that state laws currently prevent other Australian states from using iVote. ---
--- .center[
] ---
---
---
---
---
---
---
---
--- https://www.intelligence.senate.gov/sites/default/files/documents/ICA_2017_01.pdf
--- .large.center[Trump: 304 electoral votes] -- .large.center.blue[270 to win] -- .center.large.red[304-270 = 35] -- |State | Margin (votes) | margin (%) | paper? | electoral votes | |---------|-------------|------------|--------|-----------------| | Florida | 112,911 | 1.20% | mixed | 29 | | Michigan | 10,704 | 0.23% | yes | 16 | | Pennsylvania | 44,292 | 0.72% | mostly no | 20 | | Wisconsin | 22,748 | 0.77% | yes | 10 | -- .center.red[Errors in a few dozen precincts in MI and PA could alter outcome] --- + Candidate who challenges results likely to be characterized as "sore loser" - pressure to concede on election night, before large fraction of votes have been counted + No legal basis to call for an audit if the state doesn't have audit law + Hoped to put pressure on Governors, State & Local election officials: petition with >450k signatures --- ## Stein's recount efforts: PA, MI, WI -- ### PA + Not much paper to recount: none in Philadelphia, Pittsburgh + Required affidavits from 3 people who voted _in each precinct_ + Huge bond required + Tried, but judge rejected before it really started ---
---
--- ### WI + Stein had standing to request recount + Recount law allows re-scanning or manual tally - re-scanning is like asking same doctor for 2nd opinion + Stein sued to compel manual tally + Judge agreed manual is preferable, but law says jurisdictions can choose ---
---
---
---
---
---
---
---
---
--- .medium[Georgia, 2018] + Suit against GA SoS Kemp, candidate for Governor in hotly contested race v. Stacey Abrams + Judge Totenberg agreed paper ballots should be used, but was convinced GA could not transition in time + Voting systems and registration system wide open since at least 2016; no action even after vulnerabilities discovered + (massive disenfranchisement by Kemp--de-registering voters, rejecting absentee ballots, etc.) ---
---
---
---
---
---
--- ### Arguments that US elections can't be hacked: .medium[ - Physical security - Not connected to the Internet - Too decentralized - Tested before election day ] --- ### Arguments that US elections can't be hacked: .medium[ .red[ - Physical security + "sleepovers," unattended equipment in warehouses, school gyms, ... + locks use minibar keys + bad/no seal protocols, easily defeated seals + no routine scrutiny of custody logs, 2-person custody rules, ... ] - Not connected to the Internet - Too decentralized - Tested before election day ] --- ### Arguments that US elections can't be hacked: - .red.strikethrough[Physical security] .red[ - Not connected to the Internet + remote desktop software + wifi, bluetooth, cellular modems, ... + removable media used to configure equipment & transport results - Zip drives (only available used) - USB drives. Stuxnet, anyone? + parts from foreign manufacturers, including China; Chinese pop songs in flash ] - Tested before election day - Too decentralized ---
---
---
---
---
---
--- ### Arguments that US elections can't be hacked: - .red.strikethrough[Physical security] - .red.strikethrough[Not connected to the Internet] .red[ - Too decentralized - market concentrated: few vendors/models in use - vendors & EAC have been hacked - demonstration viruses that propagate across voting equipment - "mom & pop" contractors program thousands of machines, no IT security - changing presidential race requires changing votes in only a few counties - many weak links ] - Tested before election day ---
---
---
--- ### Arguments that US elections can't be hacked: - .red.strikethrough[Physical security] - .red.strikethrough[Not connected to the Internet] - .red.strikethrough[Too decentralized] .red[ - Tested before election day - Dieselgate: if a system can tell it is being tested, it can be programmed to misbehave only when it's _not_ being tested. ] ---
--- ## Evidence-Based Elections
.framed.blue.medium[It is not enough for election officials to report a result; they should also present evidence that would convince a reasonable person that the result is correct.] -- .medium[Absent convincing evidence that the reported results are right, there should be a new election.] --- ## Procedure-Based Elections -- .medium[EOs (say they) followed proper procedures, therefore, the public should trust the results.] -- .medium.blue[Relying on following procedures is like surgeon saying "I followed proper procedure, therefore, the operation was a success.] -- .medium.red[Important to look at the patient!] --- ## Evidence-Based Elections: 3 C's .medium[ + Voters .blue[_CREATE_] complete, durable, verified audit trail. ] -- .medium[ + LEO .blue[_CARES FOR_] the audit trail adequately to ensure it remains complete and accuirate. ] -- .medium[ + Verifiable audit .blue[_CHECKS_] reported results against the paper ] ---
--- ## Risk-Limiting Audits .medium[ + Endorsed by NASEM, PCEA, ASA, LWV, CC, VV, ... ] -- .medium[ + Known chance of requiring a full hand count of the votes, if that would show the outcome is wrong. (Full hand count corrects wrong outcomes.) ] -- .medium[ + _Risk limit_: largest chance that a wrong outcome will not be corrected. ] -- .medium[ + Most efficient options: **ballot-polling** and **ballot-level comparison** ] --- .medium[ + 255 state-level pres. races, 1992–2012, 10% risk limit - BPA expected to examine **fewer than 308 ballots** for half. ] -- .medium[ + 2016 presidential election, 5% risk limit - BPA expected to examine **~700k ballots nationally** (\\(<0.5\\)%) ] --- #### Ballot-Polling v. Ballot-Level Comparison, 2 Candidates, 10% Risk Limit | Winner's share | median BPA | 90th %tile BPA | comparison audit | |:---------- | ------: | ------: | -------:| -------:| |70% | 22 | 60 | 8 | |60% | 84 | 244 | 25 | |55% | 332 | 974 | 50 | |53% | 914 | 2,700 | 83 | |52% | 2,051 | 6,053 | 125 | |51% | 8,157 | 24,149 | 250 | |50.5% | 32,547| 96,411 | 500 | --- ## Risk-Limiting Audits .medium[ + ~40 pilot audits in CA, CO, IN, MI, NJ, OH, VA, and DK + CO law in effect; RI 2019; TX passed a law this week; CA has pilot laws ] --  --- ## RLA pseudo-algorithm -- .large[ ``` while ( NOT (full handcount) AND NOT(strong evidence outcome is correct)) { audit more } ``` ] -- .large[ ``` if (full handcount) { handcount result is final } ``` ] -- .medium[Chance RLA won't correct wrong outcome is at most pre-selected **risk limit**. "Wrong" means full handcount would belie it. ] --- .medium[ Magic shop claims coin will land heads 2/3 of the time. ] -- .medium[Can you test whether chance of heads is > 1/2?] -- .blue.medium[HHHHHHHHHH …] -- .red.medium[Is that strong evidence that the coin isn't fair?] -- .medium[What about .blue[THHHHHHTTH …]? ] --- .medium.blue[ + According to shop: - \\(\Pr(\mathrm{H}) = 2/3\\) - \\(\Pr(\mathrm{T}) = 1/3\\) ] -- .medium.red[ + If coin is fair: - \\(\Pr(\mathrm{H}) = 1/2\\) - \\(\Pr(\mathrm{T}) = 1/2\\) ] --- SPRT \\(t = 1\\) -- .medium[After each toss, ] $$ t \leftarrow t \times \frac{\Pr(\mbox{outcome if coin is fair})}{\Pr(\mbox{outcome if shop is right})}$$ -- .medium[ + If toss lands heads, \\(t \leftarrow t \times \frac{1/2}{2/3} = t \times 1/3\\) ] -- .medium[ + If toss lands tails, \\(t \leftarrow t \times \frac{1/2}{1/3} = t \times 3/2\\) ] -- .blue.medium[Theorem (Wald, 1945):] If the coin is fair, the chance that \\(t\\) ever gets below \\(p\\) is at most \\(t\\) --- ### _P_-values .blue[HHHHHHHHHH]: \\(t=(1/3)^{10} = 0.000017 \\) .blue[THHHHHHTTH]: \\(t=(3/2)^3(1/3)^7 = 0.0015 \\) --- ## Coins to ballots .medium[Box model if store is telling the truth:] ``` | 1 | | 0 1 | |________| ``` -- .medium[Box model if coin is fair:] ``` | | | 0 1 | |________| ``` --- .medium[Consider names instead of numbers: + "1" = vote for the reported winner + "0" = vote for the reported loser ] -- .medium[If winner really got 2/3 of the votes:] ``` | winner | | 0 1 | | loser winner | | 0 1 | | winner | | 0 1 | | loser winner | --> | 1 | | winner | | 1 | | loser winner | | 1 | |_________________| |_________________| ``` -- .medium[If outcome was really a tie:] ``` | loser winner | | 0 1 | | loser winner | | 0 1 | | loser winner | --> | 0 1 | | loser winner | | 0 1 | |_________________| |_________________| ``` --- ### More than two candidates, undervotes, overvotes, ... ``` | Alice Chris | | | | Bob Alice | | | | Bob Chris | | | | Donna Elle | | | | blank | | | | invalid blank | |____________________| ``` -- + .medium[test one reported (winner, loser) pair at a time] -- + .medium[condition on showing a vote for one member of the pair] -- + .medium[no multiplicity issue: conjunction, not union] --- ## Requirements .medium[ + paper ballots (25% of US voters don't have) - hand-marked for voters who can - ballot-marking devices for voters who need assistive technology - ballot-marking devices introduce security vulnerabilities + demonstrably trustworthy chain of custody of the ballots + ballot manifest + good, transparent, verifiable source of randomness - 20 public rolls of transluscent 10-sided dice + high-quality, verifiable PRNG - SHA256-based cryptographically secure PRNG, open source $$ X_j = \mathrm{int}(\mathrm{SHA}(\mathrm{seed},j))$$ ] ---