Cuckoo Hashing

Cuckoo hashing maintains two separate hash tables, each with its own independent hash function. An element x can only reside in one of two possible locations: Table 1 at index h1(x) or Table 2 at index h2(x). This deterministic placement guarantees that lookups require checking at most two positions, achieving worst-case O(1) constant-time retrieval.

When inserting an element x and both candidate slots are occupied, the algorithm evicts the existing occupant and re-inserts it using its alternate hash function. This triggers a chain of relocations:

• Evicted element y moves to its alternate slot
• If that slot is occupied, z is evicted and re-inserted
• The process continues until a vacant slot is found

This cascading behavior is the origin of the name, inspired by the brood parasitism of cuckoo birds that evict other eggs from nests.

An insertion sequence can enter an infinite loop where evictions cycle through the same set of occupied slots. To handle this, implementations enforce a maximum eviction threshold (typically O(log n)). If the threshold is exceeded, the entire data structure is rebuilt from scratch using two new randomly selected hash functions. This rehashing operation is amortized over many insertions, preserving expected constant-time insertion performance.

With two tables of size (1+ε)n each, Cuckoo hashing achieves a load factor exceeding 95% while maintaining constant-time operations. The space overhead is tunable:

• Higher ε reduces insertion failures and rehash frequency
• Lower ε maximizes memory utilization
• Practical PSI implementations often use ε ≈ 0.2 to 0.4 to balance speed and space

This efficiency is critical for PSI protocols where hash tables must fit within tightly constrained communication budgets.

Cuckoo hashing is a core component of modern PSI protocols like KKRT and PSZ. It enables efficient oblivious transfer (OT)-based membership testing:

• The sender inserts their set into a Cuckoo table
• The receiver uses OT to probe specific table positions without revealing which element they are querying
• The deterministic two-slot placement ensures each receiver element requires only a small, fixed number of OT operations

This reduces communication complexity from linear to sublinear in the sender's set size.

Several optimized variants extend the basic scheme:

• d-ary Cuckoo Hashing: Uses d > 2 hash functions and tables, reducing eviction chains at the cost of more lookup probes
• Cuckoo Hashing with a Stash: A small auxiliary storage for elements that fail to insert, eliminating rehashing entirely at the cost of a bounded stash size
• Bucketized Cuckoo Hashing: Each table slot holds a small bucket of b elements, improving load factor and reducing insertion failures

Bucketized variants are particularly popular in PSI for their cache-friendly memory access patterns.

A foundational cryptographic primitive where a sender inputs two messages and a receiver selects one, with the sender learning nothing about the choice and the receiver learning nothing about the unchosen message. In Cuckoo hashing-based PSI, OT is the core building block used to compare hashed items bin-by-bin without revealing non-matching elements, with the Cuckoo table structure minimizing the total number of OT invocations required.

A cryptographic technique that efficiently generates a large number of Oblivious Transfers from a small number of base OTs using only fast symmetric-key operations. When combined with Cuckoo hashing, OT extension enables PSI protocols to scale to sets with millions of items while maintaining practical execution times, as the Cuckoo table's bin count determines the number of extended OTs needed.

A PSI variant optimized for scenarios where one party's set is significantly larger than the other's, such as a client with a small contact list querying a server with millions of users. Cuckoo hashing is particularly advantageous here, as the smaller sender set can be placed into a compact Cuckoo table while the larger receiver set uses simple hashing, minimizing the computational burden on the resource-constrained client.

A space-efficient probabilistic data structure for set membership testing with a controllable false-positive rate. While Bloom filters are used in some PSI constructions, Cuckoo hashing offers a deterministic alternative with no false positives and constant-time worst-case lookups. Modern protocols often prefer Cuckoo hashing for its exact matching guarantees, though Bloom filters remain relevant for bandwidth-constrained applications.

A critical performance metric measuring the total data exchanged between parties during protocol execution. Cuckoo hashing directly optimizes communication complexity in PSI by reducing the number of OT comparisons from O(n) to O(n/β) where β is the bin size, effectively slashing bandwidth requirements and making PSI viable in bandwidth-constrained environments like mobile networks.