Why is public-key cryptography not used for all encryption?

Public-key operations are far slower than symmetric ones and add ciphertext overhead. Real systems use public-key cryptography only to authenticate parties and agree on a symmetric session key, then encrypt the bulk data symmetrically — a hybrid approach.

Will quantum computers break public-key cryptography?

A large-scale quantum computer running Shor's algorithm would break RSA, Diffie-Hellman, and elliptic-curve cryptography by efficiently factoring and computing discrete logarithms. This is why post-quantum schemes based on other hard problems are being standardized and deployed.

Public-Key Cryptography

Public-key (asymmetric) cryptography uses mathematically linked key pairs — a public key for encryption or signature verification and a private key for decryption or signing — so that parties who have never met can communicate securely.

Definition

Public-key cryptography is the branch of cryptography in which each party holds a pair of keys — a public key that may be shared freely and a private key kept secret — such that operations performed with one key are inverted or verified with the other.

Scope

This area covers cryptography based on a key pair whose security rests on computational hardness assumptions such as integer factorization and the discrete logarithm problem. It includes public-key encryption (RSA, ElGamal), key-establishment (Diffie-Hellman), elliptic-curve cryptography, and digital signatures. It addresses the trapdoor and one-way structures these schemes rely on and the standard security goals (semantic security, unforgeability). It excludes symmetric primitives and the certificate and trust infrastructure that distributes public keys (covered under systems and network security).

Sub-topics

Core questions

How can two parties communicate securely without ever sharing a secret in advance?
What computational problems (factoring, discrete log) make public-key schemes hard to break?
What is a trapdoor one-way function, and how does it enable public-key encryption?
How do digital signatures provide authenticity and non-repudiation?
Why is public-key cryptography combined with symmetric cryptography in practice?

Key concepts

public and private key pair
trapdoor one-way function
integer factorization problem
discrete logarithm problem
RSA
Diffie-Hellman key exchange
elliptic-curve cryptography
digital signatures
hybrid encryption

Key theories

Trapdoor one-way functions: Public-key encryption relies on functions easy to compute but hard to invert without secret 'trapdoor' information; RSA's modular exponentiation is easy to invert only for someone who knows the factorization of the modulus.
The public-key idea and key exchange: Diffie and Hellman showed that two parties can agree on a shared secret over a public channel using one-way functions, and proposed splitting cryptographic keys into public and private parts — launching the field of public-key cryptography.
Hardness assumptions: Asymmetric security is conditional: schemes are proven secure relative to the assumed intractability of underlying problems such as integer factorization, the RSA problem, and the discrete logarithm in finite fields or elliptic-curve groups.

Clinical relevance

Public-key cryptography underpins essentially all secure internet communication: TLS uses it to authenticate servers and establish session keys, code-signing and software updates rely on digital signatures, secure email (PGP, S/MIME) and SSH use key pairs, and certificate authorities bind identities to public keys. Cryptocurrencies use public-key signatures to authorize transactions. In practice it is paired with fast symmetric cryptography in hybrid schemes.

Evidence & guidelines

RSA, Diffie-Hellman, and the elliptic-curve variants (ECDH, ECDSA, EdDSA) are standardized (PKCS, NIST SP 800-56, FIPS 186). NIST recommends at least 2048-bit RSA/DH or 224-bit elliptic curves for classical security. Because Shor's algorithm threatens all of these on a quantum computer, NIST has standardized post-quantum replacements (covered separately).

History

Public-key cryptography was introduced publicly by Diffie and Hellman in 1976 (and independently, in classified work, by Ellis, Cocks, and Williamson at GCHQ). The RSA cryptosystem followed in 1977-1978, giving the first practical public-key encryption and signature scheme. ElGamal (1985) built encryption and signatures on the discrete logarithm, and Koblitz and Miller independently proposed elliptic-curve cryptography in 1985, enabling smaller keys.

Key figures

Whitfield Diffie
Martin Hellman
Ralph Merkle
Ronald Rivest
Adi Shamir
Leonard Adleman

Seminal works

diffie1976
rivest1978
katz2020

Frequently asked questions

Why is public-key cryptography not used for all encryption?: Public-key operations are far slower than symmetric ones and add ciphertext overhead. Real systems use public-key cryptography only to authenticate parties and agree on a symmetric session key, then encrypt the bulk data symmetrically — a hybrid approach.
Will quantum computers break public-key cryptography?: A large-scale quantum computer running Shor's algorithm would break RSA, Diffie-Hellman, and elliptic-curve cryptography by efficiently factoring and computing discrete logarithms. This is why post-quantum schemes based on other hard problems are being standardized and deployed.