Welcome to the resource topic for 2001/036
Title:
Anti-persistence: History Independent Data Structures
Authors: Moni Naor, Vanessa Teague
Abstract:Many data structures give away much more information than they
were intended to. Whenever privacy is important, we need to be
concerned that it might be possible to infer information from the
memory representation of a data structure that is not available
through its ``legitimate’’ interface. Word processors that
quietly maintain old versions of a document are merely the most
egregious example of a general problem.
We deal with data structures whose current memory representation does
not reveal their history. We focus on dictionaries, where this means
revealing nothing
about the order of insertions or deletions. Our first algorithm is
a hash table based on open addressing,
allowing O(1) insertion and search. We also present
a history independent dynamic perfect hash table that uses space
linear in the number of elements inserted and has expected amortized
insertion
and deletion time O(1). To solve the dynamic perfect hashing
problem we devise a general scheme for history independent
memory allocation.
For fixed-size records this is quite efficient, with insertion and
deletion both linear in the size of the record. Our variable-size
record
scheme is efficient enough for dynamic perfect hashing but not for
general use. The main open problem we leave is whether it is possible
to implement a variable-size record scheme with low overhead.
ePrint: https://eprint.iacr.org/2001/036
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .