Private Set Intersection

Secure Multi-Party Computation (MPC) is the foundational cryptographic framework that enables PSI. MPC allows multiple parties to jointly compute a function over their private inputs while revealing only the output of the function. PSI is a specific, widely-used MPC protocol. Key characteristics include:

• General-Purpose: Can compute any function, not just set intersections.
• Input Privacy: No party learns anything about another's input beyond what is logically revealed by the output.
• Cryptographic Guarantees: Security is proven under formal models, assuming certain computational limitations of adversaries.

Homomorphic Encryption (HE) is a form of encryption that allows computations to be performed directly on ciphertext. When the result is decrypted, it matches the result of the same operations performed on the plaintext. Its relationship to PSI includes:

• Alternative Approach: Some PSI protocols use HE as a building block, allowing one party to encrypt their set so another can compute the intersection without decrypting it.
• Broader Application: Enables encrypted inference, where a model can make predictions on encrypted client data, and encrypted vector search for privacy-preserving RAG.
• Computational Overhead: Fully homomorphic encryption is computationally intensive, leading to hybrid protocols that balance performance and security.

Private Information Retrieval (PIR) is a protocol that allows a client to retrieve an item from a database without the server learning which item was requested. It complements PSI in privacy-preserving data access scenarios:

• Query Privacy vs. Data Privacy: PIR protects the client's query; PSI protects the data contents of all parties.
• Use Case Synergy: A system might use PSI for a private 'filtering' step (e.g., find common customer IDs) and then use PIR for the client to privately fetch the detailed records associated with those IDs from the server's database.
• Efficiency Trade-offs: Information-theoretic PIR requires replicating the database, while computational PIR uses cryptographic techniques like HE.

Federated Learning (FL) is a decentralized machine learning paradigm where a global model is trained across multiple devices or data silos. Clients compute model updates on local data and share only these updates, not the raw data. Its connection to PSI is operational:

• Secure Aggregation: A critical step in FL where the server sums model updates from clients without inspecting individual contributions. PSI protocols can be adapted for this.
• Cohort Discovery: Before federated training on a specific population (e.g., patients with a rare condition), PSI can be used to privately identify the set of clients whose local datasets contain relevant records, without revealing the condition.
• Privacy Stack: FL is often combined with differential privacy and secure aggregation (using MPC/PSI techniques) for a multi-layered defense.

Differential Privacy (DP) is a rigorous mathematical framework that quantifies and bounds privacy loss. It guarantees that the inclusion or exclusion of any single individual's data has a negligible effect on the output of an analysis. It relates to PSI as a complementary, statistical approach:

• Different Guarantee: DP protects against inference attacks on individuals in a released output (e.g., a statistic or model). PSI protects the input datasets during a joint computation.
• Synergistic Use: The result of a PSI protocol (e.g., the size of the intersection) can be further protected by adding DP noise before release.
• Local DP: A variant where data is randomized on the user's device before collection, providing a strong trust model similar to some PSI scenarios.

A Trusted Execution Environment (TEE), such as Intel SGX or AMD SEV, is a hardware-based secure area within a main processor. Code and data inside a TEE are protected with confidentiality and integrity, even from the host operating system. It offers an alternative architectural approach to cryptographic protocols like PSI:

• Performance Advantage: Computations run at near-native speed, unlike cryptographic protocols which can be orders of magnitude slower.
• Trust Model Shift: Security relies on the hardware manufacturer's attestation and the integrity of the TEE implementation, rather than purely mathematical cryptographic assumptions.
• Use in PSI/MPC: TEEs can be used to run a neutral, trusted 'coordinator' for an MPC protocol, simplifying design, or to execute entire PSI logic on encrypted data provided by the parties.