Computational hardness assumption
In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where "efficiently" typically means "in polynomial time"). It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood. Computational hardness assumptions are of particular importance in cryptography. A major goal in cryptography 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. However, information theoretic security cannot always be achieved; 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. Computational hardness assumptions are also useful for guiding algorithm designers: a simple algorithm is unlikely to refute a well-studied computational hardness assumption such as P ≠ NP. Comparing hardness assumptions. Computer scientists have different ways of assessing which hardness assumptions are more reliable. Strength  of hardness assumptions. We say that assumption formula_1 is "stronger" than assumption formula_2 when formula_1 implies formula_2 (and the converse is false or not known). In other words, even if assumption formula_1 were false, assumption formula_2 may still be true, and cryptographic protocols based on assumption formula_2 may still be safe to use. Thus when devising cryptographic protocols, one hopes to be able to prove security using the "weakest" possible assumptions. Average-case vs. worst-case assumptions. An average-case assumption says that a specific problem is hard on most instances from some explicit distribution, whereas a worst-case assumption  only says that the problem is hard on "some" instances. For a given problem, average-case hardness implies worst-case hardness, so an average-case hardness assumption is stronger than a worst-case hardness assumption for the same problem. Furthermore, even for incomparable problems, an assumption like the Exponential Time Hypothesis is often considered preferable to an average-case assumption like the planted clique conjecture. Note, however, that in most cryptographic applications, knowing that a problem has some hard instance (i.e. a problem is hard on the worst-case) is useless because it does not provide us with a way  of generating hard instances. Fortunately, many average-case assumptions used in cryptography (including RSA, discrete log, and some lattice problems) can be based on worst-case assumptions via worst-case-to-average-case reductions. Falsifiability. A desired characteristic of a computational hardness assumption is falsifiability, i.e. that if the assumption were false, then it would be possible to prove it. In particular, introduced a formal notion of cryptographic falsifiability. Roughly, a computational hardness assumption is said to be falsifiable if it can be formulated in terms of a challenge: an interactive protocol between an adversary and an efficient verifier, where  an efficient adversary can convince the verifier to accept if and only if the assumption is false. Common cryptographic hardness assumptions. There are many cryptographic hardness assumptions in use. This is a list of some of the most common ones, and some cryptographic protocols that use them. Integer factorization. Given a composite number formula_8, and in particular one which is the product of two large primes formula_9, the integer factorization problem is to find formula_10 and formula_11 (more generally, find primes formula_12 such that formula_13). It is a major open problem to find an algorithm for integer factorization that runs  in time polynomial in the size of representation (formula_14). The security of many cryptographic protocols rely on the assumption that integer factorization is hard (i.e. cannot be solved in polynomial time). Cryptosystems whose security is equivalent to this assumption include the Rabin cryptosystem and the Okamoto–Uchiyama cryptosystem. Many more cryptosystems rely on stronger assumptions such as RSA, Residuosity problems, and Phi-hiding. RSA problem. Given a composite number formula_8, exponent formula_16 and number formula_17, the RSA problem is to find formula_18. The problem is conjectured to be hard, but becomes easy given the factorization of formula_8. In the  RSA cryptosystem, formula_20 is the public key, formula_21 is the encryption of message formula_18, and the factorization of formula_8 is the secret key used for decryption. Residuosity problems. Given a composite number formula_8 and integers formula_25, the residuosity problem is to determine whether there exists (alternatively, find an) formula_26 such that Important special cases include the Quadratic residuosity problem and the Decisional composite residuosity problem. As in the case of RSA, this problem (and its special cases) are conjectured to be hard, but become easy given the factorization of formula_8. Some cryptosystems that rely on the hardness of residuousity problems  include: Phi-hiding assumption. For a composite number formula_18, it is not known how to efficiently compute its Euler's totient function formula_30. The Phi-hiding assumption postulates that it is hard to compute formula_30, and furthermore even computing any prime factors of formula_30 is hard. This assumption is used in the Cachin–Micali–Stadler PIR protocol. Discrete log problem (DLP). Given elements formula_33 and formula_34 from a group formula_35, the discrete log problem asks for an integer formula_36 such that formula_37. The discrete log problem is not known to be comparable to integer factorization, but their computational complexities are  closely related. Most cryptographic protocols related to the discrete log problem actually rely on the stronger Diffie–Hellman assumption: given group elements formula_38, where formula_39 is a generator and formula_40 are random integers, it is hard to find formula_41. Examples of protocols that use this assumption include the original Diffie–Hellman key exchange, as well as the ElGamal encryption (which relies on the yet stronger Decisional Diffie–Hellman (DDH) variant). Multilinear maps. A multilinear map is a function formula_42 (where formula_43 are groups) such that for any formula_44 and formula_45, For cryptographic applications, one would like to construct groups formula_43  and a map formula_16 such that the map and the group operations on formula_43 can be computed efficiently, but the discrete log problem on formula_50 is still hard. Some applications require stronger assumptions, e.g. multilinear analogs of Diffie-Hellman assumptions. For the special case of formula_51, bilinear maps with believable security have been constructed using Weil pairing and Tate pairing. For formula_52 many constructions have been proposed in recent years, but many of them have also been broken, and currently there is no consensus about a safe candidate. Some cryptosystems that rely on multilinear hardness assumptions include: Lattice problems. The  most fundamental computational problem on lattices is the Shortest vector problem (SVP): given a lattice formula_53, find the shortest non-zero vector formula_54. Most cryptosystems require stronger assumptions on variants of SVP, such as Shortest independent vectors problem (SIVP), GapSVP, or Unique-SVP. The most useful lattice hardness assumption in cryptography is for the Learning with errors (LWE) problem: Given samples to formula_55, where formula_56 for some linear function formula_57, it is easy to learn formula_57 using linear algebra. In the LWE problem, the input to the algorithm has errors, i.e. for each pair formula_59 with some small probability. The  errors are believed to make the problem intractable (for appropriate parameters); in particular, there are known worst-case to average-case reductions from variants of SVP. For quantum computers, Factoring and Discrete Log problems are easy, but lattice problems are conjectured to be hard. This makes some lattice-based cryptosystems candidates for post-quantum cryptography. Some cryptosystems that rely on hardness of lattice problems include: Non-cryptographic 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 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, but others include the exponential time hypothesis, the planted clique conjecture, and the unique games conjecture. formula_60-hard problems. Many worst-case computational problems are known to be hard or even complete for some complexity class formula_60, in particular NP-hard (but often also PSPACE-hard, PPAD-hard, etc.). This means that they are at least as hard as any problem in the class formula_60. If a  problem is formula_60-hard (with respect to polynomial time reductions), then it cannot be solved by a polynomial-time algorithm unless the computational hardness assumption formula_64 is false. Exponential Time Hypothesis (ETH) and variants. The Exponential Time Hypothesis (ETH) is a strengthening of formula_65 hardness assumption, which conjectures that not only does the Boolean satisfiability problem not have a polynomial time algorithm, it furthermore requires exponential time (formula_66). An even stronger assumption, known as the Strong Exponential Time Hypothesis (SETH) conjectures that formula_36-SAT requires formula_68 time, where formula_69. ETH, SETH, and related computational hardness assumptions allow for deducing  fine-grained complexity results, e.g. results that distinguish polynomial time and quasi-polynomial time, or even formula_70 versus formula_71. Such assumptions are also useful in parametrized complexity. Average-case hardness assumptions. Some computational problems are assumed to be hard on average over a particular distribution of instances. For example, in the planted clique problem, the input is a random graph sampled, by sampling an Erdős–Rényi random graph and then "planting" a random formula_36-clique, i.e. connecting formula_36 uniformly random nodes (where formula_74), and the goal is to find the planted formula_36-clique (which is unique w.h.p.). Another important example  is Feige's Hypothesis, which is a computational hardness assumption about random instances of 3-SAT (sampled to maintain a specific ratio of clauses to variables). Average-case computational hardness assumptions are useful for proving average-case hardness in applications like statistics, where there is a natural distribution over inputs. Additionally, the planted clique hardness assumption has also been used to distinguish between polynomial and quasi-polynomial worst-case time complexity of other problems, similarly to the Exponential Time Hypothesis. Unique Games. The Unique Label Cover problem is a constraint satisfaction problem, where each constraint formula_60 involves two variables formula_77 , and for each value of formula_26 there is a "unique" value of formula_79 that satisfies formula_60. Determining whether all the constraints can be satisfied is easy, but the Unique Game Conjecture (UGC) postulates that determining whether almost all the constraints (formula_81-fraction, for any constant formula_82) can be satisfied or almost none of them (formula_83-fraction) can be satisfied is NP-hard. Approximation problems are often known to be NP-hard assuming UGC; such problems are referred to as UG-hard. In particular, assuming UGC there is a semidefinite programming algorithm that achieves optimal approximation guarantees for many important problems . Small Set Expansion. Closely related to the Unique Label Cover problem is the Small Set Expansion (SSE) problem: Given a graph formula_84, find a small set of vertices (of size formula_85) whose edge expansion is minimal. It is known that if SSE is hard to approximate, then so is Unique Label Cover. Hence, the "Small Set Expansion Hypothesis", which postulates that SSE is hard to approximate, is a stronger (but closely related) assumption than the Unique Game Conjecture. Some approximation problems are known to be SSE-hard (i.e. at least as hard as approximating SSE). The 3SUM Conjecture. Given a  set of formula_8 numbers, the 3SUM problem asks whether there is a triplet of numbers whose sum is zero. There is an quadratic-time algorithm for 3SUM, and it has been conjectured that no algorithm can solve 3SUM in "truly sub-quadratic time": the 3SUM Conjecture is the computational hardness assumption that there are no formula_87-time algorithms for 3SUM (for any constant formula_88). This conjecture is useful for proving near-quadratic lower bounds for several problems, mostly from computational geometry.