Paper 2007/151

Deterministic History-Independent Strategies for Storing Information on Write-Once Memories

Tal Moran, Moni Naor, and Gil Segev

Abstract

Motivated by the challenging task of designing ``secure'' vote storage mechanisms, we study information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. We propose a mechanism for storing a set of at most $K$ elements from a large universe of size $N$ on write-once memories in a manner that does not reveal the insertion order of the elements. We consider a standard model for write-once memories, in which the memory is initialized to the all $0$'s state, and the only operation allowed is flipping bits from $0$ to $1$. Whereas previously known constructions were either inefficient (required $\Theta(K^2)$ memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements. We also demonstrate a connection between secure vote storage mechanisms and one of the classical distributed computing problems: conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. ICALP '07. This is the full version.
Keywords
History-indepedenceVote storageConflict resolution
Contact author(s)
gil segev @ weizmann ac il
History
2009-05-14: last of 4 revisions
2007-04-26: received
See all versions
Short URL
https://ia.cr/2007/151
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/151,
      author = {Tal Moran and Moni Naor and Gil Segev},
      title = {Deterministic History-Independent Strategies for Storing Information on Write-Once Memories},
      howpublished = {Cryptology ePrint Archive, Paper 2007/151},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/151}},
      url = {https://eprint.iacr.org/2007/151}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.