Single Layer Optical-scan Voting with Fully Distributed Trust

Aleksander Essex, Christian Henrich, Urs HengartnerIACR ePrint 2011 · OpenReview

TL;DR

This paper introduces a novel cryptographic voting system that achieves end-to-end verifiability with a single-layer optical-scan ballot, eliminating the need for trusted third parties and offering a public audit trail. It addresses the long-standing trade-off between cryptographic security and traditional, user-friendly voting methods.

What Problem Does This Paper Address?

Traditional optical-scan voting systems, while familiar to voters, often lack robust verifiability, making them susceptible to manipulation. Cryptographic voting systems aim to solve this by providing proofs that votes are counted correctly and that voter privacy is maintained. However, many existing cryptographic systems rely on complex multi-layer ballots or trusted entities (like ballot printers or election commissions) to achieve these goals. This creates a barrier to adoption due to increased complexity for voters and administrators, and the inherent risks associated with trusting any single party. The authors tackle the challenge of creating a system that is both cryptographically secure and end-to-end verifiable, while retaining the simplicity of a single-layer optical-scan ballot and distributing trust among multiple parties.

Methods

The paper proposes two systems, building upon the Scantegrity framework.

  • Basic System: This system uses a two-party protocol between ballot printers to generate ballots with randomized confirmation codes. It relies on a private paper audit trail and an in-person dispute resolution procedure. The core idea is to distribute the printing process so that neither printer knows the full ballot details, preventing them from linking a receipt to a specific vote.
  • Improved System: This system enhances the basic one by introducing "self-blanking" invisible ink confirmation codes. This innovation allows for a public paper audit trail without compromising ballot secrecy. It also introduces an informational dispute resolution procedure, where disputes can be resolved using knowledge of confirmation codes rather than physical receipts, further reducing reliance on trusted entities. The system leverages cryptographic primitives like homomorphic encryption and visual cryptography, along with physical security mechanisms like invisible ink and scratch-off coatings.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully demonstrates that it's possible to achieve strong cryptographic guarantees (end-to-end verifiability, distributed trust) while maintaining the simplicity and familiarity of traditional optical-scan ballots. This is a significant step towards making secure voting more accessible.
  • Self-Blanking Invisible Ink: The introduction of "self-blanking" invisible ink is a key innovation. It allows confirmation codes to be temporarily visible for voters to record, but then fade away, preventing them from being used to link receipts to votes later. This is crucial for enabling a public paper audit trail.
  • Informational Dispute Resolution: Moving from physical to informational dispute resolution reduces complexity and reliance on physical evidence, making the process more efficient and less prone to manipulation.
  • Distributed Trust in Printing: By splitting the ballot printing process between two independent printers, the system ensures that no single printer can compromise ballot secrecy or link receipts to votes.

Key Results

The paper presents two systems that meet the following requirements:

  1. Distributed Trust: No single party can deduce how a voter voted or link a receipt to a clear-text vote.
  2. Single Layer Ballot Form: A simple, familiar optical-scan ballot.
  3. Human-Readable Paper Audit Trail: The voting intent is evident on cast ballots.
  4. Public Paper Audit Trail: The collection of cast ballots can be made public without compromising secrecy (achieved by the improved system).

The improved system, in particular, offers a more efficient dispute resolution and a public paper audit trail, addressing limitations of previous systems like Scantegrity II.

Limitations and Future Work

  • Physical Primitive Assumptions: The security of the system relies on ideal functioning of physical primitives like invisible ink and scratch-off coating. The paper acknowledges that passive attacks on these primitives could be a concern, and suggests potential countermeasures like photographs or multiple auditors for evidence.
  • Usability of Disappearing Ink: The paper raises important usability questions regarding how the delayed darkening of invisible ink might affect voter behavior and their ability to record confirmation codes, especially in multi-contest ballots.
  • Future Work: The authors suggest extending the system to a secure multi-party protocol, distributing trust among more than two printers. This would require a new approach to private printing and ballot generation. They also note that proving coercion resistance for their system would be a natural extension, given its similarities to Scantegrity II.

Summary updated

Abstract

We present a new approach for cryptographic end-to-end verifiable optical-scan voting. Ours is the first that does not rely on a single point of trust to protect ballot secrecy while simultaneously offering a conventional single layer ballot form and unencrypted paper trail. We present two systems following this approach. The first system uses ballots with randomized confirmation codes and a physical in-person dispute resolution procedure. The second system improves upon the first by offering an informational dispute resolution procedure and a public paper audit trail through the use of self-blanking invisible ink confirmation codes. We then present a security analysis of the improved system.
BibTeX
@article{essex2011single,
  author = {Aleksander Essex and Christian Henrich and Urs Hengartner},
  title = {{Single Layer Optical-scan Voting with Fully Distributed Trust}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2011},
  url = {https://openreview.net/forum?id=1DqYLJsgiT},
}
Figure