Elliptic Curve Diffie-Hellman (ECDH)

ECDH achieves the same security level as traditional finite-field Diffie-Hellman with dramatically smaller key sizes. A 256-bit ECDH key provides security comparable to a 3072-bit RSA key.

• 128-bit security: 256-bit ECDH vs. 3072-bit DH
• 256-bit security: 512-bit ECDH vs. 15360-bit DH
• Reduces bandwidth and storage overhead in PSI protocols
• Critical for mobile and IoT applications with constrained resources

ECDH operates over the elliptic curve discrete logarithm problem (ECDLP) rather than modular exponentiation. The protocol uses scalar multiplication of a public base point on a standardized curve like Curve25519 or secp256k1.

• Alice generates private key a and public key aG
• Bob generates private key b and public key bG
• Shared secret: a(bG) = b(aG) = abG
• ECDLP makes recovering a from aG computationally infeasible

ECDH serves as the foundational primitive for many classical Private Set Intersection protocols. In DH-PSI, each party hashes their set elements and exponentiates them with their private key, enabling intersection discovery without revealing non-matching elements.

• Enables semi-honest secure PSI constructions
• Used in contact discovery applications (e.g., Signal, WhatsApp)
• Pairs with Cuckoo Hashing for efficient set representation
• Forms the basis for asymmetric PSI where only one party learns the result

ECDH supports perfect forward secrecy (PFS) when ephemeral key pairs are generated for each session. Even if a long-term private key is compromised, past session keys remain secure because the ephemeral private keys are discarded after use.

• Ephemeral ECDH (ECDHE) generates fresh keys per session
• Prevents retrospective decryption of captured traffic
• Essential for secure messaging and TLS 1.3 handshakes
• Adds minimal computational overhead due to fast ECC operations

ECDH implementations rely on standardized, well-vetted elliptic curves to ensure security and cross-platform compatibility. Widely adopted curves include:

• Curve25519 (X25519): Designed for high-speed, constant-time ECDH
• NIST P-256 (secp256r1): FIPS 186-4 compliant, widely used in government
• secp256k1: Used in Bitcoin and blockchain applications
• Curve448 (X448): Higher security margin for long-term protection

Standardization ensures consistent behavior across libraries like OpenSSL, libsodium, and Bouncy Castle.

ECDH is not post-quantum secure. Shor's algorithm running on a sufficiently powerful quantum computer can efficiently solve the ECDLP, breaking the protocol entirely.

• Both ECDH and finite-field DH are vulnerable to quantum attacks
• Migration to post-quantum key exchange (e.g., Kyber) is underway
• NIST is standardizing quantum-resistant alternatives
• Hybrid ECDH + post-quantum schemes provide transitional security
• Current PSI protocols using ECDH will require redesign for long-term confidentiality

A security model where all parties are assumed to follow the protocol specification correctly but may attempt to learn additional information from the protocol transcript. Basic ECDH-based PSI protocols typically achieve this level of security. It offers a practical efficiency-security trade-off, as it avoids the heavy cryptographic machinery required to enforce correct behavior against actively malicious adversaries.

A hashing scheme that resolves collisions by relocating existing keys using multiple hash functions. In ECDH-based PSI, Cuckoo hashing is used to optimize the placement of elements into bins, ensuring that each bin contains at most one element. This reduces the number of expensive oblivious comparisons required and dramatically lowers both computation and communication complexity.

A variant of private set intersection where only one party (typically the client) learns the intersection result, while the other (the server) learns nothing. ECDH-based protocols are naturally suited for this, as the client can blind its set elements, send them to the server for one-sided computation, and then locally compare the results against its own processed set to determine the intersection.

ECDH-based PSI protocols are vulnerable to attacks by large-scale quantum computers running Shor's algorithm, which can efficiently solve the elliptic curve discrete logarithm problem. Post-quantum PSI seeks to replace ECDH with quantum-resistant primitives, such as lattice-based key encapsulation mechanisms or isogeny-based cryptography, to ensure long-term privacy of set intersection operations.