Outsourced private set intersection using homomorphic encryption

Florian KerschbaumAsiaCCS 2012 · DOI

TL;DR

This paper introduces a novel, efficient, and secure protocol for Private Set Intersection (PSI) that can be outsourced to a cloud service provider. It leverages homomorphic encryption and Bloom filters to achieve security in the malicious model, client set size independence, and efficient computation, even in the presence of a potentially untrusted third-party service.

What Problem Does This Paper Address?

Private Set Intersection (PSI) is a fundamental cryptographic primitive that allows two parties, a client and a server, to compute the intersection of their respective datasets without revealing any information beyond the intersection itself. This has numerous applications, from privacy-preserving database queries to law enforcement searches against watchlists. While existing PSI protocols offer varying levels of security and efficiency, this paper tackles several key challenges:

  • Security in the Malicious Model: Many prior protocols only guarantee security against "semi-honest" adversaries (who follow the protocol but try to learn more). This paper aims for security against "malicious" adversaries who can deviate arbitrarily from the protocol.
  • Efficiency: Achieving security in the malicious model often comes at a significant computational or communication cost. The authors seek to maintain efficiency, ideally with linear complexity.
  • Client Set Size Independence: The size of the client's dataset can be sensitive information. The protocol aims to hide this size from the server.
  • Outsourcing to Cloud Services: A major goal is to enable the computation to be outsourced to an oblivious service provider (like a cloud service). This provider should perform the computation without learning anything about the inputs or the output, making PSI practical for cloud environments.
  • Minimal Assumptions: The authors strive to rely on the weakest possible cryptographic assumptions, specifically avoiding the random oracle model.

Methods

The paper presents a novel construction for PSI that combines two key cryptographic tools:

  • Homomorphic Encryption (HE): Specifically, the Goldwasser-Micali (GM) encryption scheme is used. GM encryption is public-key, semantically secure, and homomorphic under the XOR operation. This allows computations (like XOR) to be performed on encrypted data. For the outsourced version, a new HE scheme based on pairings (similar to BGN encryption but simplified) is introduced to handle the multiplicative depth required for the protocol.
  • Bloom Filters: These are probabilistic data structures that efficiently test for set membership. They are used to represent the client's set. The protocol leverages the fact that Bloom filters can have a small probability of false positives, which is managed by the protocol's parameters.

The core idea is to encrypt the client's Bloom filter using GM encryption. Then, for each element in the server's set, the protocol uses a technique called the Sander-Young-Yung (SYY) technique to perform a logical AND operation between the encrypted Bloom filter and the server's element. This process is designed to reveal only the intersection to the client.

For security in the malicious model, the paper introduces client set certification. A trusted third party (TTP) verifies the client's set before the PSI protocol begins. This prevents a malicious client from submitting a set designed to exploit false positives in the Bloom filter or to learn more about the server's set.

For outsourcing, the protocol is adapted to use an oblivious service provider. The client sends its encrypted Bloom filter, and the server sends its elements encrypted with a second HE scheme. The service provider then performs the intersection computation on these encrypted values without learning any information.

Datasets

Not discussed in the paper. The paper focuses on theoretical cryptographic protocols and their security properties, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Synergistic Use of Bloom Filters and HE: The paper demonstrates a powerful combination of Bloom filters for efficient set representation and homomorphic encryption for secure computation on encrypted data. This pairing is central to achieving both efficiency and privacy.
  • Client Set Certification for Malicious Security: Introducing a trusted third party to certify the client's set is a crucial step for achieving security against malicious adversaries. It effectively mitigates risks associated with false positives and client manipulation.
  • Outsourcing to Oblivious Cloud Providers: The ability to outsource PSI computation to an untrusted cloud service provider is a significant practical advancement. This makes PSI more scalable and accessible, especially for resource-constrained clients.
  • Novel HE Scheme for Outsourcing: The development of a new homomorphic encryption scheme that can handle the required multiplicative depth for the outsourced protocol is a notable contribution, potentially of independent interest.
  • Weakest Possible Assumptions: The protocol's security relies on the quadratic residuosity assumption, which is considered one of the weakest in cryptography, and avoids the need for random oracles.

Key Results

  • Malicious Model Security: The proposed MPSI (Malicious Private Set Intersection) protocol is proven secure in the standard model (without random oracles) against malicious adversaries, assuming the quadratic residuosity assumption.
  • Efficiency: The MPSI protocol achieves linear complexity (O(v+w)), which is optimal. The outsourced OPSI protocol has quadratic complexity (O(kw²)) but is still efficient for its purpose.
  • Client Set Size Independence: The protocol hides the client's set size from the server.
  • Outsourced PSI: The paper presents the first PSI protocol that can be outsourced to an oblivious service provider, enabling computation in cloud environments.
  • Reduced Constants: The protocol's constants are competitive with, and in some cases better than, existing linear-complexity protocols, especially when considering the avoidance of full-domain hash functions and random oracles.

Limitations and Future Work

  • Trusted Third Party for Certification: The MPSI protocol requires a trusted third party for client set certification. While this is a common approach for achieving malicious security, it introduces a point of trust.
  • Semi-Honest Security for Outsourcing: The outsourced PSI (OPSI) protocol is secure only in the semi-honest model for the service provider. Achieving malicious security for the provider would require verifiable computation, which is currently prohibitively expensive.
  • Communication Complexity: While efficient, the communication complexity of the MPSI protocol is higher than some protocols that only offer semi-honest security or rely on random oracles.
  • Future Work: The authors suggest exploring more efficient outsourced PSI protocols, potentially with malicious security for the service provider, and investigating further applications of their novel HE scheme. They also note that their protocol is beneficial for computationally weak clients.

Summary updated

BibTeX
@inproceedings{kerschbaum2012outsourced,
  author = {Florian Kerschbaum},
  title = {{Outsourced private set intersection using homomorphic encryption}},
  booktitle = {AsiaCCS},
  year = {2012},
  doi = {10.1145/2414456.2414506},
}
Figure