International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Tamper-Evident, History-Independent, Subliminal-Free Data Structures on PROM Storage -or- How to Store Ballots on a Voting Machine

Authors:
David Molnar
Tadayoshi Kohno
Naveen Sastry
David Wagner
Download:
URL: http://eprint.iacr.org/2006/081
Search ePrint
Search Google
Abstract: We enumerate requirements and give constructions for the vote storage unit of an electronic voting machine. In this application, the record of votes must survive even an unexpected failure of the machine; hence the data structure should be durable. At the same time, the order in which votes are cast must be hidden to protect the privacy of voters, so the data structure should be history-independent. Adversaries may try to surreptitiously add or delete votes from the storage unit after the election has concluded, so the storage should be tamper-evident. Finally, we must guard against an adversarial voting machine's attempts to mark ballots through the representation of the data structure, so we desire a subliminal-free representation. We leverage the properties of Programmable Read Only Memory (PROM), a special kind of write-once storage medium, to meet these requirements. We give constructions for data structures on PROM storage that simultaneously satisfy all our desired properties. Our techniques can significantly reduce the need to verify code running on a voting machine.
BibTeX
@misc{eprint-2006-21574,
  title={Tamper-Evident, History-Independent, Subliminal-Free Data Structures on PROM Storage -or- How to Store Ballots on a Voting Machine},
  booktitle={IACR Eprint archive},
  keywords={applications /},
  url={http://eprint.iacr.org/2006/081},
  note={Short version to appear in IEEE Security and Privacy 2006. This is the full version. dmolnar@eecs.berkeley.edu 13208 received 28 Feb 2006, last revised 1 Mar 2006},
  author={David Molnar and Tadayoshi Kohno and Naveen Sastry and David Wagner},
  year=2006
}