 Computational hardness assumption

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 onetime 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.
Common cryptographic hardness assumptions
There 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 stronger than assumption B, that means solving the problem underlying assumption B is polytime reducible to solving the problem underlying assumption A – which means that if B is solvable in poly time, A definitely is, but the reverse doesn't follow. 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
 Decisional composite residuosity assumption (stronger than factorization)
 Higher residuosity problem (stronger than factorization)
 Phihiding 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)
Noncryptographic hardness assumptions
As 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 complexitytheoretic statement, instead of proving that the statement is itself true. The bestknown assumption of this type is the assumption that P ≠ NP,^{[1]} but others include the exponential time hypothesis^{[2]} and the unique games conjecture.^{[3]}
References
 ^ Fortnow, Lance (2009), "The status of the P versus NP problem", Communications of the ACM 52 (9): 78–86, doi:10.1145/1562164.1562186, http://www.cs.uchicago.edu/~fortnow/papers/pnpcacm.pdf.
 ^ Woeginger, Gerhard (2003), "Exact algorithms for NPhard problems: A survey", Combinatorial Optimization — Eureka, You Shrink!, 2570, SpringerVerlag, pp. 185–207, doi:10.1007/3540364781_17.
 ^ Khot, Subhash (2010), "On the Unique Games Conjecture", Proc. 25th IEEE Conference on Computational Complexity, pp. 99–121, doi:10.1109/CCC.2010.19, http://cs.nyu.edu/~khot/papers/UGCSurvey.pdf.
Categories: Theory of cryptography
 Computational number theory
 Integer factorization
Wikimedia Foundation. 2010.
Look at other dictionaries:
Computational — may refer to: Computer Computational algebra Computational Aeroacoustics Computational and Information Systems Laboratory Computational and Systems Neuroscience Computational archaeology Computational auditory scene analysis Computational biology … Wikipedia
Computational Diffie–Hellman assumption — The computational Diffie–Hellman (CDH assumption) is the assumption that a certain computational problem within a cyclic group is hard. Consider a cyclic group G of order q. The CDH assumption states that, given for a randomly chosen… … Wikipedia
Decisional Diffie–Hellman assumption — The decisional Diffie–Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most… … Wikipedia
Decisional DiffieHellman assumption — The decisional Diffie Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups. It is used as the basis to prove the security of many cryptographic protocols, most… … Wikipedia
Decisional composite residuosity assumption — The decisional composite residuosity assumption (DCRA) is a mathematical assumption used in cryptography. In particular, the assumption is used in the proof of the Paillier cryptosystem. Informally the DCRA states that given a composite n… … Wikipedia
Phihiding assumption — The Phi Hiding assumption or Φ Hiding assumption is an assumption about the difficulty of finding small factors of φ( m ) where m is a number whose factorization is unknown, and φ is Euler s totient function. The security of many modern… … Wikipedia
Decision Linear assumption — The Decision Linear (DLIN) assumption is a mathematical assumption used in elliptic curve cryptography. In particular, the DLIN assumption is useful in settings where the decisional Diffie–Hellman assumption does not hold (as is often the case in … Wikipedia
List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… … Wikipedia
Problème de la résiduosité quadratique — En théorie algorithmique des nombres, le problème de la résiduosité[1] quadratique est celui de distinguer, à l aide de calculs, les résidus quadratiques modulo un nombre composé N fixé. C est un problème important en cryptographie, en… … Wikipédia en Français
Cryptography — Secret code redirects here. For the Aya Kamiki album, see Secret Code. Symmetric key cryptography, where the same key is used both for encryption and decryption … Wikipedia