Paper 2006/081

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

David Molnar, Tadayoshi Kohno, Naveen Sastry, and David Wagner

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.

Metadata
Available format(s)
PS
Category
Applications
Publication info
Published elsewhere. Short version to appear in IEEE Security and Privacy 2006. This is the full version.
Contact author(s)
dmolnar @ eecs berkeley edu
History
2006-03-01: revised
2006-03-01: received
See all versions
Short URL
https://ia.cr/2006/081
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/081,
      author = {David Molnar and Tadayoshi Kohno and Naveen Sastry and David Wagner},
      title = {Tamper-Evident, History-Independent, Subliminal-Free Data Structures on PROM Storage -or- How to Store Ballots on a Voting Machine},
      howpublished = {Cryptology ePrint Archive, Paper 2006/081},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/081}},
      url = {https://eprint.iacr.org/2006/081}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.