Name
Title | ||
|---|---|---|
Deterministic history-independent strategies for storing information on write-once memories |
Abstract | ||
|---|---|---|
Motivated by the challenging task of designing "secure" vote storage mechanisms, we deal with 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. In this setting, 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. Whereas previously known constructions were either inefficient (required Θ(K2) 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. In addition, we consider 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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-73420-8_28 | international colloquium on automata, languages and programming |
Keywords | DocType | Volume |
history-independent,vote storage mechanism,storing information,information-theoretic security,tamper-evident,vote storage mech- anisms,deterministic history-independent strategy,size n,conflict resolution,write-once memory,information storage mechanism,large universe,expander graphs,hostile environment,non-adaptive conflict resolution algorithm,k element,information storage,expander graph,standard model,information theoretic security | Conference | 2007 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-73419-8 | 8 |
PageRank | References | Authors |
0.49 | 28 | 3 |