# Subexponential hardness assumption

Edited
I want to read more about subexponential hardness assumption, but I didn't find any good survey on this. I just took a look at Heavy-tailed distribution and Some properties of subexponential distributions but I didn't get a good picture of it.

Question: What is the subexponential hardness assumption? Is it a weaker hardness assumption in comparison with discrete logarithm? Do you know any good survey or article on this?

I saw this subject in this paper:
Adaptive hardness and composable security in the plain model from standard assumptions

• I do not think that I know the answer anyway, but can you provide more information about the term “sublinear hardness assumption”? For example, the context where the term appears will be hopefully helpful. – Tsuyoshi Ito Nov 23 '10 at 12:56
• I've never heard of a sublinear hardness assumption either – Suresh Venkat Nov 23 '10 at 17:13
• Sorry! My bad! Two subjects got mixed together! Please see the edited text – Yasser Sobhdel Nov 23 '10 at 17:47
• the reference you link to nowhere mentions "subexponential hardness assumption". It talks about subexponential hardness which I assume implies hardness of solution in subexponential time ? – Suresh Venkat Nov 23 '10 at 18:44
• @Suresh: I don't get what you mean by "the reference you link to nowhere". I have changed the topic from the original post and I think the Sadeq answer below is more to the point. – Yasser Sobhdel Nov 23 '10 at 20:16

"Complex" problems are normally defined as problems which cannot be solved by (probabilistic) polynomial-time Turing machines.

When there are extra information available for solving the problem, the model changes to machines which take advice. That is, instead of $\rm{BPP}$ machines, we consider $\rm{P/poly}$ circuits; i.e. polynomial-size circuits (equivalently, polynomial-time Turing machines which take polynomial advice).

In some cases, we may consider even stronger solvers: Instead of poly-sized circuits, we may use circuits whose size is sub-exponential. (e.g. circuits whose size is $n^{\log n}$). One might note that, an exponential-size family of circuits can decide any language (even undecidable ones) by merely incorporating the look-up table in its code. (In particular, the size of the look-up table is $O(n2^n)$.)

Let's consider the Decisional Diffie-Hellman (DDH) assumption. I don't go into details. Just assume that $p$ is a large prime, all computations are over $\mathbb{Z}^*_p$, and $g$ is its generator.

DDH: Distinguishing $(g,g^a,g^b,g^{ab})$ from $(g,g^a,g^b,g^c)$ is hard for $\rm{PPT}$ machines.

A stronger assumption is:

DDH-1: Distinguishing $(g,g^a,g^b,g^{ab})$ from $(g,g^a,g^b,g^c)$ is hard for $\rm{P/poly}$ circuits.

An even stronger assumption is:

DDH-2: Distinguishing $(g,g^a,g^b,g^{ab})$ from $(g,g^a,g^b,g^c)$ is hard for sub-exponential circuits.

I saw both DDH and DDH-1 assumptions in the literature. DDH-2 may also exist, but I can't recall whether I ever saw it.

One example of sub-exponential hardness assumption is that, some languages in $\rm{E}$ don't have sub-exponential circuits. Such assumption is used by Impagliazzo & Wigderson in P=BPP unless E has sub-exponential circuits: Derandomizing the XOR Lemma.

## Description of Some Terms

While obvious, I'm going to define several terms here. Let $f \colon \mathbb{N} \to \mathbb{N}$ be a function. Then:

• $f(n) = n^{\Theta(1)}$ is called polynomial. (e.g. $n, n^3, 7n^{100}$.)
• $f(n) = n^{\omega(1)}$ is called super-polynomial. (e.g. $n^{\log n}, 2^n, 2^{2^n}$.)
• $f(n) = 2^{\Theta(n)}$ is called linear exponential. (e.g. $2^n, 3^n, 10^n$.)
• $f(n) = 2^{n^{\Theta(1)}}$ is called exponential. (e.g. $2^n, 3^{n^4}$.)
• $f(n) = 2^{n^{o(1)}}$ is called sub-exponential. (e.g. $2^{n^{1/n}}, n^{\log n}$.)