Diffie-Hellman Key Exchange

The core innovation of Diffie-Hellman is that it allows two parties to agree on a shared secret while communicating exclusively over a public, insecure channel. An eavesdropper observing all exchanged messages—the public keys—cannot feasibly compute the shared secret. This relies on the computational hardness of the discrete logarithm problem: given g^a mod p, finding a is infeasible for sufficiently large prime p and generator g.

The security of standard Diffie-Hellman rests on the Decisional Diffie-Hellman (DDH) assumption. This states that given g^a and g^b, the resulting shared secret g^{ab} is computationally indistinguishable from a random group element. This property is critical for PSI protocols, as it ensures that the encrypted representations of set elements reveal no information about the underlying items to a party that does not hold the corresponding private key.

Each party generates an ephemeral key pair for a given protocol session:

• Private key: A randomly selected integer a kept strictly secret.
• Public key: The value g^a mod p, which is transmitted openly. The security guarantee holds only if the private key remains confidential and a fresh key pair is generated for each session. Reusing private keys across multiple protocol runs can create vulnerabilities to replay and correlation attacks.

Elliptic Curve Diffie-Hellman (ECDH) provides equivalent security to classical DH but with significantly smaller key sizes. A 256-bit ECDH key offers security comparable to a 3072-bit classical DH key. This efficiency makes ECDH the preferred choice for modern DH-based PSI protocols, reducing both communication complexity and computational overhead. The underlying assumption shifts from the standard discrete logarithm to the Elliptic Curve Discrete Logarithm Problem (ECDLP).

In DH-based PSI protocols, each party hashes their set elements and then exponentiates them with their private key. The doubly-exponentiated values are compared to find the intersection:

• Party A sends H(x)^a for each element x.
• Party B sends H(y)^b for each element y and also computes (H(x)^a)^b.
• The intersection is revealed where the doubly-exponentiated values match. This works because exponentiation is commutative: (H(x)^a)^b = (H(x)^b)^a.

The basic DH-based PSI protocol is secure only in the semi-honest model, where parties follow the protocol correctly but may try to learn additional information. It is vulnerable to malicious adversaries who could send malformed public keys to probe the other party's set. Achieving malicious security requires additional cryptographic machinery, such as zero-knowledge proofs of correct exponentiation. DH-based PSI also does not provide post-quantum security, as Shor's algorithm can efficiently solve the discrete logarithm problem on a sufficiently large quantum computer.

A variant of the Diffie-Hellman protocol using elliptic curve cryptography to provide equivalent security with significantly smaller key sizes. In PSI, ECDH enables efficient exponentiation-based protocols where parties hash their set elements to curve points and perform private key operations. The computational Diffie-Hellman assumption on elliptic curves ensures that an adversary cannot derive the shared secret from public transcripts. Modern implementations like X25519 offer fast, constant-time operations resistant to timing side channels.

A protocol where a client learns the output of a pseudorandom function keyed by a server on the client's input, without the server learning the input or the client learning the server's key. DH-based OPRFs are constructed by having the server hold a secret exponent and the client blind their input before sending it. The server applies the exponent and returns the result, which the client unblinds to obtain PRF(k, x). OPRFs are the core building block of many modern PSI protocols, including the KKRT protocol.

A cryptographic security model that assumes all parties follow the protocol specification correctly but may attempt to learn additional information from the transcript. Classical DH-based PSI protocols typically achieve semi-honest security, offering a favorable efficiency-security trade-off. Under this model, the protocol guarantees that no party can distinguish the real execution from an ideal one where a trusted third party computes the intersection. For stronger guarantees, protocols can be upgraded to malicious security using zero-knowledge proofs or cut-and-choose techniques.

A variant of private set intersection where only one party learns the intersection result while the other party learns nothing. This is the natural model for client-server contact discovery, where a messaging app user wants to find which contacts are registered without revealing their entire address book. DH-based asymmetric PSI is straightforward: the client sends blinded elements, the server exponentiates and returns them, and the client unblinds and compares. The server's set remains entirely private throughout the exchange.

A measure of the total amount of data exchanged between parties during protocol execution, critical for PSI in bandwidth-constrained environments. DH-based PSI protocols have communication linear in the size of the smaller set, typically requiring O(n) group elements where n is the set size. Each element is a curve point or large integer. Optimizations like Cuckoo hashing reduce the effective set size, while OT extension and VOLE-based protocols can achieve sublinear or even constant communication in newer constructions.

Private set intersection protocols designed to remain secure against adversaries equipped with large-scale quantum computers. Classical DH-based PSI relies on the discrete logarithm problem, which is efficiently solvable by Shor's algorithm on a sufficiently powerful quantum computer. Post-quantum alternatives replace DH with lattice-based assumptions like Learning With Errors (LWE) or code-based cryptography. These constructions often use homomorphic encryption or oblivious transfer as their foundation rather than exponentiation, fundamentally changing the protocol structure.