Combining Private Set-Intersection with Secure Two-Party Computation

Michele Ciampi, Claudio Orlandi

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

Abstract

Private Set-Intersection (PSI) is one of the most popular and practically relevant secure two-party computation (2PC) tasks. Therefore, designing special-purpose PSI protocols (which are more efficient than generic 2PC solutions) is a very active line of research. In particular, a recent line of work has proposed PSI protocols based on oblivious transfer (OT) which, thanks to recent advances in OT-extension techniques, is nowadays a very cheap cryptographic building block. Unfortunately, these protocols cannot be plugged into larger 2PC applications since in these protocols one party (by design) learns the output of the intersection. Therefore, it is not possible to perform secure post-processing of the output of the PSI protocol. In this paper we propose a novel and efficient OT-based PSI protocol that produces an “encrypted” output that can therefore be later used as an input to other 2PC protocols. In particular, the protocol can be used in combination with all common approaches to 2PC including garbled circuits, secret sharing and homomorphic encryption. Thus, our protocol can be combined with the right 2PC techniques to achieve more efficient protocols for computations of the form $$z=f(X\cap Y)$$ for arbitrary functions f.
BibTeX
@article{ciampi2018combining,
  author = {Michele Ciampi and Claudio Orlandi},
  title = {{Combining Private Set-Intersection with Secure Two-Party Computation}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
  url = {https://openreview.net/forum?id=TjYdI118ob},
}
Figure