Skip to content

Assumptions

This page lists common hardness assumptions upon which cryptographic schemes have been based. These range from standard (widely used and believed to hold) to newer assumptions (recently introduced and less well-tested).

Computing the requested answer in each of these cases is believed to be hard. Since the assumptions useful in cryptography are largely computational assumptions, "hard to compute" means computationally intractable (typically in polynomial time).

See also Wikipedia for a list of cryptographic hardness assumptions. Assumptions marked with :simple-atom: are thought to be post-quantum secure.

Types of Assumptions

Subexponential assumptions
Instead of assuming hardness against any adversary running in polynomial time, we make the (stronger) assumption that the problem remains hard even against adversaries running in any subexponential time (so we give the adversary more computational power).
Knowledge assumption
Average-case hardness
When a randomly selected instance of the problem is hard to solve.
Worst-case hardness
When a randomly selected instance of the problem is not necessarily hard to solve, but rather only a carefully crafted "worst case" instance.
Decisional vs. Computational (aka Search)

A decisional problem is of the form "given an input z of the form X or Y, decide whether X or Y was given". A computational problem is of the form "given some input, compute an output meeting some condition". (See the DDH and CDH assumptions below for an example.)

In general, solving the computational variant of a problem implies solving the decisional variant; equivalently, the decisional variant is stronger, i.e., decisional hardness ⇒ computational hardness in general.

List of Assumptions

Discrete logarithm

Discrete Logarithm Problem (DLog/DLP/DL)

Let G be a group.
 Given: \(a,b \in G\)
 Compute: k such that \(b^k=a\)

Diffie–Hellman (DH) assumptions

Computational Diffie–Hellman (CDH)

Let \(G\) be a cyclic group of order \(q\). Choose a random generator \(g\) and let \(a,b\) be uniform and independent integers in \({0, ..., q-1}\):
 Given: \((g, g^a, g^b)\)
 Compute: \(g^{ab}\)

Computational co-Diffie–Hellman (co-CDH) (Variant of CDH)

Let \(G_1\) and \(G_2\) be cyclic groups.
 Given: \((g,g^a,h)\) where \(g,g^a \in G_1\) and \(h \in G_2\)
 Compute: \(h^a \in G_2\)

Decisional Diffie-Hellman (DDH)

Warning

Importantly, the DDH assumption is believed to hold only in certain groups.

Let \(G\) be a cyclic group of order \(q\) with generator \(g\). Let \(a,b,c\) be uniform and independent integers in \({0, ..., q-1}\):
 Given: \((g,g^a,g^b,g^{ab})\)1 or \((g,g^a,g^b,g^c)\)
 Decide: Which type of tuple was given?

Decisional co-Diffie-Hellman (co-DDH) (Variant of DDH)

Let \(G_1\) and \(G_2\) be cyclic groups with generators \(g\) and \(h\).
 Given: \((g,g^a,h,h^b)\)
 Decide: Does \(a=b\)?

Gap Diffie-Hellman (GDH)

Let G be a group in which the DDH problem is easy but the CDH problem is hard (this is called a gap group). The assumption is that CDH is still hard in these groups.

Gap co-Diffie–Hellman (co-GDH) (Variant of GDH)

Let \(G_1\) and \(G_2\) be cyclic groups in which co-DDH is easy but co-CDH is hard. The assumption is that co-CDH is still hard.

External Diffie–Hellman (XDH) (or asymmetric XDH)

Assumes the existence of elliptic-curve subgroups \((G_1, G_2)\) such that

  1. DLog, CDH, and co-CDH are hard in both groups
  2. DDH is hard in \(G_1\)
  3. There is an efficiently computable bilinear map \(e(\cdot, \cdot): G_1 \times G_2 \mapsto G_T\).
Symmetric External Diffie–Hellman (SXDH)

The same as XDH, but additionally assumes in (2) that DDH is also hard in \(G_2\).

Factoring

RSA Assumption

This assumption corresponds exactly to finding the plaintext (\(y\)) of an RSA ciphertext (\(x\)) given only the public key \((n,e)\). Let \(n=pq\) for two large primes \(p,q\) and \(2 < e < n\) (equivalently, \(\gcd(e,n)=1\)).

 Given: \(e,x,n\)
 Compute: \(y\) such that \(y^e = x \pmod{n}\)

Hardness of factoring large numbers

Given a "sufficiently large" composite number, there is no efficient algorithm for decomposing it into a product of smaller integers. (The hardest instances of this problem are of the form \(n=pq\) for large random primes \(p,q\) of similar magnitude; \(n\) is sometimes called a semiprime)

Lattice Assumptions

Learning With Errors (LWE) :simple-atom:

Let \(\mathbf{A}\) be a \(m \times n\) matrix of (uniformly random) integers modulo \(q\) and \(\vec{e},\vec{s}\) be vectors of length \(m\), where \(\vec{e}\) is sampled according to some error distribution \(\chi\) and \(\vec{s}\) consists of uniform integers modulo \(q\).

That is, \(\mathbf{A} \gets\!\!\tiny{\$}\normalsize\ \mathbb{Z}_q^{m \times n}\), \(\vec{s} \gets\!\!\tiny{\$}\normalsize\ \mathbb{Z}_q^m\), \(\vec{e} \gets\!\!\tiny{\$}\normalsize\ \chi\).

 Given: \(\mathbf{A},\vec{b} := \mathbf{A} \cdot \vec{s} + \vec{e}\)
 Compute: \(\vec{s} \in \mathbb{Z}_q^n\) such that \(\mathbf{A}\cdot \vec{s} + \vec{e} = \vec{b} \pmod{q}\)

Let \(\mathbf{A},\vec{s},\vec{e},\vec{b}\) be initialized as in the computational assumption.

 Given: Either \((\mathbf{A},\vec{b})\) or \((\mathbf{A},\vec{u})\), where \(\vec{u} \gets\!\!\tiny{\$}\normalsize\ \mathbb{Z}_q^m\)
 Decide: Whether the given tuple was of the form \((\mathbf{A},\vec{b}:=\mathbf{A}\cdot \vec{s} + \vec{e})\) or \((\mathbf{A},\vec{u})\).

Short Integer Solution (SIS) :simple-atom:

The problem is parameterized by a "small" scalar \(\beta\) (some discussion of bounds on \(\beta\) can be found here).

 Given: \(\mathbf{A} \gets\!\!\tiny{\$}\normalsize\ \mathbb{Z}_q^{n \times m}\)
 Compute: \(\vec{x} \in \mathbb{Z}_q^m\) such that \(\lVert \vec{x} \rVert < \beta\) and \(\mathbf{A} \cdot \vec{x} = \vec{0}\)

Shortest Vector Problem (SVP) :simple-atom:

Other

Learning Parity with Noise (LPN) :simple-atom:

There are a few (equivalent) ways to phrase this assumption; two are given below.

Fix a secret \(n\)-bit string \(k \in \{0,1\}^n\). Let \(\mathcal{O}_{k,\epsilon}\) be an oracle that outputs independent samples \((x_i,y_i)\), where \(x_i\) is a random \(n\)-bit string and \(y_i := \langle x_i \mid k \rangle \oplus e_i\), where the bit \(e_i\) is 1 with probability \(\epsilon\) and 0 otherwise and \(\langle \cdot \mid \cdot \rangle\) means inner product.
 Given: \(q\) samples \((x_i,y_i)\) from \(\mathcal{O}_{k,\epsilon}\)
 Compute: \(k\) (such that \(y_i = \langle x_i \mid k \rangle \oplus e_i\) for all \((x_i,y_i), i=1\ldots q\))

Let \(\mathbf{A}\) be a \(q \times n\) matrix of (uniformly random) bits and \(\vec{e},\vec{y}\) be \(q\)-bit vectors (where \(e_i = 1\) with probability \(\epsilon\) and 0 otherwise).
 Given: \(\mathbf{A},\vec{y}\)
 Compute: \(\vec{k} \in \{0,1\}^n\) such that \(\mathbf{A}\cdot \vec{k} + \vec{e} = \vec{y} \pmod{2}\)

One-way functions

  1. This type of tuple is often called a "DDH tuple" (or a "DDH triple" if the generator is left out). ↩