Quiz Entry - updated: 2026.07.14
Why does symmetric cryptography have a key distribution problem that asymmetric cryptography solves, and what's the trade-off?
Symmetric crypto needs $O(n^2)$ keys for n participants (every pair shares a secret key), while asymmetric crypto needs only $O(n)$ key pairs — but asymmetric operations are much slower.
* At a million users the pairwise-secret model needs ~500 billion keys; public keys need only a million and can be published openly. *
Key count comparison for n participants:
| Symmetric | Asymmetric | |
|---|---|---|
| Keys needed | $\frac{n(n-1)}{2} \approx \frac{n^2}{2}$ | $n$ key pairs |
| For 1,000 users | ~500,000 shared secrets | 1,000 key pairs |
| For 1,000,000 users | ~500 billion secrets | 1,000,000 key pairs |
| Key distribution | Requires secure channel for each pair | Public keys can be published openly |
| Speed | Fast (AES: hardware acceleration) | Slow (RSA: large number arithmetic) |
The three categories of cryptographic primitives:
- Unkeyed: Hash functions, one-way functions, PRNGs — no secret parameters
- Secret-Key (symmetric): Both parties share the same secret — symmetric ciphers, MACs
- Public-Key (asymmetric): Each party has a public/private pair — encryption, signatures, key exchange
In practice: Hybrid approach — use asymmetric crypto to exchange a symmetric session key, then encrypt bulk data with AES.
Go deeper:
Public-key cryptography — key distribution (Wikipedia) — how publishing public keys dissolves the $O(n^2)$ problem.