Private Set Intersection (PSI)

The fundamental property ensuring that only the intersection is revealed. Neither party learns anything about the other's non-intersecting elements.

• Zero-knowledge leakage: The protocol reveals no more information than the intersection itself.
• Input privacy: Alice learns nothing about Bob's exclusive items, and vice versa.
• Real-world example: Two factories can identify shared defective component batches without exposing their proprietary yield data or supplier lists.

Modern PSI protocols have evolved from slow, heavy cryptographic operations to highly optimized constructions capable of handling billion-element sets.

• Oblivious Transfer (OT) extension: Dramatically reduces the number of expensive public-key operations.
• Cuckoo hashing: Minimizes the computational overhead of comparing large datasets.
• Performance benchmark: State-of-the-art protocols can intersect sets of 1 million items in under 2 seconds on standard hardware.

Protocols hardened against adversaries who actively deviate from the specification to steal information.

• Input consistency checks: Verifies that a party's input set is well-defined and not adaptively chosen based on the protocol's progress.
• Cut-and-choose techniques: Forces a malicious party to prove correct behavior by opening a random subset of their cryptographic commitments.
• Use case: Essential for competitive manufacturing audits where a participant might attempt to probe for specific proprietary formulations.

Architectures that offload the heavy computation to untrusted cloud servers without granting them access to the plaintext data or the final intersection result.

• Two-server model: Data is secret-shared across two non-colluding servers that perform the intersection computation.
• Client delegation: A resource-constrained factory-floor edge device can outsource the PSI computation to powerful servers.
• Key benefit: Enables real-time federated analytics across factory fleets without requiring each plant to maintain high-performance cryptographic hardware.

Variants that reveal only aggregate statistics rather than the explicit intersection set, providing an additional layer of data protection.

• Cardinality-only PSI: Reveals only the size of the overlap, not the identities of the common elements.
• Threshold PSI: Outputs the intersection only if the overlap size exceeds a pre-agreed threshold t.
• Application: A consortium of manufacturers can verify if a critical safety issue affects more than a threshold percentage of their combined fleet before sharing specific incident details.

Optimized protocols for scenarios where one party's dataset is significantly smaller than the other's, a common situation in enterprise data sharing.

• Asymmetric computation: The party with the smaller set performs proportionally less work.
• Communication complexity: Scales linearly with the size of the smaller set, not the larger one.
• Practical scenario: A small component supplier (10k records) can efficiently check for overlap with a global manufacturer's massive defect database (100M records) without the manufacturer exposing its full list.

The broader cryptographic field from which PSI emerges. SMPC allows multiple parties to jointly compute a function over their private inputs while keeping those inputs secret. In the context of PSI, the computed function is the set intersection itself. Protocols rely on techniques like garbled circuits and secret sharing to ensure that no party learns anything beyond the final intersection result. This is the foundational paradigm that makes collaborative analytics across competing factories possible without exposing proprietary production data.

A fundamental cryptographic building block frequently used to construct efficient PSI protocols. In an Oblivious Transfer, a sender transmits multiple messages to a receiver, but the receiver only learns one of them, and the sender remains oblivious to which message was selected. PSI protocols often use OT extension techniques to efficiently perform millions of these transfers, enabling the comparison of large datasets without revealing non-matching elements. This primitive is critical for scaling PSI to industrial fleet data volumes.

A cryptographic scheme that enables computation directly on ciphertexts. In PSI, Fully Homomorphic Encryption (FHE) or Somewhat Homomorphic Encryption (SHE) allows one party to encrypt their dataset and send it to another, who can then compute the intersection homomorphically without ever decrypting the data. The result, when decrypted, reveals only the common elements. This approach offers strong security guarantees but incurs significant computational overhead compared to OT-based methods.

A mathematical framework that provides a provable guarantee against the leakage of individual records. When combined with PSI, Differential Privacy adds calibrated noise to the intersection output or to intermediate computations. This prevents an adversary from inferring whether a specific element was in the other party's set based on the result. For factory fleets, this ensures that even the intersection cardinality or specific common defect patterns do not inadvertently reveal a single factory's proprietary operational data.

A space-efficient probabilistic data structure used in many practical PSI implementations. A Bloom Filter represents a set as a compact bit array, allowing fast membership queries with a controllable false-positive rate. In PSI, parties can exchange encrypted or hashed Bloom Filters to compute approximate intersections. While efficient, this approach requires careful analysis of the false-positive probability to ensure that no unintended information about non-matching elements is leaked through collisions.

A closely related protocol that computes the sum of private vectors from multiple clients without revealing individual contributions. In federated learning for factory fleets, Secure Aggregation is often paired with PSI to first identify common feature spaces across sites and then securely aggregate model updates. While PSI discovers the overlap, secure aggregation ensures that the central server cannot inspect any single factory's gradient update, creating a comprehensive privacy-preserving machine learning pipeline.