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), ex-pected 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 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