Computational hardness assumption

computational hardness assumptionscomputational securityhardassumptioncomputational assumptionscomputational hardnesscomputationally difficulthardnesshardness assumptionproblems
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").wikipedia
84 Related Articles

Cryptography

cryptographiccryptographercryptology
Computational hardness assumptions are of particular importance in cryptography.
Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed around computational hardness assumptions, making such algorithms hard to break in practice by any adversary.

Provable security

provably secureproven securesecurity reduction
A major goal in cryptography is to create cryptographic primitives with provable security.
The proof of security (called a "reduction") is that these security requirements are met provided the assumptions about the adversary's access to the system are satisfied and some clearly stated assumptions about the hardness of certain computational tasks hold.

Planted clique

planted clique conjecture
preferable to an average-case assumption like the planted clique conjecture. 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.
The conjecture that no polynomial time solution exists is called the planted clique conjecture; it has been used as a computational hardness assumption.

Decisional Diffie–Hellman assumption

Decisional Diffie-Hellmandecisional Diffie–Hellman problemDDH tuple
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).
The decisional Diffie–Hellman (DDH) assumption is a computational hardness assumption about a certain problem involving discrete logarithms in cyclic groups.

Quadratic residuosity problem

quadratic residuosity assumption
Important special cases include the Quadratic residuosity problem and the Decisional composite residuosity problem.
Several cryptographic methods rely on its hardness, see Applications.

Exponential time hypothesis

exponentiallystrong exponential time hypothesis
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.
In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by.

Lattice-based cryptography

lattice-basedLattice-based cryptosystemslattice-based cryptographic schemes
This makes some lattice-based cryptosystems candidates for post-quantum cryptography.
Furthermore, many lattice-based constructions are known to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

Learning with errors

The most useful lattice hardness assumption in cryptography is for the Learning with errors (LWE) problem: Given samples to (x,y), where y=f(x) for some linear function f(\cdot), it is easy to learn f(\cdot) using linear algebra.
The LWE problem has recently been used as a hardness assumption to create public-key cryptosystems, such as the ring learning with errors key exchange by Peikert.

Time complexity

polynomial timelinear timeexponential time
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 n^{1.99} versus n^2.
Although quasi-polynomially solvable, it has been conjectured that the planted clique problem has no polynomial time solution; this planted clique conjecture has been used as a computational hardness assumption to prove the difficulty of several other problems in computational game theory, property testing, and machine learning.

Security level

level of securitybits of securitysecurity claim
* Security level
Their security level isn't set at design time, but represents a computational hardness assumption, which is adjusted to match the best currently known attack.

Computational complexity theory

computational complexitycomplexity theorycomplexity
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").

Reduction (complexity)

reductionreducedreductions
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.

Cryptographic primitive

primitivesalgorithmscryptographic
A major goal in cryptography is to create cryptographic primitives with provable security.

Information-theoretic security

information-theoretically secureinformation theoretic securityperfect secrecy
In some cases, cryptographic protocols are found to have information theoretic security; the one-time pad is a common example.

One-time pad

one-time tapeone time padone-time pads
In some cases, cryptographic protocols are found to have information theoretic security; the one-time pad is a common example.

P versus NP problem

P ≠ NPP = NPcomplexity classes P and NP
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. a simple algorithm is unlikely to refute a well-studied computational hardness assumption such as P ≠ NP.

Average-case complexity

expected timeaverage caseaverage-case
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.

Worst-case complexity

worst caseworst-casein the worst-case
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.

Falsifiability

falsifiableunfalsifiablefalsification
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.

Composite number

compositecomposite numberscomposite integer
Given a composite number n, and in particular one which is the product of two large primes, the integer factorization problem is to find p and q (more generally, find primes such that ).

Rabin cryptosystem

RabinRabin signaturesRabin–Williams
Cryptosystems whose security is equivalent to this assumption include the Rabin cryptosystem and the Okamoto–Uchiyama cryptosystem.

Okamoto–Uchiyama cryptosystem

Cryptosystems whose security is equivalent to this assumption include the Rabin cryptosystem and the Okamoto–Uchiyama cryptosystem.

RSA (cryptosystem)

RSARSA cryptosystemRSA algorithm
The problem is conjectured to be hard, but becomes easy given the factorization of n. In the RSA cryptosystem, (n,e) is the public key, c is the encryption of message m, and the factorization of n is the secret key used for decryption.

Public-key cryptography

public keypublic key cryptographyprivate key
The problem is conjectured to be hard, but becomes easy given the factorization of n. In the RSA cryptosystem, (n,e) is the public key, c is the encryption of message m, and the factorization of n is the secret key used for decryption.

Decisional composite residuosity assumption

Decisional composite residuosity problem
Important special cases include the Quadratic residuosity problem and the Decisional composite residuosity problem.