PSI Cardinality

The ability to measure overlap size without revealing identities unlocks critical business applications:

• Advertising Conversion Tracking: Measuring audience overlap between an advertiser's customer list and a publisher's audience without exposing user-level data.
• Contact Discovery Sizing: A messaging app can tell a user how many of their contacts are on the platform before revealing specific identities.
• Federated Analytics: Healthcare networks can measure patient cohort overlap across institutions for epidemiological studies without sharing patient records.

Modern PSI Cardinality protocols are built on efficient primitives:

• Oblivious Transfer (OT): Forms the basis for secure comparison operations.
• Cuckoo Hashing: Maps set elements into bins to reduce the number of required comparisons.
• Homomorphic Encryption (HE): Allows one party to compute the intersection size directly on encrypted data, often used in unbalanced settings where one set is much smaller.
• Diffie-Hellman (DH): Classical DH-based PSI can be adapted to reveal only cardinality by shuffling and masking the intersection.

PSI Cardinality protocols can be proven secure under different adversarial models:

• Semi-Honest Security: Assumes parties follow the protocol correctly but may try to infer additional information from the transcript. This is the most common and efficient model.
• Malicious Security: Protects against adversaries that arbitrarily deviate from the protocol. Achieved through zero-knowledge proofs or cut-and-choose techniques, at a higher computational cost.
• Leakage Profile: The protocol intentionally leaks the intersection size. A secure protocol ensures nothing beyond this cardinality is revealed.

PSI Cardinality is generally more efficient than full PSI because the final intersection elements do not need to be communicated or verified. Key performance metrics include:

• Communication Complexity: Often linear in the size of the smaller set, O(n), but with very small constants.
• Computational Overhead: Dominated by the number of OT or HE operations. Protocols using VOLE (Vector Oblivious Linear Evaluation) can process millions of items per second.
• Unbalanced Optimization: Highly efficient when one set is significantly smaller (e.g., a client's 1,000 contacts vs. a server's 100 million users).

While both reveal aggregate information, they serve distinct purposes:

• PSI Cardinality: Outputs the count of intersecting elements. |X ∩ Y|.
• PSI-Sum: Outputs the sum of associated values for the intersecting elements. For example, the total transaction value of shared customers.
• Labeled PSI Cardinality: A hybrid where one party learns the cardinality of the intersection for each label in a predefined set of categories, enabling segmented overlap analysis.

A direct extension of PSI Cardinality that reveals the sum of associated values for intersecting elements rather than just the count. While cardinality answers 'how many users overlap?', PSI-Sum answers 'what is the total transaction volume of overlapping users?'. This is critical for privacy-preserving aggregate analytics in finance and advertising where the intersection itself is sensitive but aggregate metrics are actionable.

The baseline threat model for most efficient PSI Cardinality protocols. Assumes parties follow the protocol correctly but may try to learn additional information from the transcript. In cardinality-only protocols, this is often sufficient because the output is a single integer, limiting what a passive adversary can infer. Contrasts with malicious security, which adds overhead to prevent active cheating.

A core building block for modern PSI Cardinality protocols. An OPRF allows a client to evaluate a pseudorandom function keyed by the server on its private input without the server learning the input. In cardinality protocols, OPRFs are used to hash both parties' sets into a common domain where the size of the intersection can be computed without revealing the elements themselves.

A PSI variant where only one party learns the output. In the context of cardinality, this often means the client learns the intersection size while the server learns nothing. This is the standard model for contact discovery applications: a user discovers how many of their contacts are on a platform without the platform learning the user's address book. Asymmetric cardinality is typically more efficient than symmetric variants.

A critical performance metric for PSI Cardinality protocols, measuring the total data exchanged between parties. Cardinality-only protocols can achieve significantly lower communication than full PSI because they transmit only a count rather than the entire intersection set. State-of-the-art protocols achieve communication that is linear only in the smaller set size, making them practical for highly unbalanced scenarios like mobile devices querying large server databases.

The stronger adversarial model where parties may arbitrarily deviate from the protocol to learn unauthorized information or corrupt the output. In PSI Cardinality, a malicious client might try to inflate the count, or a malicious server might attempt to learn which specific elements the client holds. Achieving malicious security in cardinality protocols typically requires zero-knowledge proofs or cut-and-choose techniques, adding computational overhead but providing the strongest practical guarantees.