Cryptography, security, and hardness assumptions
Important
Cryptography is based on finding a mathematical problem that is very hard to solve – unless you know a secret, sometimes known as the private key.
Important
A key is information.
Analogy
Important
Most problems are presumed hard until proven easy.
It is always possible to put an upper bound on the work that an adversary needs to do to break a cryptosystem – at worst, trying every possible key. Trial and error without a strategy is also known as brute force.
Putting a lower bound on the work an adversary needs to do – in other words, proving that a problem is at least this hard to solve – is quite rare.
Exception
Problem
Quantum computing allows the invention of some algorithms that are much more efficient than classical algorithms at solving specific problems. In particular, Shor’s algorithm allows a sufficiently powerful quantum computer to recover private keys from public keys for legacy cryptosystems.
This drives the need to replace all public key algorithms, particularly digital signatures and key exchange / encapsulation.
Solution
Post-quantum cryptography is about finding new problems that are presumed to be difficult to solve on both classical and quantum computers – until proven otherwise – and building new cryptosystems on these problems.
Learn more about legacy cryptosystems like RSA in the Cryptography section, and more about quantum algorithms in the Quantum Information section.