TL;DR
This paper introduces a novel Private Set-Intersection (PSI) protocol that outputs the intersection in an encrypted format. This encrypted output can then be seamlessly integrated with other secure two-party computation (2PC) techniques, enabling more efficient secure computation of arbitrary functions over the intersection of private sets.
What Problem Does This Paper Address?
Private Set-Intersection (PSI) is a crucial cryptographic primitive used in various applications, such as contact discovery in messaging apps or identifying common interests for matchmaking. While efficient PSI protocols exist, particularly those leveraging Oblivious Transfer (OT) extensions, they often reveal the intersection to one of the parties. This limitation prevents secure post-processing of the intersection result, hindering its use in more complex secure computations where the output needs to remain private or be further processed by other 2PC protocols. The paper addresses this by proposing a PSI protocol that outputs an "encrypted" intersection, making it compatible with a wider range of 2PC frameworks.
Methods
The core of the paper's contribution lies in an OT-based Private Set Membership (PSM) protocol that produces an encrypted output. This PSM protocol is then combined with a hashing approach, similar to prior work by Pinkas et al. (PSZ), to achieve efficient PSI.
The PSM protocol involves constructing a graph where nodes represent prefixes of elements in the sender's set. The receiver navigates this graph using multiple executions of a 1-out-of-2 OT protocol, guided by the bits of their input element. This navigation allows the receiver to obtain either a key corresponding to their element if it's in the sender's set, or a "sink key" otherwise. The output is then encrypted using these keys.
The paper also discusses optimizations and extensions, including:
- Point and Permute: A technique to improve efficiency by adding pointers to ciphertexts in subsequent layers, reducing the need for repeated decryptions.
- One-time Pad: An optimization for reducing communication complexity in the final layers.
- PSM with Secret Shared Input: Adapting the protocol to work with secret-shared inputs.
- PSI from PSM: Leveraging the PSM protocol to build a full PSI protocol, similar to the PSZ approach, by running multiple PSM instances and using hashing to achieve sub-quadratic complexity.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Encrypted Output for Composability: The most significant insight is the design of a PSI protocol that outputs an encrypted intersection. This is crucial for enabling the composition of PSI with other 2PC protocols, unlocking more complex and versatile secure computations.
- Leveraging OT for Encrypted Output: The paper demonstrates how to effectively use OT, a relatively cheap cryptographic primitive due to OT-extension techniques, to achieve the goal of an encrypted PSI output.
- Graph-Based Navigation for Set Membership: The novel use of a graph structure with levels representing prefixes of set elements, navigated via OT, is a key technique for achieving private set membership with an encrypted outcome.
- Bridging the Gap between Specialized PSI and General 2PC: The work effectively bridges the gap between highly optimized, specialized PSI protocols and the broader capabilities of general 2PC frameworks, allowing for more efficient execution of functions like $z = f(X \cap Y)$.
Key Results
The paper proposes a novel OT-based PSI protocol that produces an encrypted output. This protocol is shown to be efficient, with a computational complexity comparable to existing PSI protocols and better performance than circuit-based PSI approaches in terms of symmetric key operations and communication. The authors provide a formal security proof for their protocol under the semi-honest model, demonstrating its security guarantees. The paper also presents a detailed complexity analysis comparing their approach to prior work.
Limitations and Future Work
- Semi-Honest Security: The protocol is designed for semi-honest adversaries. The authors acknowledge that extending this to actively secure protocols (against malicious adversaries) is an interesting open problem.
- Two-Party Setting: The current work focuses on the two-party setting. The authors suggest that extending the result to the multiparty case is a promising future research direction.
- Malicious Adversaries: While the paper focuses on semi-honest security, it mentions that using an actively secure OT-extension protocol could lead to a protocol with privacy but not correctness. This highlights the challenge of achieving full security against malicious adversaries while maintaining efficiency.
- Efficiency for Malicious Adversaries: Designing efficient protocols that are secure against active adversaries and produce encrypted output remains an open problem.
Summary updated