Combining Private Set-Intersection with Secure Two-Party Computation

Michele Ciampi, Claudio Orlandi

TL;DR

This paper introduces a novel protocol for Private Set-Intersection (PSI) that outputs the intersection in an encrypted format. This is a significant advancement because it allows the result of PSI to be securely combined with other secure two-party computation (2PC) tasks, enabling more complex and efficient computations on private data without revealing intermediate results.

What Problem Does This Paper Address?

Private Set-Intersection (PSI) is a crucial cryptographic primitive where two parties want to find the common elements between their private sets without revealing any other information about their sets. While efficient PSI protocols exist, a major limitation is that their output is typically revealed to one of the parties. This prevents the secure post-processing of the intersection result, hindering its use in more complex secure computations. For example, if you want to compute a function f on the intersection of two sets, X and Y, i.e., f(X ∩ Y), existing PSI protocols would reveal X ∩ Y to one party, compromising privacy. This paper addresses this by designing a PSI protocol whose output is encrypted, allowing it to be seamlessly integrated into other 2PC protocols for secure computation of arbitrary functions on the intersection.

Methods

The core of the paper's contribution lies in its novel Private Set Membership (PSM) protocol, which is then used to build the PSI protocol. The PSM protocol is based on Oblivious Transfer (OT) and a specially constructed graph.

Here's a breakdown of the key techniques:

  • Graph Construction: A graph is constructed where nodes represent prefixes of elements in the sender's set Y. Special "sink" nodes are used to represent elements not in Y. This graph structure allows for efficient navigation.
  • Oblivious Navigation: The receiver, using a series of 1-out-of-2 OT (Oblivious Transfer) operations, navigates this graph. The OT protocol ensures that the receiver learns whether their input element x belongs to Y (by obtaining a specific key) or not (by obtaining a sink key), without revealing x to the sender or Y to the receiver.
  • Encrypted Output: The final output of the PSM protocol is an encrypted bit indicating membership. This encrypted output is designed to be compatible with various 2PC techniques like garbled circuits, secret sharing, and homomorphic encryption.
  • PSI Construction: The PSM protocol is then used to build the PSI protocol. The paper suggests a straightforward approach of running multiple PSM protocols (one for each element in the receiver's set) and also mentions the possibility of using hashing techniques (similar to prior work) to achieve better efficiency.

The protocol relies on a special private-key encryption scheme with efficiently verifiable and elusive range properties.

Datasets

Not discussed in the paper. The paper focuses on theoretical cryptographic protocols and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Encrypted Output is Key: The most significant insight is that by encrypting the output of PSI, it can be securely fed into subsequent 2PC computations. This bridges the gap between specialized PSI protocols and general-purpose 2PC.
  • Graph-Based PSM: The use of a specially constructed graph and oblivious navigation via OT is an elegant way to achieve private set membership.
  • Leveraging OT Extensions: The protocol benefits from advances in OT-extension techniques, making OT a more practical building block for efficient PSI.
  • Composability: The protocol's design emphasizes composability, allowing it to be a component in larger, more complex secure multi-party computations.

Key Results

The paper presents a theoretical construction of a Private Set Membership (PSM) protocol that outputs an encrypted bit. This PSM protocol can then be used to construct a Private Set Intersection (PSI) protocol with an encrypted output. The authors provide a formal security proof for their protocol under the semi-honest model.

While specific quantitative results on efficiency (like speedup percentages) are not the primary focus of this theoretical paper, they do provide a comparison table (Table 1) showing their protocol's computational and communication complexity against existing circuit-based PSI approaches for the PSM case. Their protocol is shown to have better performance in terms of symmetric key operations and communication bits compared to the considered circuit-based methods.

Limitations and Future Work

  • Semi-Honest Security: The protocol is designed for semi-honest adversaries. The authors acknowledge that extending it to actively or covertly 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 multi-party case is a promising future research direction.
  • Efficiency for Malicious Adversaries: While the paper mentions that using actively secure OT-extension protocols could lead to a protocol with privacy but not correctness, achieving full security against malicious adversaries while producing encrypted output remains a challenge.
  • Keyword Search and Applications: The paper outlines how their PSM protocol can be adapted for applications like encrypted keyword search and computing statistics on private intersections, suggesting these as areas for further exploration.

Summary updated

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},
}

Loading related content...

Figure