In cryptography, a major goal is to create cryptographic primitives with provable security. In some cases cryptographic protocols are found to have information theoretic security, the one-time pad is a common example. In many cases, information theoretic security cannot be achieved, and in such cases cryptographers fall back to computational security. Roughly speaking this means that these systems are secure assuming that any adversaries are computationally limited, as all adversaries are in practice. Because ## [edit]Common cryptographic hardness assumptionsThere are many common cryptographic hardness assumptions. While the difficulty of solving any of the underlying problems is unproven, some assumptions on the computational hardness are stronger than others. Note that if assumption A is This is a list of some of the most common cryptographic hardness assumptions, and some cryptographic protocols that use them. - Integer factorization
- RSA problem (stronger than factorization)
- Quadratic residuosity problem (stronger than factorization)
- Decisional composite residuosity assumption (stronger than factorization)
- Higher residuosity problem (stronger than factorization)
- Phi-hiding assumption (stronger than factorization)
- Cachin–Micali–Stadler PIR
- Discrete log problem (DLP)
- Computational Diffie–Hellman assumption (CDH; stronger than DLP)
- Decisional Diffie–Hellman assumption (DDH; stronger than CDH)
## [edit]Non-cryptographic hardness assumptionsAs well as their cryptographic applications, hardness assumptions are used in computational complexity theory to provide evidence for mathematical statements that are difficult to prove unconditionally. In these applications, one proves that the hardness assumption implies some desired complexity-theoretic statement, instead of proving that the statement is itself true. The best-known assumption of this type is the assumption that P ≠ NP, |

Technology >