Mathematical problems that are thought to be difficult to solve for all cases in polynomial time

A hardness assumption, also called a hardness problem, is a mathematical problem that is assumed to be difficult to solve in polynomial time. A well-known example is integer factorization. There is no known way for a classical computer to perform integer factorization in polynomial time.

A cryptographic algorithm may be provably reducible to a particular hardness assumption, which provides a guarantee that the algorithm can only be broken if the a solution to the assumption is found. The Rabin cryptosystem is provably reducible to the difficulty of integer factorization, for example, whereas RSA is thought to be as difficult as integer factorization, but this has not been proven (i.e. the RSA problem has not been provably reduced to the integer factorization problem).

A hardness assumption can be classified based on whether it's average or worst-case for typical problems. There are a very large number of hardness assumptions used in cryptography.

history | excerpt history