Recurrent Private Set Intersection for Unbalanced Databases with Cuckoo Hashing and Leveled FHE

Recurrent Private Set Intersection for Unbalanced Databases with Cuckoo Hashing and Leveled FHE

Speakers: Eduardo Chielle

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=RijlYkOjCW8

Overview

This talk by Eduardo Chielle introduces a novel protocol for Private Set Intersection (PSI), specifically designed to address the challenges of recurrent intersections involving unbalanced databases. PSI is a cryptographic primitive that allows two or more parties to compute the intersection of their private datasets without revealing any information about the elements not in the intersection. While traditional PSI protocols often assume sets of similar sizes and one-time computations, many real-world applications, such as private contact discovery or malicious URL detection, involve a small, frequently changing set intersecting with a large, static database.

The core contribution of this work is an efficient PSI protocol tailored for this "recurrent, unbalanced" setting. The protocol leverages Cuckoo Hashing for efficient data structuring and Leveled Fully Homomorphic Encryption (FHE) combined with a novel Chinese Remainder Theorem (CRT)-based packing technique to drastically reduce both computation and communication costs. The speaker demonstrates that their approach achieves a speedup of one to two orders of magnitude compared to state-of-the-art methods, making privacy-preserving operations feasible for a wider range of practical applications, particularly those requiring high throughput and low latency.

The motivation for this research stems from critical security applications like institutional email phishing protection. In such scenarios, a mail server needs to check URLs from incoming emails against a large database of known malicious URLs held by a service provider, without exposing the user's email content to the provider. The recurrent nature arises from the continuous stream of emails, while the unbalanced aspect comes from a few URLs per email compared to a million-entry malicious URL database. This work provides a robust and efficient solution to this prevalent privacy-security dilemma.

Background

▶ Watch: Introduction to Private Set Intersection and challenges (0:00)

Private Set Intersection (PSI) is a fundamental cryptographic primitive enabling two or more parties to compute the common elements between their sets without revealing any information about the non-intersecting elements. In a typical two-party PSI protocol, there is a designated sender and a receiver; the receiver learns the intersection, while the sender learns nothing. Historically, PSI protocols have been designed with the assumption that participating parties hold sets of roughly similar sizes. This assumption, however, breaks down in numerous practical applications, leading to significant inefficiencies.

The emergence of applications like private contact discovery highlights the need for unbalanced PSI. For instance, when a new user joins a messaging app like WhatsApp, they might want to find which of their contacts are already on the platform. Their contact list (the "small set") is intersected against the entire WhatsApp user base (the "large set"). Similarly, in enterprise security, a mail server might need to compare a handful of URLs from an incoming email against a vast database of millions of known malicious URLs maintained by a threat intelligence provider. These scenarios necessitate protocols optimized for situations where one set is orders of magnitude smaller than the other.

Compounding this challenge is the requirement for recurrent PSI. In the phishing protection example, while an individual might receive only a few emails per day, an entire institution with thousands of users will process a continuous stream of emails. This means the intersection operation needs to be performed repeatedly, perhaps thousands of times per second, against the same large, static malicious URL database. Running a full PSI protocol from scratch for every new small set (each email's URLs) would be prohibitively expensive in terms of both computation and communication. The state-of-the-art prior to this work struggled with the combined demands of unbalanced and recurrent PSI, lacking the efficiency required for real-time, high-volume deployments. This research directly addresses these limitations by designing a protocol with a one-time setup cost for the large set and a highly efficient, linear cost for subsequent recurrent intersections involving small sets.

Key Findings

▶ Watch: Summary of protocol's efficiency and performance improvements (2:50)

The central finding of this research is the development of a highly efficient protocol for recurrent private set intersection (PSI) with unbalanced databases, significantly outperforming existing state-of-the-art solutions. The protocol is specifically engineered for scenarios where a small set frequently needs to be intersected against a large, static database.

The key contributions and findings include:

• Novel Protocol Design: The proposed protocol features a one-time setup cost associated with the large database (the sender's set) and a linear cost relative to the size of the smaller, recurrent set (the receiver's set). This architecture is critical for applications requiring many intersections against a stable large dataset.
• Significant Performance Improvement: Through a combination of cryptographic techniques and optimizations, the protocol achieves a remarkable speedup. Depending on network speed and target set sizes, it is one to two orders of magnitude faster than existing state-of-the-art PSI protocols, particularly in its recurrent phase. For very small receiver set sizes (e.g., 4 entries), recurrent intersections can be completed in as little as 20 to 30 milliseconds on fast networks (10 Gbit/s).
• Drastic Communication Reduction: The protocol addresses the prohibitive communication costs typically associated with Homomorphic Encryption. By combining Cuckoo Hashing with a novel packing technique based on the Chinese Remainder Theorem (CRT), the initial encrypted large set, which would otherwise be around 7 terabytes (TB) for 1 million entries, is compressed down to a mere 12.5 megabytes (MB). This makes the initial setup phase practical even over slower networks.
• Efficient Search Mechanism: Cuckoo Hashing is employed to transform the computationally expensive linear search (requiring 1 million homomorphic multiplications per receiver entry in a naive FHE approach) into a constant-time operation, requiring only three multiplications for the chosen parameters. This significantly reduces the computational burden on the receiver during the intersection phase.
• Optimized FHE Parameterization: The reduction in the number of required homomorphic multiplications due to Cuckoo Hashing allows for the use of more efficient Fully Homomorphic Encryption (FHE) parameters. This further contributes to smaller ciphertext sizes and faster operations.
• Practical Applicability: The performance gains make the protocol suitable for real-world applications like private contact discovery and, as highlighted by the speaker, large-scale email phishing protection, where privacy and efficiency are paramount.

Technical Deep Dive

▶ Watch: Overview of the basic, inefficient FHE-based PSI protocol (3:30)

The proposed recurrent, unbalanced Private Set Intersection (PSI) protocol builds upon the principles of Fully Homomorphic Encryption (FHE) and introduces significant optimizations to overcome the inherent inefficiencies of FHE for large-scale operations. The speaker first outlines a basic, inefficient FHE-based PSI protocol as a blueprint, then details the two most impactful optimizations: Cuckoo Hashing and a novel CRT-based packing technique.

The Basic FHE-PSI Blueprint

The foundational protocol, while inefficient, illustrates the core idea of using FHE for PSI. It involves two parties: the sender (holding the large set, e.g., the malicious URL database) and the receiver (holding the small set, e.g., URLs from an email).

1. Sender's Setup (One-time): The sender encrypts its entire set X using its own FHE public key. This encrypted set is then sent to the receiver.
2. Receiver's Computation (Recurrent): For each element y in its small set, the receiver wants to check if y is present in X. The receiver performs a homomorphic subtraction of y from every encrypted element in the sender's set. If y is an element of X, one of these subtractions will result in a homomorphically encrypted zero. The receiver then computes the homomorphic product of all these subtraction results. If the product is zero, it indicates y is in X; otherwise, it's not. To prevent the sender from learning which specific element of X matched y, the receiver adds randomness to the homomorphic product.
3. Intermediate Result Transmission: The receiver sends this encrypted, randomized result back to the sender. Additionally, the receiver encrypts the random value used in step 2 with its own FHE key and sends it to the sender.
4. Sender's Finalization: The sender decrypts the result received in step 3. Since the result is still under the receiver's key (due to homomorphic operations), it appears random to the sender. The sender then performs a homomorphic subtraction of the encrypted random value (received in step 3 and encrypted under the receiver's key) from the main encrypted result. This effectively removes the receiver's randomness. To add another layer of security, the sender multiplies this result by another random number.
5. Final Result Transmission and Decryption: The sender sends this final, doubly-randomized encrypted result back to the receiver. The receiver decrypts it. If the decrypted value is zero, it confirms that y is part of the intersection; otherwise, it is not.

This blueprint has two major inefficiencies:

• Communication Cost: For a sender set of 1 million entries, sending the encrypted set (Step 1) would require approximately 7 terabytes (TB), which is impractical.
• Computation Cost: The linear search in Step 2, where the receiver compares its element y against 1 million encrypted entries, requires roughly 1 million homomorphic multiplications per receiver entry. This is computationally prohibitive.

Optimization 1: Cuckoo Hashing for Efficient Search

To address the prohibitive linear search, the protocol incorporates Cuckoo Hashing. Instead of comparing a receiver's element against every entry in the sender's set, Cuckoo Hashing allows the receiver to check only a few specific locations where the element could be.

• Mechanism: The sender first applies Cuckoo Hashing to its large set X. Cuckoo Hashing uses multiple hash functions to place items into a hash table. If a collision occurs (an item hashes to an occupied slot), the existing item is "kicked out" and re-hashed to an alternative location, continuing this process until all items are placed or a loop is detected (requiring a rehash of the entire table with new hash functions). This creates a highly compact data structure.
• Security Considerations: Simple hashing would reveal information about the distribution and load of items, potentially leaking data. To prevent this, the Cuckoo Hash table is padded with dummy values. The receiver performing the check does not know if a slot contains a real item or a dummy value.
• Benefits:
• Reduced Computation: Cuckoo Hashing reduces the search complexity from linear to constant time. For the parameters used in this work, the receiver only needs to perform three homomorphic multiplications to check for an element's presence, a massive reduction from 1 million.
• Compactness: Cuckoo Hashing creates a much more compact data structure compared to simple hashing with padding, which is crucial for minimizing the size of the encrypted set.
• FHE Parameter Optimization: The significant reduction in the number of required homomorphic multiplications allows the use of FHE parameters that support fewer multiplications, leading to smaller ciphertext sizes and faster operations.

Even with Cuckoo Hashing, the encrypted table size was still around 100 gigabytes (GB), which remained too large for practical communication.

Optimization 2: CRT-based Packing for Communication Reduction

To further reduce communication, especially the initial setup cost, the protocol introduces a novel packing technique on top of existing FHE batching capabilities, leveraging the Chinese Remainder Theorem (CRT).

• FHE Context (BFV Scheme): The protocol uses the BFV (Brakerski/Fan-Vercauteren) FHE scheme, which operates over an integer message space. Plaintexts and ciphertexts are represented as polynomials.
• Batching: Traditionally, one integer message would be encrypted into a single polynomial. Batching, a significant advancement in FHE, allows encoding n independent messages (where n is the polynomial degree) into a single plaintext polynomial. This means one ciphertext can homomorphically operate on n messages simultaneously, reducing computation.
• Proposed CRT-based Packing: The speaker's innovation is to add another layer of packing on top of batching. This technique allows packing k * n messages into a single polynomial, where k is a factor achieved through their CRT-based method.
• Encoding Process:

1. The sender's set X undergoes Cuckoo Hashing, which typically generates multiple hash tables for security and efficiency.
2. Each of these hash tables is then mapped to a different packing slot within a plaintext polynomial.
3. Within each packing slot, multiple elements are encoded using batching slots.
4. The final result is that many (k*n) elements from the Cuckoo Hash table are encoded into a single plaintext polynomial, which is then encrypted into a single ciphertext.

• Resulting Communication Cost: This combined approach reduces the encrypted Cuckoo Hash table size from 100 GB down to a remarkable 12.5 MB. For context, the unencrypted data size for the same 1 million entries is approximately 4 MB. This represents an almost 560,000-fold reduction from the original 7 TB estimate, making the initial setup phase highly efficient.

Protocol Instances

The paper proposes two instances of the protocol, catering to different recurrence frequencies:

• Fast Setup Instance: Optimized for scenarios with fewer recurrences, prioritizing a quicker initial setup.
• Fast Intersection Instance: Designed for applications with many recurrences (e.g., thousands of recurrent intersections per update of the large set), optimizing the recurring cost.

The speaker's results for the fast intersection instance show that the one-time setup cost ranges from 0.1 to 0.3 seconds on fast networks (10 Gbit/s) and 1.2 to 2.5 seconds on slower networks (100 Mbit/s). The recurrent cost for small receiver set sizes (e.g., 4 to 64 entries) is exceptionally low: 20 to 30 milliseconds on fast networks and 0.2 to 0.3 seconds on slower networks. This performance represents a significant leap, making recurrent, unbalanced PSI practical for high-demand applications.

Demo / Proof of Concept

▶ Watch: Optimizing linear search using cuckoo hashing for efficiency (6:00)

While the talk did not include a live demonstration of the protocol in action, the speaker presented comprehensive performance results and benchmarks that serve as a robust proof of concept for the protocol's efficiency and practicality. These results were derived from their implementation, which is publicly available on GitHub. The benchmarks directly illustrate the dramatic improvements in communication and computation costs achieved by their optimized design, comparing their protocol against state-of-the-art related work. The performance metrics, including setup times, recurrent intersection times, and overall speedups, effectively demonstrate the feasibility and superior performance of their proposed solution for recurrent private set intersection with unbalanced databases.

Defensive Implications

▶ Watch: Reducing communication cost with advanced FHE packing (7:00)

The recurrent private set intersection protocol presented by Eduardo Chielle has profound defensive implications, particularly in areas where organizations must balance robust security measures with stringent privacy requirements. The core benefit is enabling privacy-preserving security services that were previously impractical due to computational and communication overheads, or that required unacceptable data exposure.

One of the most compelling applications highlighted is email phishing protection. Institutions can deploy this protocol to protect their users from malicious URLs without requiring their mail servers to expose the full list of URLs from incoming emails to a third-party threat intelligence service. Instead, the mail server (receiver) can securely query a service provider's (sender's) vast database of malicious URLs. If an intersection is found, the email can be blocked, but the service provider never learns the specific URLs users received, nor does the mail server learn the entire malicious URL database. This significantly reduces the attack surface and potential for data breaches associated with centralizing sensitive email content.

Beyond phishing, this technology is applicable to:

• Private Contact Discovery in Enterprise Settings: Enabling employees to securely find colleagues within a large corporate directory without revealing their entire contact list to the directory service.
• Fraud Detection: Financial institutions could securely compare transaction patterns against known fraud indicators from a shared database without disclosing individual customer transaction details.
• Insider Threat Detection: An organization could check if an employee's activities match patterns of known insider threats from a security database, without revealing the employee's specific actions to the database holder.
• Vulnerability Management: Securely checking software inventories against databases of known CVEs (Common Vulnerabilities and Exposures) without revealing the full software stack to a third-party vulnerability scanner provider.

The protocol's efficiency, particularly its one-time setup cost for the large database and fast recurrent intersection capabilities (as low as 20-30 milliseconds), makes these privacy-preserving security operations feasible at scale and in near real-time. This allows organizations to enhance their security posture by leveraging external threat intelligence and shared security data, while simultaneously adhering to strict privacy regulations such as GDPR (General Data Protection Regulation) and CCPA (California Consumer Privacy Act). By minimizing data leakage and ensuring that only the bare minimum of information (the intersection) is revealed, organizations can build more secure and privacy-respecting defense mechanisms.

Key Takeaways

• Addressing Critical Gaps: The presented protocol effectively solves the challenging problem of recurrent Private Set Intersection (PSI) for unbalanced databases, which is crucial for real-world applications like private contact discovery and email phishing protection.
• Orders of Magnitude Faster: The protocol achieves a significant performance improvement, being one to two orders of magnitude faster than existing state-of-the-art PSI solutions, especially for the recurrent intersection phase.
• Cuckoo Hashing for Efficiency: Cuckoo Hashing is a key innovation, transforming computationally expensive linear searches into constant-time operations (only 3 homomorphic multiplications), drastically reducing the computational burden.
• Novel CRT-Based Packing for Communication: A new packing technique, built on top of FHE batching and leveraging the Chinese Remainder Theorem (CRT), compresses the large encrypted sender set from an initial 7 terabytes down to just 12.5 megabytes, making communication practical.
• Practical Privacy-Preserving Security: The combined optimizations enable the deployment of highly efficient, privacy-preserving security services, allowing organizations to detect threats (e.g., malicious URLs) without exposing sensitive user data to third-party providers.
• Open-Source Availability: The code for the protocol is available on GitHub, fostering further research, adoption, and development within the security and cryptography communities.

About the Speaker(s)

Eduardo Chielle is the speaker who presented this work at the NDSS Symposium. While his specific title and company affiliation were not mentioned in the provided transcript, his presentation clearly demonstrates deep expertise in the fields of cryptography, particularly Fully Homomorphic Encryption (FHE), and secure multi-party computation, as applied to practical security challenges like Private Set Intersection. His research focuses on developing highly efficient and scalable cryptographic protocols to enable privacy-preserving data operations.