Mutual Private Set Intersection with Linear Complexity

Myungsun Kim, Hyung Tae Lee, Jung Hee CheonIACR ePrint 2011 · DOI

TL;DR

This paper introduces a novel mutual private set intersection (mPSI) protocol that achieves linear computational complexity, a significant improvement over previous quadratic or quasi-linear methods. This is accomplished through a new "prime representation" technique that maps set elements to prime numbers, enabling more efficient computations within a semi-honest security model.

What Problem Does This Paper Address?

The core problem addressed is mutual private set intersection (mPSI). Imagine two parties, each with a private list of items (e.g., customer IDs, medical records). They want to find out which items are common to both lists (the intersection) without revealing any other items from their respective lists to each other. While "unilateral PSI" allows one party (the client) to learn the intersection while the other (the server) learns nothing, mPSI ensures both parties learn the intersection. Existing mPSI protocols, especially those secure against malicious adversaries, often suffer from high computational overhead, making them impractical for large datasets. This paper aims to significantly reduce this computational burden.

Methods

The paper's main innovation lies in its "prime representation" technique. Instead of representing set elements as roots of polynomials (a common approach in prior work), they map each element to a prime number. This mapping is done in two steps:

  1. Hash to an index: A hash function maps the input element to an index within a pre-defined table of primes.
  2. Map to a prime: The element is then mapped to a prime number from that table.

This prime representation allows for more efficient computations. The protocol then leverages additive homomorphic encryption (specifically, a threshold version of Paillier encryption) to perform computations on encrypted data. The core protocol involves each player computing an encrypted product of their mapped primes and then performing additive operations on these encrypted products. Finally, a threshold decryption reveals the combined result, which is then checked for divisibility by the square of the mapped prime to determine membership in the intersection. The authors also briefly discuss how to transform this semi-honest protocol into one secure against malicious adversaries using zero-knowledge proofs.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Prime Representation is Key: The fundamental insight is that representing set elements as primes, rather than polynomial roots, dramatically simplifies computations. This avoids the expensive polynomial multiplication and evaluation over encrypted data that plagued previous methods.
  • Linear Complexity Achieved: The paper demonstrates that by using prime representation and additive homomorphic encryption, an mPSI protocol can achieve linear computational complexity in the semi-honest model. This is a significant theoretical and practical advancement.
  • Trade-offs in Prime Mapping: The "map-to-prime" function needs to be deterministic and efficient. The paper discusses the challenges of probabilistic primality tests and the inefficiency of deterministic ones like AKS, opting for a table-based approach with hashing to buckets to manage these issues.
  • Conjecture for Malicious Security: The paper relies on a conjecture about the difficulty of solving a specific Diophantine equation to prove the privacy of their protocol in the semi-honest model. This highlights a common challenge in proving security for cryptographic protocols.

Key Results

  • Linear Computational Complexity: The proposed mPSI protocol achieves O(k) computational complexity, where k is the cardinality of the private sets. This is a substantial improvement over prior protocols that had O(k²) or O(k log² k) complexity.
  • Linear Communication Complexity: The protocol also maintains linear communication complexity, O(k).
  • Efficiency Comparison: Table 1 in the paper shows that their protocol is more efficient in terms of computation than previous prominent mPSI protocols [19, 11, 5, 7].

Limitations and Future Work

  • Semi-Honest Model Focus: The primary protocol presented is secure only in the semi-honest model. While the paper outlines a transformation to a malicious model using zero-knowledge proofs, it acknowledges that generic ZK proofs can be inefficient, potentially impacting the practical performance of the malicious version.
  • Malicious Protocol Details: A detailed description and formal security proof for the malicious mPSI protocol are left as future work.
  • Multiparty Setting: Extending the protocol to the multiparty setting is also identified as a direction for future research.
  • Conjecture Reliance: The privacy proof for the semi-honest protocol relies on a conjecture about the difficulty of solving a specific equation, which, if proven false, could weaken the privacy guarantees.

Summary updated

BibTeX
@article{kim2011mutual,
  author = {Myungsun Kim and Hyung Tae Lee and Jung Hee Cheon},
  title = {{Mutual Private Set Intersection with Linear Complexity}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2011},
  doi = {10.1007/978-3-642-27890-7\_18},
}
Figure