In cryptography

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

, a major goal is to create cryptographic primitive

Cryptographic primitive

Cryptographic primitives are well-established, low-level cryptographic algorithms that are frequently used to build computer security systems. These routines include, but are not limited to, one-way hash functions and encryption functions.- Rationale :...

s with provable security

Provable security

In cryptography, a system has provable security if its security requirements can be stated formally in an adversarial model, as opposed to heuristically, with clear assumptions that the adversary has access to the system as well as enough computational resources...

. In some cases cryptographic protocols are found to have information theoretic security

Information theoretic security

A cryptosystem is information-theoretically secure if its security derives purely from information theory. That is, it is secure even when the adversary has unlimited computing power. The adversary simply does not have enough information to break the security...

, the one-time pad

One-time pad

In cryptography, the one-time pad is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key of the same length as the plaintext, resulting...

 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
  Integer factorization
  In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
  
  
  • Rabin cryptosystem
    Rabin cryptosystem
    The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proved to be as hard as integer factorization, which is...
    
    
  • Blum Blum Shub generator
  • Okamoto–Uchiyama cryptosystem
• RSA problem
  RSA problem
  In cryptography, the RSA problem summarizes the task of performing an RSA private-key operation given only the public key. The RSA algorithm raises a message to an exponent, modulo a composite number N whose factors are not known. As such, the task can be neatly described as finding the eth roots...
  
   (stronger than factorization)
  • RSA cryptosystem
• Quadratic residuosity problem
  Quadratic residuosity problem
  The quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number...
  
   (stronger than factorization)
  • Goldwasser–Micali cryptosystem
• Decisional composite residuosity assumption
  Decisional composite residuosity assumption
  The decisional composite residuosity assumption is a mathematical assumption used in cryptography. In particular, the assumption is used in the proof of the Paillier cryptosystem....
  
   (stronger than factorization)
  • Paillier cryptosystem
    Paillier cryptosystem
    The Paillier cryptosystem, named after and invented by Pascal Paillier in 1999, is a probabilistic asymmetric algorithm for public key cryptography. The problem of computing n-th residue classes is believed to be computationally difficult...
    
    
• Higher residuosity problem
  Higher residuosity problem
  In cryptography most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem is one such problem...
  
   (stronger than factorization)
  • Benaloh cryptosystem
    Benaloh cryptosystem
    The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem created in 1994 by Josh Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually.-Scheme...
    
    
  • Naccache–Stern cryptosystem
• Phi-hiding assumption
  Phi-hiding assumption
  The phi-hiding assumption or Φ-hiding assumption is an assumption about the difficulty of finding small factors of φ where m is a number whose factorization is unknown, and φ is Euler's totient function. The security of many modern cryptosystems comes from the perceived difficulty of certain...
  
   (stronger than factorization)
  • Cachin–Micali–Stadler PIR
    Private information retrieval
    In cryptography, a private information retrieval protocol allows a user to retrieve an item from a server in possession of a database without revealing which item they are retrieving...
    
    
• Discrete log problem (DLP)
• Computational Diffie–Hellman assumption (CDH; stronger than DLP)
  • Diffie–Hellman key exchange
• Decisional Diffie–Hellman assumption (DDH; stronger than CDH)
  • ElGamal encryption
    ElGamal encryption
    In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1984. ElGamal encryption is used in the free GNU Privacy Guard software, recent versions of...
    
    

Non-cryptographic hardness assumptions

As well as their cryptographic applications, hardness assumptions are used in computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

 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

Exponential time hypothesis

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption formalized by stating that 3-SAT cannot be solved in subexponential time in the worst case. The exponential time hypothesis, if true, would imply that P ≠ NP...

 and the unique games conjecture

Unique games conjecture

In computational complexity theory, the Unique Games Conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the value of a certain type of game, known as a unique game, has NP-hard algorithmic complexity...

.