NDSS 2025 – Recurrent Private Set Intersection For Unbalanced Databases With Cuckoo Hashing

Why It Matters

The protocol enables fast, privacy‑preserving filtering for high‑volume services like email and URL denylisting, reducing latency and computational costs. Its efficiency on slower networks expands practical deployment of secure set intersection in real‑world security pipelines.

Key Takeaways

• Optimized for recurrent intersections of small sets
• Uses leveled FHE with Microsoft SEAL library
• Cuckoo hashing reduces lookup overhead dramatically
• Achieves 20 ms latency on 10 Gbps networks

Pulse Analysis

Private Set Intersection (PSI) has become a cornerstone of privacy‑preserving data sharing, yet most implementations assume similarly sized datasets and single‑shot execution. In practice, many security workflows—such as email spam detection or URL blacklist checks—require repeatedly intersecting tiny query sets against a massive reference list. Traditional PSI protocols must restart the entire cryptographic exchange for each query, incurring prohibitive latency and bandwidth overhead, especially on constrained networks.

The NDSS 2025 paper tackles this gap by marrying leveled Fully Homomorphic Encryption (FHE) with cuckoo hashing, a high‑performance hash table scheme. Leveraging Microsoft’s SEAL library, the authors implement a recurrent PSI that pre‑processes the large database into a cuckoo hash structure, enabling constant‑time lookups for each incoming small set. Optimizations such as batch ciphertext packing and network‑aware parameter tuning shrink the cryptographic workload, delivering intersection times of 20 ms on 10 Gbps links and 240 ms on 100 Mbps links—far faster than existing solutions.

The implications for enterprise security are significant. Real‑time, privacy‑preserving filtering can now be embedded directly into email gateways, web proxies, and threat‑intel platforms without sacrificing speed or exposing sensitive data. Faster PSI on slower networks lowers the barrier for adoption in remote or bandwidth‑limited environments, expanding the reach of secure data collaboration across industries. As regulatory pressures mount for data minimization, such efficient cryptographic primitives will likely become a standard component of next‑generation security architectures.