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-zero 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.