Private Set Intersection (PSI)

PSI protocols enforce one-sided output, where only the querying party learns the intersection result. The responding party receives no information about the querying party's set beyond what can be inferred from the intersection size.

• Sender Privacy: The responder's non-intersecting elements remain cryptographically hidden
• Receiver Privacy: The querying party's set elements outside the intersection are never revealed
• Prevents data leakage in clinical trial patient matching where only the sponsor should discover overlapping cohorts

PSI protocols balance communication complexity against computational overhead based on the underlying cryptographic primitive:

• Diffie-Hellman PSI: O(n) computation with minimal communication, ideal for small to medium sets
• Cuckoo Hashing + OPRF: Reduces asymptotic complexity to near-linear while handling sets of 2^20+ elements
• Fully Homomorphic PSI: Enables computation on encrypted sets but incurs 1000x+ computational overhead
• Modern labeled PSI extends intersection to retrieve associated metadata without additional leakage

Production PSI deployments in healthcare require security against active adversaries who may deviate from the protocol:

• Semi-honest security: Assumes parties follow the protocol but may try to learn additional information from transcripts
• Malicious security: Protects against arbitrary deviations using zero-knowledge proofs to enforce honest behavior
• Covert security: Detects cheating with a configurable probability, offering a practical middle ground
• Real-world genomic data matching requires malicious security to prevent input substitution attacks

PSI-Cardinality (PSI-CA) reveals only the size of the intersection, not the elements themselves. This weaker primitive is sufficient for many healthcare analytics use cases:

• Clinical trial feasibility: Determine how many patients match criteria across institutions without identifying them
• Epidemiological surveillance: Count overlapping disease cases between jurisdictions
• PSI-CA protocols are typically 10-100x faster than full PSI
• Can be combined with differential privacy to add calibrated noise to the intersection count

Delegated PSI offloads computation to untrusted cloud servers while preserving input privacy from the servers themselves:

• Clients encrypt their sets and send them to a semi-honest cloud that performs the intersection
• Relies on secret sharing or homomorphic encryption to keep inputs hidden from the delegate
• Enables resource-constrained medical devices to participate in PSI without heavy local computation
• Critical for cross-silo federated learning where hospitals lack dedicated cryptographic hardware

Standard Diffie-Hellman-based PSI protocols are vulnerable to Shor's algorithm on sufficiently large quantum computers. Post-quantum PSI constructions are emerging:

• Lattice-based OPRFs replace discrete log assumptions with Learning With Errors (LWE) hardness
• Oblivious Transfer from lattice assumptions enables quantum-secure PSI building blocks
• NIST PQC standardization drives adoption of Kyber and Dilithium primitives in PSI frameworks
• Healthcare data with multi-decade sensitivity mandates cryptographic agility for future quantum threats

A cryptographic primitive that allows computations to be performed directly on encrypted ciphertexts, producing an encrypted result that matches operations on plaintext. While PSI computes intersections, HE can be used to perform arbitrary analytics on the intersected data without decryption. In federated healthcare networks, HE often complements PSI to enable private computation on the matched cohort.

A mathematical framework that quantifies the privacy guarantee of a randomized algorithm. When combined with PSI, differential privacy ensures that the intersection output itself does not leak information about any single individual. Key parameters:

• Epsilon (ε): The privacy loss parameter; smaller values indicate stronger guarantees
• Privacy Budget: The total allowable privacy loss across multiple queries This prevents membership inference attacks on the intersected set.

A fundamental cryptographic protocol where a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious to which piece was transferred. OT serves as a core building block for many PSI protocols, particularly in OT-based PSI constructions. It enables efficient private matching without revealing non-matching elements to either party.

A space-efficient probabilistic data structure used to test whether an element is a member of a set. In PSI protocols, Garbled Bloom Filters enable efficient private set intersection by allowing parties to encode their sets in a way that supports oblivious querying. False positives are possible but can be cryptographically controlled, making them suitable for large-scale patient record matching.

A protocol in federated learning that computes the sum of model updates from multiple clients without revealing individual contributions. While distinct from PSI, secure aggregation shares the same privacy-preserving multi-party computation foundations. In healthcare federated learning, PSI can first identify overlapping patient cohorts across institutions, and secure aggregation then combines their model updates privately.