Sun. Jan 22nd, 2023

Computational Hardness Assumption


The Computational Hardness Assumption is a hypothesis that a given problem cannot be solved in efficiently (in polynomial or better).

It is used where there is no way to prove the hardness of solving a problem: instead, the problem is simplified (reduced) and then compared to another, better understood problem, in order to approximate the hardness.


In cryptography, it is vitally important to prove that an algorithm is secure and provides a safe means of encrypting, transmitting and storing sensitive information.

The security of a cryptographic algorithm can either be proven by Information theoretic security, or if this is not possible, by computational security. Computational security essentially works on the proviso that the attacker is computationally limited (and therefore brute force attacks are futile).

Further reading