Private Set Intersection (PSI)

The fundamental guarantee that the protocol outputs the exact intersection of the input sets. A correct PSI protocol ensures that every element in the output is genuinely present in both parties' inputs (soundness), and every element present in both inputs appears in the output (completeness).

• Perfect correctness: The intersection is computed without any error probability
• Statistical correctness: A negligible probability of error exists, typically bounded by a security parameter (e.g., 2^-40)
• Failure modes include hash collisions in Bloom filter-based constructions or decryption failures in lattice-based schemes

The strongest adversarial model where a corrupt party may arbitrarily deviate from the protocol specification to learn the other party's private inputs. Protocols secure in this model must enforce honest behavior through cryptographic mechanisms.

• Input consistency checks: Verifying that a party's input set is well-formed and consistent across all protocol rounds
• Cut-and-choose techniques: Used in garbled circuit-based PSI to detect cheating with high probability
• Zero-knowledge proofs: Attached to each protocol message to prove correct computation without revealing secrets
• Protocols like PSI from Oblivious Pseudorandom Functions (OPRF) can be upgraded to malicious security with relatively low overhead compared to semi-honest variants

Also known as honest-but-curious, this model assumes all parties follow the protocol exactly but may attempt to infer additional information from the messages they receive. It is the baseline security guarantee for most efficient PSI constructions.

• Adversaries do not deviate from the protocol specification
• Protects against passive observation and traffic analysis
• Significantly more efficient than malicious-secure protocols due to the absence of heavy zero-knowledge proofs
• Suitable for environments where participants are trusted to execute correctly but data must remain confidential, such as inter-departmental analytics within a single organization

The total amount of data exchanged between parties during protocol execution, measured in bits or bytes. This is often the bottleneck in wide-area network deployments and directly impacts latency.

• Linear complexity O(n): Grows proportionally with set size; achieved by modern OPRF-based protocols
• Sublinear complexity: Achieved by protocols using fully homomorphic encryption or polynomial representations, but with higher computational cost
• Asymmetric communication: Some protocols minimize sender-to-receiver bandwidth at the expense of the reverse direction, useful for mobile clients
• Real-world benchmarks: KKRT16 protocol achieves approximately 0.5 MB of communication per 1,000 elements at the 128-bit security level

The processing overhead required by each party, typically dominated by public-key cryptographic operations such as exponentiations, elliptic curve scalar multiplications, or homomorphic encryption evaluations.

• Oblivious Pseudorandom Function (OPRF) evaluation is the dominant cost in modern PSI protocols, requiring one oblivious transfer per input element
• Asymmetric computation: Protocols can be designed to shift the computational burden to the larger or more powerful party
• Preprocessing models: Heavy cryptographic operations can be performed offline before the inputs are known, dramatically reducing online phase latency
• Hardware acceleration via AES-NI and vectorized elliptic curve operations can reduce computation time by an order of magnitude

A privacy property beyond basic PSI that conceals the cardinality of each party's input set. Without this guarantee, the protocol reveals the size of the intersection, which can leak sensitive information about the underlying data.

• Standard PSI reveals the intersection size to at least one party by default
• Fully size-hiding PSI: Hides both input set sizes from the other party, often achieved through padding to an upper bound
• Differential privacy integration: Adding calibrated noise to the intersection size to provide formal privacy guarantees
• Critical in applications where set size itself is sensitive, such as contact tracing where the number of contacts reveals social activity patterns

A fundamental cryptographic primitive where a sender transmits one of potentially many pieces of information to a receiver, but remains oblivious to which piece was selected. PSI protocols, particularly those based on Oblivious Transfer Extension, use OT as a core building block to efficiently compare encoded set elements without revealing non-matching items. Modern OT extension techniques dramatically reduce the reliance on expensive public-key operations, making PSI practical for large datasets.

A cryptographic protocol, introduced by Andrew Yao, that enables two parties to jointly evaluate a boolean circuit over their private inputs without revealing those inputs to each other. In the context of PSI, garbled circuits can be used to compute the intersection function itself, especially in circuit-based PSI protocols. The Free-XOR optimization is critical here, allowing XOR gates to be evaluated without cryptographic operations, significantly reducing the computational overhead of comparing hashed set elements.

A cryptographic scheme that allows computation directly on encrypted data, enabling private inference and training without exposing raw inputs. In PSI, Somewhat Homomorphic Encryption (SHE) or Fully Homomorphic Encryption (FHE) can be used to evaluate a polynomial representing a client's set on a server's encrypted set. This allows the server to compute the intersection without learning the client's elements, and the client decrypts only the matching results. HE-based PSI often features low communication but higher computation.

A hashing algorithm that resolves collisions by relocating existing keys to alternative positions using two or more hash functions. In PSI, Cuckoo Hashing is a critical optimization technique used to pack set elements into a dense table structure. This allows protocols to perform batch-wise comparisons and reduces the number of expensive cryptographic operations. The technique ensures that each bin contains at most one element with high probability, enabling constant-time lookups during the private comparison phase.

A space-efficient probabilistic data structure used to test whether an element is a member of a set. In PSI, Bloom Filters can encode one party's set, allowing the other party to query for membership privately. However, standard Bloom Filters leak information through false positives. Garbled Bloom Filters (GBF) address this by using garbled circuit techniques to create a filter that reveals nothing during a query unless the item is in the intersection, forming the basis of efficient, semi-honest PSI protocols.

A mathematical framework that provides provable privacy guarantees by injecting calibrated noise into computation outputs. When combined with PSI, Differentially Private PSI ensures that the size of the intersection or the elements themselves do not leak information about individual records. This is crucial when the intersection result itself is sensitive, such as in genomic cohort discovery or contact tracing, where revealing that two parties share a specific data point could constitute a privacy breach.