On this page
1. Why intuition fails
For most of history, ciphers were considered secure because no one present could break them. That is not evidence — it is absence of evidence, and the record of confidently broken schemes is long.
The problem is that "secure" on its own is meaningless. Secure against whom? With what resources? Achieving what? A cipher safe against someone reading traffic may collapse against someone who can also submit chosen messages.
2. Security as a game
Cryptographers replaced intuition with a precise setup: a game between a challenger and an adversary. The rules state exactly what the adversary can see and do, and what counts as a win.
A scheme is secure if no efficient adversary wins with probability meaningfully better than guessing. Two terms carry the weight:
Efficient means running in polynomial time — a stand-in for "realistically achievable". Negligible means the advantage shrinks faster than any inverse polynomial as the key grows. Not zero; just small enough that scaling the key makes it hopeless.
3. IND-CPA: the baseline
Indistinguishability under chosen-plaintext attack is the standard minimum. The game:
Probe
The adversary may encrypt any messages it likes, as many times as it likes.
Challenge
It submits two equal-length messages. The challenger secretly picks one and returns its encryption.
Guess
The adversary says which was encrypted. Winning means being right meaningfully more than half the time.
This immediately rules out deterministic encryption. If the same plaintext always produced the same ciphertext, the adversary would simply encrypt both candidates and compare — which is exactly why ECB mode fails and why real encryption is randomised.
4. IND-CCA: active attackers
IND-CPA assumes a passive observer. Real attackers do more: they modify ciphertexts and watch how the system reacts.
Under chosen-ciphertext attack the adversary may also ask for decryptions of ciphertexts of its choosing — anything except the challenge itself. This models something that genuinely happens: padding-oracle attacks recovered plaintext from real TLS implementations using nothing but error messages.
Achieving IND-CCA essentially requires authenticated encryption. If tampered ciphertexts are rejected outright, the decryption oracle stops leaking — another reason GCM replaced bare CBC.
5. Reduction proofs
Almost nothing in cryptography is proved secure outright. Instead security is reduced to a problem believed hard.
The argument runs backwards: assume an adversary breaks the scheme, then use it as a component to solve factoring or the discrete logarithm. Since nobody can do that, no such adversary exists.
This is honest about its own limits. "Provably secure" never means unbreakable — it means as hard to break as the underlying problem. If factoring falls, everything reduced to it falls with it. That is precisely what quantum computing threatens, and why the assumptions matter as much as the proofs.
Frequently asked questions
- What does provably secure mean?
- That breaking the scheme is at least as hard as solving a problem believed to be intractable, such as factoring. It is a relative guarantee, not a claim of being unbreakable.
- What is IND-CPA?
- Indistinguishability under chosen-plaintext attack. An adversary who can encrypt anything it likes still cannot tell which of two chosen messages was encrypted, better than guessing.
- What is the difference between IND-CPA and IND-CCA?
- IND-CCA additionally lets the adversary request decryptions of ciphertexts it chooses, modelling active attackers. Achieving it generally requires authenticated encryption.
- Why must encryption be randomised?
- Because deterministic encryption fails IND-CPA: an adversary could encrypt both candidate messages and compare the results directly.