Multiparty PSI

The primary security upgrade from two-party to multiparty PSI is the ability to withstand collusion attacks. A robust protocol ensures that even if a subset of parties (up to a defined threshold) secretly shares their private inputs and protocol transcripts, they cannot learn the honest parties' exclusive elements. This is formalized as security in the malicious majority or dishonest majority setting, often relying on secret-sharing schemes rather than simple Diffie-Hellman key exchange.

Multiparty PSI protocols are categorized by their communication structure:

• Star Topology: A central leader coordinates the computation. All parties send encrypted or secret-shared data to the leader, who computes the intersection. This is efficient but often relies on the leader being non-colluding.
• Fully Connected Mesh: All parties communicate directly with every other party. This eliminates the single point of trust but incurs quadratic communication complexity (O(n²)), which can become a bottleneck for large groups.

To avoid a single party learning the output first, many protocols represent the intersection as a secret-shared value. The final result is split into random-looking shares distributed across all parties. Only when a threshold of parties recombines their shares is the intersection revealed. This prevents an early-exiting malicious party from gaining an information advantage and is a standard technique in protocols achieving guaranteed output delivery.

Naive multiparty PSI requires comparing every element of every party's set, leading to O(n²) communication. Modern optimized protocols, such as those based on Oblivious Programmable PRF (OPPRF) or multi-key Fully Homomorphic Encryption (FHE), reduce this to linear overhead O(n). They allow a single party to broadcast a single encrypted query that is evaluated sequentially by all others, dramatically improving scalability for large datasets.

In adversarial environments, a protocol must guarantee fairness. Threshold output delivery ensures that the adversary learns the intersection result if and only if all honest parties also receive it. This prevents a malicious actor from aborting the protocol after learning the output but before others do. Achieving this typically requires a broadcast channel and consensus on a commitment to the final output before decryption.

A cutting-edge approach uses Multi-Key Fully Homomorphic Encryption (MK-FHE). Each party encrypts its data under its own unique public key. The protocol homomorphically evaluates the intersection circuit on the combined ciphertexts, producing a ciphertext that can only be decrypted by a joint decryption protocol involving all parties. This minimizes round complexity but currently incurs high computational cost.

A foundational two-party cryptographic primitive where a sender inputs two messages and a receiver inputs a choice bit. The receiver learns only the chosen message, and the sender learns nothing about the choice. In multiparty PSI, OT serves as the core building block for secure comparison gates and is massively extended using OT extension techniques to handle large-scale set operations efficiently.

A security model where all parties are assumed to follow the protocol specification correctly but may attempt to learn additional information from the protocol transcript. Most high-performance multiparty PSI protocols target this model first, as it allows for significantly lower communication and computation overhead compared to malicious security. Suitable for collaborative analytics between trusted but curious institutional partners.

The strongest practical security guarantee, where an adversary may arbitrarily deviate from the protocol—sending malformed messages, aborting early, or injecting false data. Multiparty PSI with malicious security uses zero-knowledge proofs and consistency checks to ensure correctness and privacy even against active attackers. Essential for adversarial settings like financial fraud detection across competing institutions.

A privacy-preserving variant that reveals only the size of the intersection across multiple parties, not the intersecting elements themselves. Useful for aggregate analytics where knowing how many users overlap across platforms is sufficient without identifying which users. Dramatically reduces information leakage compared to full PSI while still enabling valuable cross-organizational metrics.

Extends private set intersection to identify approximate matches rather than exact equality. Uses techniques like locality-sensitive hashing and edit distance metrics to match similar strings, biometric templates, or noisy sensor readings across multiple parties. Critical for applications like private contact discovery with typo tolerance or cross-institutional patient record linkage with inconsistent formatting.

Multiparty PSI protocols designed to resist adversaries with large-scale quantum computers. Traditional DH-based and some OT-based constructions rely on discrete logarithm or factoring assumptions vulnerable to Shor's algorithm. Post-quantum variants use lattice-based cryptography, code-based assumptions, or supersingular isogenies to ensure long-term security for sensitive multi-party computations.