Introduction
Private Set Intersection (PSI) is a fundamental cryptographic primitive that allows two parties, Alice and Bob, to compute the intersection of their respective private sets without revealing any information about elements not in the intersection. As data collaboration becomes increasingly vital for fields like medical research and fraud detection, the need for PSI protocols that are both computationally efficient and rigorously secure has grown. This paper presents a suite of PSI protocols that achieve linear communication and computation complexity while providing simulation-based security—the gold standard for ensuring protocol safety against semi-honest and malicious adversaries.
Problem Statement
Historically, PSI protocols faced a trade-off between theoretical security and practical performance. Many early solutions suffered from quadratic complexity ($O(n^2)$), making them unusable for large datasets. Furthermore, many efficient protocols lacked formal simulation-based security proofs, leaving potential vulnerabilities. This research aims to bridge this gap by developing protocols that scale linearly with set size ($O(n)$) while maintaining robust security guarantees.
Methodology
The proposed protocols leverage two primary cryptographic and algorithmic tools: Additively Homomorphic Encryption (AHE) and advanced hashing techniques.
Polynomial Representation and Oblivious Evaluation
The core of the approach involves representing sets as polynomials. Party 1 ($P_1$) defines a polynomial $Q(x)$ such that its roots are the elements of their set. The coefficients of $Q(x)$ are encrypted using an AHE scheme (e.g., Paillier or ElGamal) and sent to Party 2 ($P_2$).
$P_2$ then performs an oblivious evaluation. For each element $y$ in their set, $P_2$ uses the homomorphic properties of the encryption to compute an encryption of $r \cdot Q(y) + y$, where $r$ is a random value. If $y$ is a root of $Q(x)$ (meaning it is in the intersection), $Q(y) = 0$, and the result decrypts to $y$. Otherwise, the result is a random value, hiding the identity of the non-matching element.
Hashing for Linear Complexity
To avoid the $O(n^2)$ cost of evaluating a single high-degree polynomial, the authors utilize hashing to distribute elements into smaller bins. They compare three main strategies:
- Simple Hashing: Elements are mapped to bins, and small polynomials are evaluated per bin. Bin sizes must be padded to the maximum possible size to prevent information leakage.
- Balanced Allocations: This method uses multiple hash functions to achieve a more uniform distribution across bins, reducing the necessary padding.
- Cuckoo Hashing: This sophisticated technique ensures that most bins contain only a single element, which significantly reduces the degree of the polynomials being evaluated.
Malicious Security
To protect against parties that might deviate from the protocol (malicious actors), the authors introduce a "redo and verify" technique within the Random Oracle Model. This approach provides security without the massive computational overhead typically associated with Zero-Knowledge proofs or "cut-and-choose" mechanisms.
Experimental Results
The protocols were evaluated using synthetic datasets with set sizes ranging from 10 to 1,000,000 elements. Elements were represented as 160-bit strings for ElGamal-based implementations and 1024-bit strings for Paillier-based ones.
Performance Insights
A key finding was the distinction between asymptotic complexity and real-world performance. While Cuckoo hashing is theoretically superior ($O(n)$), the overhead of managing multiple polynomials (three per element) made it slower than simple hashing for sets up to 100,000 elements. The experiments indicated that the total number of polynomials evaluated often impacts performance more than the degree of those polynomials.
Furthermore, ElGamal-based PSI consistently outperformed Paillier-based versions. This is attributed to ElGamal's use of smaller prime-order groups compared to the large composite-order groups required by Paillier.
Scalability
The protocols demonstrated successful linear scaling. For a set size of $n=10,000$, the semi-honest ElGamal protocol with random hashing completed in approximately 65 seconds. The results suggest that Cuckoo hashing becomes the most efficient choice only at very large scales, approaching $n=1,000,000$.
Conclusion
This work demonstrates that highly secure, simulation-based PSI can be achieved with linear overhead. By optimizing the interplay between homomorphic encryption and hashing, the authors provide a practical path for secure data collaboration. Future research may address the "stash" requirement in Cuckoo hashing and explore communication compression techniques such as Oblivious Transfer (OT) extension to further enhance efficiency.
Summary updated