Paper 2008/358

History-Independent Cuckoo Hashing

Moni Naor, Gil Segev, and Udi Wieder

Abstract

Cuckoo hashing is an efficient and practical dynamic dictionary. It provides expected amortized constant update time, worst case constant lookup time, and good memory utilization. Various experiments demonstrated that cuckoo hashing is highly suitable for modern computer architectures and distributed settings, and offers significant improvements compared to other schemes. In this work we construct a practical {\em history-independent} dynamic dictionary based on cuckoo hashing. In a history-independent data structure, the memory representation at any point in time yields no information on the specific sequence of insertions and deletions that led to its current content, other than the content itself. Such a property is significant when preventing unintended leakage of information, and was also found useful in several algorithmic settings. Our construction enjoys most of the attractive properties of cuckoo hashing. In particular, no dynamic memory allocation is required, updates are performed in expected amortized constant time, and membership queries are performed in worst case constant time. Moreover, with high probability, the lookup procedure queries only two memory entries which are independent and can be queried in parallel. The approach underlying our construction is to enforce a canonical memory representation on cuckoo hashing. That is, up to the initial randomness, each set of elements has a unique memory representation.

Metadata
Available format(s)
PDF PS
Category
Applications
Publication info
Published elsewhere. ICALP '08.
Keywords
History-independent data structuresCuckoo hashing.
Contact author(s)
gil segev @ weizmann ac il
History
2008-08-18: received
Short URL
https://ia.cr/2008/358
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/358,
      author = {Moni Naor and Gil Segev and Udi Wieder},
      title = {History-Independent Cuckoo Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2008/358},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/358}},
      url = {https://eprint.iacr.org/2008/358}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.