History-Independent Cuckoo Hashing

Cuckoo hashing is a very efficient dynamic dictionary. It provides worst case constant lookup time (only two memory queries that are independent and can be performed in parallel), expected amortized constant update 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 dynamic dictionary, 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 has significant importance in preventing unintended leakage of information, and was also found useful in several algorithmic settings.

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.

HICuckooHashing.pdf
PDF file
HICuckooHashing.pptx
PowerPoint presentation

In  ICALP '08: Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part II

Publisher  Springer-Verlag

Details

TypeInproceedings
Pages631–642
ISBN978-3-540-70582-6
AddressBerlin, Heidelberg
> Publications > History-Independent Cuckoo Hashing