International Association
for Cryptologic Research

Cuckoo hashing is a powerful primitive that enables storing items using small space with efficient lookups. At a high level, cuckoo hashing maps $n$ items into $b$ entries storing at most $\ell$ items such that each item is placed into one of $k$ randomly chosen entries. Additionally, there is an overflow stash that can store at most $s$ items. Many cryptographic primitives rely upon cuckoo hashing to privately and efficiently embed data. It is integral to ensure small failure probability for constructing cuckoo hashing tables as it directly relates to the privacy.

As our main result, we present a more efficient cuckoo hashing construction using more hash functions. For construction failure probability $\epsilon$, the query complexity of our cuckoo hashing scheme is $O(\sqrt{\log(1/\epsilon)/\log n})$. This is a quadratic improvement over previously known cuckoo hashing constructions that used larger stashes or entries. We also prove lower bounds matching our construction.

We also initiate the study of robust cuckoo hashing where the input set may be chosen with knowledge of the hash functions. We present a cuckoo hashing scheme with query overhead $\tilde{O}(\log \lambda)$ that is robust against PPT adversaries except with ${\bf negl}(\lambda)$ probability. Furthermore, we present lower bounds showing that this construction is tight and that extending previous approaches of large stashes or entries cannot obtain robustness except with $\Omega(n)$ query overhead. In other words, robust cuckoo hashing may only be obtained efficiently with a large number of hash functions.

As applications of our results, we obtain improved constructions for batch codes and private information retrieval. In particular, we present the most efficient explicit batch code and blackbox reduction from single-query PIR to batch PIR.