2
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Nov 23 '10 at 12:56
  • $\begingroup$ I've never heard of a sublinear hardness assumption either $\endgroup$ – Suresh Venkat Nov 23 '10 at 17:13
  • $\begingroup$ Sorry! My bad! Two subjects got mixed together! Please see the edited text $\endgroup$ – Yasser Sobhdel Nov 23 '10 at 17:47
  • 1
    $\begingroup$ 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 ? $\endgroup$ – Suresh Venkat Nov 23 '10 at 18:44
  • $\begingroup$ @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. $\endgroup$ – Yasser Sobhdel Nov 23 '10 at 20:16
9
$\begingroup$

"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}$.)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.