A computational hardness assumption is a conjecture that a particular mathematical problem cannot be solved efficiently by any probabilistic polynomial-time algorithm. Such assumptions, including integer factorisation, the discrete logarithm, and learning-with-errors, are the foundations on which provable security of cryptographic schemes is reduced. If an assumption is broken, every construction whose security reduces to it is compromised.
Content
- Schemes are proven secure by reducing an attack to solving the underlying hard problem, so a scheme is only as strong as its assumption. Post-quantum cryptography migrates from factorisation and discrete-log assumptions to lattice, code, and isogeny problems believed to resist quantum attack.