Welcome to the resource topic for 2021/447
Title:
An Intimate Analysis of Cuckoo Hashing with a Stash
Authors: Daniel Noble
Abstract:Cuckoo Hashing is a dictionary data structure in which a data item is stored in a small constant number of possible locations. It has the appealing property that the data structure size is a small constant times larger than the combined size of all inserted data elements. However, many applications, especially cryptographic applications and Oblivious RAM, require insertions, builds and accesses to have a negligible failure probability, which standard Cuckoo Hashing cannot simultaneously achieve. An alternative proposal introduced by Kirsch et al. is to store elements which cannot be placed in the main table in a ``stash’', reducing the failure probability to O(n^{-s}) where n is the table size and s any constant stash size. This failure probability is still not negligible. Goodrich and Mitzenmacher showed that the failure probability can be made negligible in some parameter N when n = \Omega(log^7(N)) and s = \Theta(log N). In this paper, I will explore these analyses, as well as the insightful alternative analysis of Aumüller et al. Following this, I present a tighter analysis which shows failure probability negligible in N for all n = \omega(\log(N)) (which is asymptotically optimal) and I present explicit constants for the failure probability upper bound.
ePrint: https://eprint.iacr.org/2021/447
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 .