Anti-presistence: history independent data structures

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.

REFERENCES

• 1: O. Amble and D. Knuth. Ordered hash tables. The Computer Journal, 17(2):135-142, 1974. Reprinted in: D. E. Knuth, Selected Papers on Analysis of Algorithms, Center for the Study of Language and Information Lecture Notes, no. 102, Stanford, 2000.
• 2: Arne Anderson , Thomas Ottmann, Faster uniquely represented dictionaries, Proceedings of the 32nd annual symposium on Foundations of computer science, p.642-649, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185430]
• 3: Richard P. Brent, Reducing the retrieval time of scatter storage techniques, Communications of the ACM, v.16 n.2, p.105-109, Feb. 1973 [doi>10.1145/361952.361964]
• 4: M. Dietzfelbinger , Friedhelm Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.6-19, July 1990, Warwick University, England
• 5: Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm MeyerAuf Der, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
• 6: James R. Driscoll , Neil Sarnak , Daniel D. Sleator , Robert E. Tarjan, Making data structures persistent, Journal of Computer and System Sciences, v.38 n.1, p.86-124, February 1989 [doi>10.1016/0022-0000(89)90034-2]
• 7: Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
• 8: Oded Goldreich , Rafail Ostrovsky, Software protection and simulation on oblivious RAMs, Journal of the ACM (JACM), v.43 n.3, p.431-473, May 1996 [doi>10.1145/233551.233553]
• 9: L. J. Guibas and E. Szemeredi. The analysis of double hashing. Journal of Computer and System Sciences, 16:226-274, 1978.
• 10: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 11: R. J. Lipton and J. F. Naughton. Clocked adversaries for hashing. Algorithmica, 9(3):239-252, 1993.
• 12: G. S. Lueker and M. Molodowitch. More analysis of double hashing. Combinatorica, 13(1):83-96, 1993.
• 13: Daniele Micciancio, Oblivious data structures: applications to cryptography, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.456-464, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258638]
• 14: J. P. Schmidt , A. Siegel, On aspects of university and performance for closed hashing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.355-366, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73041]
• 15: R. Seidel and C. Aragon. Randomized search trees. Algorithmica, 16:464-497, 1996.
• 16: A. Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proc. 30th IEEE Symp. on Foundations of Computer Science, pages 20-25, 1989.
• 17: J. P. Schmidt , A. Siegel, The analysis of closed hashing under limited randomness, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.224-234, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100245]
• 18: Andrew C. Yao, Uniform hashing is optimal, Journal of the ACM (JACM), v.32 n.3, p.687-693, July 1985 [doi>10.1145/3828.3836]

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.1 Public Policy Issues
          Subjects: Privacy
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

General Terms:
Algorithms, Human Factors, Measurement, Performance, Security, Theory, Verification

Keywords:
algorithms, anti-persistence, data structures, hash table, history independence, privacy, security