Abstract
Risk-limiting audits (RLAs) guarantee a high probability of correcting incorrect reported electoral outcomes before the outcomes are certified. The most efficient are ballot-level comparison audits (BLCAs), which compare the voting system’s interpretation of randomly selected individual ballot cards (cast-vote records, CVRs) from a trustworthy paper trail to a human interpretation of the same cards. BLCAs have logistical and privacy hurdles: Individual randomly selected cards must be retrieved for manual inspection; the voting system must export CVRs; and the CVRs must be linked to the corresponding physical cards, to compare the two. In practice, such links have been made by keeping cards in the order in which they are scanned or by printing serial numbers on cards as they are scanned. Both methods may compromise voter privacy. Cards selected for audit have been retrieved by manually counting into stacks or by looking for cards with particular serial numbers. The methods are time-consuming; the first is also error-prone. Connecting CVRs to cards using a unique pseudo-random number (“cryptographic nonce”) printed on each card after the voter last sees it could reduce privacy risks, but retrieving the card imprinted with a particular random number may be harder than counting into a stack or finding the card with a given serial number. And what if the system does not in fact print a unique number on each ballot or does not accurately report the numbers it printed? This paper presents a method for conducting BLCAs that maintains the risk limit even if the system does not print a genuine nonce on each ballot or misreports the identifiers it used. The method also allows untrusted technology to be used to retrieve the cards selected for audit—automation that may reduce audit workload even if cards are imprinted with serial numbers rather than putative nonces. The method limits the risk rigorously, even if the imprinting or retrieval technology misbehaves. If the imprinting and retrieval systems behave properly, this protection does not increase the number of cards the RLA has to inspect to confirm or correct the outcome.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
- 3.
See https://csrc.nist.gov/glossary/term/nonce, last visited 4 July 2022).
- 4.
The DVSOrder vulnerability of some Dominion systems, published in October 2022, illustrates this problem. See https://dvsorder.org/ (last visited 27 January 2023).
- 5.
However, it does not require checking the list against the system’s reported list of IDs: suppose that the ID on a card does not match any ID in the list of CVRs. Treating the card as if its CVR were as unfavorable as possible to every outcome (an “evil zombie” in the terminology of [3, 16]), e.g., as if it showed a valid vote for every loser in a plurality contest, ensures that the audit will not stop sooner than it would have stopped if the list of IDs had been accurate.
References
Appel, A., DeMillo, R., Stark, P.: Ballot-marking devices cannot assure the will of the voters. Elect. Law J.: Rules Politics Policy 19(3), 432–450 (2020). https://doi.org/10.1089/elj.2019.0619
Appel, A., Stark, P.: Evidence-based elections: create a meaningful paper trail, then audit. Georgetown Law Technol. Rev. 4(2), 523–541 (2020). https://georgetownlawtechreview.org/wp-content/uploads/2020/07/4.2-p523-541-Appel-Stark.pdf
Bañuelos, J., Stark, P.: Limiting risk by turning manifest phantoms into evil zombies. Technical report (2012). arXiv preprint http://arxiv.org/abs/1207.3413. Accessed 17 July 2012
Ottoboni, K., Bernhard, M., Halderman, J.A., Rivest, R.L., Stark, P.B.: Bernoulli ballot polling: a manifest improvement for risk-limiting audits. In: Bracciali, A., Clark, J., Pintore, F., Rønne, P.B., Sala, M. (eds.) FC 2019. LNCS, vol. 11599, pp. 226–241. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-43725-1_16
Blom, M., et al.: Assertion-based approaches to auditing complex elections, with application to party-list proportional elections. In: Krimmer, R., et al. (eds.) E-Vote-ID 2021. LNCS, vol. 12900, pp. 47–62. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-86942-7_4
Blom, M., Stark, P.B., Stuckey, P.J., Teague, V., Vukcevic, D.: Auditing Hamiltonian elections. In: Bernhard, M., et al. (eds.) FC 2021. LNCS, vol. 12676, pp. 235–250. Springer, Heidelberg (2021). https://doi.org/10.1007/978-3-662-63958-0_21
Glazer, A., Spertus, J., Stark, P.: More style, less work: card-style data decrease risk-limiting audit sample sizes. Digit. Threats Res. Pract. 2, 1–15 (2021). https://doi.org/10.1145/3457907
Harrison, A., Fuller, B., Russell, A.: Lazy risk-limiting ballot comparison audits (2022). https://doi.org/10.48550/arXiv.2202.02607. https://arxiv.org/abs/2202.02607
Higgins, M., Rivest, R., Stark, P.: Sharper p-values for stratified post-election audits. Stat. Polit. Policy 2(1) (2011). https://doi.org/10.2202/2151-7509.1031
Ottoboni, K., Stark, P.B., Lindeman, M., McBurnett, N.: Risk-limiting audits by stratified union-intersection tests of elections (SUITE). In: Krimmer, R., et al. (eds.) E-Vote-ID 2018. LNCS, vol. 11143, pp. 174–188. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00419-4_12. Preprint: arxiv.org/abs/1809.04235
Spertus, J.V., Stark, P.B.: Sweeter than SUITE: supermartingale stratified union-intersection tests of elections. In: Krimmer, R., Volkamer, M., Duenas-Cid, D., Rønne, P., Germann, M. (eds.) E-Vote-ID 2022. LNCS, vol. 13553, pp. 106–121. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15911-4_7
Sridhar, M., Rivest, R.L.: k-Cut: a simple approximately-uniform method for sampling ballots in post-election audits. In: Bracciali, A., Clark, J., Pintore, F., Rønne, P.B., Sala, M. (eds.) FC 2019. LNCS, vol. 11599, pp. 242–256. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-43725-1_17
Stark, P.: Conservative statistical post-election audits. Ann. Appl. Stat. 2, 550–581 (2008). http://arxiv.org/abs/0807.4005
Stark, P.: Risk-limiting post-election audits: \(P\)-values from common probability inequalities. IEEE Trans. Inf. Forensics Secur. 4, 1005–1014 (2009)
Stark, P.: Delayed stratification for timely risk-limiting audits (2019). https://www.stat.berkeley.edu/~stark/Preprints/delayed19.pdf
Stark, P.B.: Sets of half-average nulls generate risk-limiting audits: SHANGRLA. In: Bernhard, M., et al. (eds.) FC 2020. LNCS, vol. 12063, pp. 319–336. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-54455-3_23
Stark, P.: ALPHA: audit that learns from previously hand-audited ballots. Ann. Appl. Stat. (2022). Preprint: https://arxiv.org/abs/2201.02707
Stark, P., Xie, R.: They may look and look, yet not see: BMDs cannot be tested adequately. In: Krimmer, R., et al. (eds.) E-Vote-ID 2022. LNCS, vol. 13553, pp. 122–138. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15911-4_8
Waudby-Smith, I., Stark, P.B., Ramdas, A.: RiLACS: risk limiting audits via confidence sequences. In: Krimmer, R., et al. (eds.) E-Vote-ID 2021. LNCS, vol. 12900, pp. 124–139. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-86942-7_9
Acknowledgments
I am grateful to Marilyn Marks for helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Stark, P.B. (2023). Non(c)esuch Ballot-Level Comparison Risk-Limiting Audits. In: Katsikas, S., et al. Computer Security. ESORICS 2022 International Workshops. ESORICS 2022. Lecture Notes in Computer Science, vol 13785. Springer, Cham. https://doi.org/10.1007/978-3-031-25460-4_31
Download citation
DOI: https://doi.org/10.1007/978-3-031-25460-4_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-25459-8
Online ISBN: 978-3-031-25460-4
eBook Packages: Computer ScienceComputer Science (R0)