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