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