Private Set Intersection Cardinality (PSI-CA)

The foundational protocol from which PSI-CA is derived. While PSI-CA reveals only the intersection size, full PSI allows two parties to learn the actual elements in the intersection of their private sets without disclosing non-matching items.

• Key distinction: PSI reveals what is common; PSI-CA reveals only how many are common
• Common implementations use Diffie-Hellman key exchange, oblivious transfer, or homomorphic encryption
• Essential for contact discovery, password monitoring, and private record linkage

A preprocessing step that partitions encoded datasets into mutually exclusive blocks to reduce the quadratic computational complexity of record linkage. PSI-CA is often used as a blocking key selection mechanism to estimate overlap between candidate blocking strategies without revealing plaintext.

• Uses techniques like Locality-Sensitive Hashing (LSH) and reference value encoding
• PSI-CA helps evaluate blocking quality by measuring the cardinality of intersection per block
• Critical for scaling PPRL to datasets with millions of records

The cryptographic framework that enables multiple parties to jointly compute a function over their private inputs while keeping those inputs secret. PSI-CA is a specific SMPC functionality optimized for the set intersection cardinality problem.

• Garbled circuits and secret sharing are common SMPC building blocks
• PSI-CA protocols can be extended to multi-party settings for consortium-based linkage
• Provides formal security guarantees under the semi-honest or malicious adversary models

A probabilistic data structure that encodes sensitive identifiers into a fixed-length bit array using multiple hash functions. PSI-CA can operate directly on Bloom filter representations to estimate set intersection size without decrypting the underlying tokens.

• Hardened Bloom filters add cryptographic salts to resist frequency-based attacks
• PSI-CA over Bloom filters enables approximate cardinality estimation with tunable false positive rates
• Forms the basis for the Cryptographic Longterm Key (CLK) encoding scheme used in PPRL

Encryption schemes that allow computation directly on ciphertexts, enabling PSI-CA protocols where one party encrypts their set and the other performs intersection operations without ever decrypting. Fully Homomorphic Encryption (FHE) supports arbitrary computation, while Partially Homomorphic Encryption (PHE) is optimized for specific operations.

• Paillier cryptosystem enables additive operations used in polynomial-based PSI-CA
• Eliminates the need for interactive rounds in some protocol designs
• Computationally intensive but provides strong semantic security guarantees

A fundamental cryptographic primitive where a sender transmits one of many pieces of information to a receiver, but remains oblivious to which piece was selected. OT serves as a core building block for many efficient PSI-CA protocol implementations.

• OT extension techniques dramatically reduce the computational overhead for large sets
• Forms the basis for OT-based PSI protocols that scale to billion-element sets
• Provides unconditional security for the receiver's choice in the ideal model