Communication Complexity

The absolute size of the input sets and the ratio between them is the primary driver of communication cost.

• Symmetric PSI: When sets are roughly equal, complexity often scales linearly with the combined set size, typically O(n + m).
• Unbalanced PSI: When one set is massive (server) and the other is small (client), protocols like Unbalanced PSI aim for complexity sublinear in the larger set, often O(small_set * log(large_set)).
• Real-world example: A contact discovery service with a 1B-user server set and a 500-contact client set requires highly asymmetric techniques to avoid transferring gigabytes of data.

Stronger adversarial defenses significantly inflate communication.

• Semi-Honest Security: Assumes parties follow the protocol. This is the baseline for efficiency and minimal communication.
• Malicious Security: Defends against arbitrary deviations. This requires zero-knowledge proofs or cut-and-choose techniques, often multiplying communication by a factor of 2x to 10x compared to semi-honest protocols.
• Trade-off: A protocol secure against active adversaries must transmit cryptographic consistency checks that are absent in the passive model.

The choice of building blocks dictates the constant factors in communication complexity.

• Diffie-Hellman (DH): Classical DH-based PSI transmits a number of group elements proportional to the set size. Elliptic Curve Diffie-Hellman (ECDH) reduces this to ~256 bits per element.
• OT Extension (IKNP/KKRT): Modern protocols use Oblivious Transfer Extension to minimize public-key operations. They transmit a large number of symmetric ciphertexts, achieving very low amortized cost per item.
• Vector OLE (VOLE): The latest generation (e.g., Ferret) uses VOLE to achieve the lowest communication constants, often just a few bits per element for the core comparison.

How sets are encoded before the protocol drastically changes the data volume.

• Bloom Filters: A probabilistic structure that compresses sets but introduces a false-positive rate. Communication is linear in the filter size, but the receiver must filter out spurious matches.
• Cuckoo Hashing: A dense hashing scheme that maps elements to a table without collisions. It allows protocols to operate only on a fraction of the table, reducing the number of comparisons and transmitted data.
• Bit Vectors: Simple but inefficient for large domains; transmitting a raw bit vector is linear in the domain size, making it impractical for large ID spaces.

The number of sequential back-and-forth interactions directly impacts wall-clock time, especially in high-latency networks.

• Non-Blocking: Protocols with constant round complexity (e.g., 2-3 rounds) are preferred for WAN deployments.
• Pipelining: Some protocols allow streaming data without waiting for full completion, hiding latency.
• FHE-Based PSI: Fully Homomorphic Encryption can achieve 1 round of interaction, but at the cost of massive ciphertext expansion, often trading latency for total bandwidth.

What the protocol reveals determines the minimum necessary communication.

• Full Intersection: Revealing all matching elements requires transmitting the actual identifiers, adding O(intersection_size) overhead.
• PSI Cardinality: Revealing only the count of matches eliminates this final transmission step, reducing communication to the absolute minimum required for the comparison logic.
• Labeled PSI: If associated data (labels) must be retrieved for matches, communication increases linearly with the intersection size multiplied by the label length.

A foundational technique that dramatically reduces the communication complexity of PSI protocols. Instead of performing expensive asymmetric cryptography for every comparison, OT extension uses a small number of base OTs to bootstrap a large number of efficient symmetric-key transfers. The IKNP protocol is the classic construction, enabling modern PSI to scale to billion-element sets without prohibitive bandwidth costs.

A hashing scheme critical for optimizing communication vs. computation trade-offs. By mapping elements into bins using multiple hash functions, Cuckoo hashing ensures each bin holds at most one element. This allows protocols to pack data structures tightly, reducing the total bits that must be exchanged. It is a core component of the KKRT protocol, enabling compact OT-based private set intersection.

A space-efficient probabilistic data structure that trades false-positive rate for communication savings. In PSI, one party can encode their entire set into a Bloom filter and send it to the other party, who tests their elements locally. While this reduces rounds, the filter size and the false-positive rate must be carefully calibrated against the security parameter to avoid leaking information about non-intersecting elements.

A powerful primitive that generates long vectors of correlated randomness with minimal communication. VOLE-based PSI protocols, such as those using Ferret OT, achieve the lowest amortized communication costs. The setup phase is independent of the input sets, allowing for a highly efficient online phase where the data exchanged is proportional only to the set sizes, not the security parameter.

A protocol variant explicitly designed for scenarios with asymmetric set sizes (e.g., a client with 1,000 contacts and a server with 1 billion users). Standard PSI would require communication linear in the larger set. Unbalanced protocols use techniques like fully homomorphic encryption (FHE) or specialized OT structures to ensure the communication complexity is linear only in the size of the smaller client set, saving enormous bandwidth.

The security model directly impacts communication overhead. Semi-honest security assumes parties follow the protocol, allowing for leaner, faster communication. Malicious security requires the protocol to defend against arbitrary deviations, which necessitates additional zero-knowledge proofs or MACs. This extra cryptographic machinery can increase the total data exchanged by a significant constant factor to achieve robustness against active adversaries.