**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.

**Category / Keywords: **oblivious ram, oblivious hash table

**Date: **received 6 Apr 2021, last revised 8 Apr 2021

**Contact author: **dgnoble at cis upenn edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20210408:212226 (All versions of this report)

**Short URL: **ia.cr/2021/447

[ Cryptology ePrint archive ]