Labeled PSI

In a Labeled PSI protocol, the Sender holds a set of elements with associated labels, while the Receiver holds a query set. The Receiver learns only the labels for elements in the intersection, while the Sender learns nothing about the Receiver's set. This asymmetry is critical for applications like private contact discovery with profile data or secure database lookup where one party owns the enriched dataset.

Many efficient Labeled PSI protocols are built on Oblivious Pseudorandom Functions (OPRFs). The Sender holds a PRF key and the Receiver evaluates the PRF on their inputs without learning the key. For intersecting elements, both parties derive the same PRF output, which is then used to encrypt the associated label. This ensures that labels for non-intersecting elements remain indistinguishable from random noise.

Once the intersection is identified through the OPRF or a similar primitive, labels are protected using symmetric encryption derived from the PRF output. Common approaches include:

• One-time pad XOR with a hash of the PRF output
• AES-GCM encryption keyed by the PRF result This ensures that only the party who can compute the correct PRF output for an intersecting element can decrypt the corresponding label.

Labeled PSI protocols can be upgraded from semi-honest security to malicious security using techniques like cut-and-choose, zero-knowledge proofs, or authenticated data structures. In the malicious model, the protocol guarantees correctness even if one party deviates arbitrarily from the specification—preventing a malicious Sender from returning incorrect labels or a malicious Receiver from learning labels for non-intersecting elements.

Labeled PSI is the cryptographic foundation for private database query systems where a client queries a server's database by a key without revealing the key to the server, and the server returns only the matching record without disclosing the rest of the database. Real-world use cases include:

• Private contact discovery with profile information
• Secure password breach checking where the service returns breach metadata only for compromised credentials
• Confidential genomic matching where labels represent phenotypic data

Modern Labeled PSI protocols achieve near-linear communication complexity in the size of the Receiver's set, independent of the Sender's total dataset size. Techniques include:

• Cuckoo hashing to reduce the number of OPRF evaluations
• Batching multiple OPRF evaluations into a single multi-point OPRF
• Compressed label delivery using vector OLE (VOLE) to transmit labels with minimal overhead These optimizations make Labeled PSI practical for datasets containing billions of records.

A foundational building block where a client evaluates a pseudorandom function (PRF) keyed by a server on the client's private input. The client learns the PRF output, but the server learns nothing about the input, and the client learns nothing about the server's key. In labeled PSI, OPRFs are used to privately mask set elements before performing the intersection, ensuring that the labels can only be decrypted by the party holding the corresponding masked value.

A cryptographic primitive where a sender inputs two messages and a receiver inputs a choice bit. The receiver learns only their chosen message, and the sender learns nothing about the choice. OT serves as the atomic operation for secure computation. In labeled PSI protocols, OT is often used to transmit encrypted labels corresponding to intersecting elements without revealing which labels were selected to the sender.

A PSI variant where only one party—typically the client—learns the intersection result, while the other party learns nothing. This directly mirrors the labeled PSI use case: a client with a query set learns only the labels associated with the intersection, while the server holding the labeled database receives no output. Contact discovery in messaging apps is a canonical real-world example.

A private set intersection variant that reveals only the aggregate sum of values associated with intersecting elements, rather than the elements themselves. Labeled PSI generalizes this concept: instead of a single aggregate, the client learns the individual labels for each element in the intersection. PSI-Sum is useful for private analytics, such as computing total revenue from overlapping customer segments without exposing individual transactions.

The process of matching records referring to the same real-world entity across disparate databases without revealing non-matching identities. Labeled PSI enables a powerful variant: one party can enrich their records with attributes from another party's database only for the matched entities. This is critical in healthcare for linking patient records across institutions while maintaining HIPAA compliance.

A highly efficient semi-honest PSI protocol by Kolesnikov, Kumaresan, Rosulek, and Trieu that uses OT extension and Cuckoo hashing to achieve fast, low-communication private set intersection. The KKRT construction forms the performance baseline against which modern labeled PSI protocols are measured. It demonstrates how OT-based techniques can scale to sets containing millions of elements.