Computational hardness assumption

From Wikipedia, the free encyclopedia

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 hardness of a problem is difficult to prove, in practice certain problems are "assumed" to be difficult.

[edit] Common cryptographic hardness assumptions

There are many common cryptographic hardness assumptions, while the difficulty of solving any of the underlying problems is unknown, some assumptions are stronger than others. Note: that if any assumption is weaker than another that means solving the underlying problem is easier. When devising cryptographic protocols, one hopes to be able to prove security using the weakest possible assumptions.

This is a list of some of the most common cryptographic hardness assumptions, and some cryptographic protocols that use them.

• Integer factorization
  • Rabin cryptosystem
  • Blum Blum Shub generator
  • Okamoto-Uchiyama cryptosystem
• RSA problem (stronger than factorization)
  • RSA Cryptosystem
• Quadratic residuosity problem (stronger than factorization)
  • Goldwasser-Micali cryptosystem
• Composite residuosity problem (stronger than factorization)
  • Paillier cryptosystem
• Higher residuosity problem (stronger than factorization)
  • Benaloh cryptosystem
  • Naccache-Stern cryptosystem
• Phi-hiding assumption (stronger than factorization)
  • Cachin-Micali-Stadler PIR
• Discrete log problem (DLP)
• Decisional Diffie-Hellman assumption (stronger than DLP)
  • El Gamal cryptosystem
• Computational Diffie-Hellman assumption (stronger than DLP)
  • Diffie-Hellman key exchange