- cc.complexity-theory cr.crypto-security np advice-and-nonuniformity average-case-complexity
- Updated Sat, 11 Jun 2022 04:05:15 GMT

This question arose in the context of cryptography, but below I will present it in terms of complexity theory, since people here are more acquainted with the latter. This question is related to Problems in NP but not in Average-P/poly and Beating Nonuniformity by Oracle Access.

**Informal statement:** When do non-uniform adversaries (i.e. poly-size family of circuits) succeed in breaking a cryptographic scheme, but uniform adversaries (i.e. probabilistic poly-time Turing machines) do not?

**Complexity-theoretic statement:** This is not exactly the same as the above informal statement, but I'm actually interested in this version:

What natural problems lie in $(\mathsf{NP} \cap \mathsf{P/poly}) - \mathsf{AvgP}$ ?

In other words, what **hard-on-average** natural $\mathsf{NP}$ problems can be **solved** by poly-sized family of circuits?

The word **solved** can be interpreted as the worst-case or average-case (the latter is preferred).

If natural problems cannot be found easily, artificial problems are acceptable as well.

There is hardly any natural problem which is believed to be in P/poly but not in P. The artificial examples can be adapted to answer your question.

Assume $E \neq NE$, then there is a unary language L in NP which is not in P -- unary means that all the strings in the language have the form $1^n$ for some n.

Then define L' to be the set of all strings x such that $1^{length(x)}$ is in L. This is in NP, it is in P/poly, and it is not in average polynomial time

External links referenced by this document: