Computational Hardness Assumption

Summary

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.

Significance

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

https://en.wikipedia.org/wiki/Computational_hardness_assumption