Cryptology ePrint Archive: Report 2006/081
Tamper-Evident, History-Independent, Subliminal-Free Data Structures on PROM Storage -or- How to Store Ballots on a Voting Machine
David Molnar and Tadayoshi Kohno and 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.
Category / Keywords: applications /
Publication Info: Short version to appear in IEEE Security and Privacy 2006. This is the full version.
Date: received 28 Feb 2006, last revised 1 Mar 2006
Contact author: dmolnar at eecs berkeley edu
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Version: 20060301:101848 (All versions of this report)
Short URL: ia.cr/2006/081
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]