Paper 2021/447

An Intimate Analysis of Cuckoo Hashing with a Stash

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.

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Keywords
oblivious ramoblivious hash table
Contact author(s)
dgnoble @ cis upenn edu
History
2021-05-18: last of 2 revisions
2021-04-08: received
See all versions
Short URL
https://ia.cr/2021/447
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/447,
      author = {Daniel Noble},
      title = {An Intimate Analysis of Cuckoo Hashing with a Stash},
      howpublished = {Cryptology ePrint Archive, Paper 2021/447},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/447}},
      url = {https://eprint.iacr.org/2021/447}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.