Computational hardness assumption

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where efficiently typically means "in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a>"). It is not known how to <a href="/facts/Mathematical_proof/7ECDrU80">prove</a> (unconditional) hardness for essentially any useful problem. Instead, <a href="/facts/Computer_scientist/DavggjGL">computer scientists</a> rely on <a href="/facts/Reduction_(complexity)/IVWF7a1c">reductions</a> 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 <a href="/facts/Cryptography/e94PEVau">cryptography</a>. A major goal in cryptography is to create <a href="/facts/Cryptographic_primitive/fy6vq5YM">cryptographic primitives</a> with <a href="/facts/Provable_security/2kQS1WId">provable security</a>. In some cases, cryptographic protocols are found to have <a href="/facts/Information_theoretic_security/DG2q6XeI">information theoretic security</a>; the <a href="/facts/One-time_pad/03hA9XSQ">one-time pad</a> 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 <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> designers: a simple algorithm is unlikely to refute a well-studied computational hardness assumption such as <a href="/facts/P_versus_NP_problem/xoC7Ruda">P ≠ NP</a>.

Computational hardness assumption open-in-new

Computational hardness assumption