No non-adaptive reduction from NP to average-case NP hardness

Unconditional · BT03

Statement

Let $L^{\prime }\in \mathbf{NP}$ and let $D$ be a polynomial-time samplable distribution. If a randomized polynomial-time non-adaptive reduction decides an NP-complete language on every input, given oracle access to any algorithm that decides $L^{\prime }$ on $x\leftarrow D$ with inverse-polynomial error, then $\mathbf{coNP}\subseteq \mathbf{NP}/\mathrm{poly}$ and the polynomial hierarchy collapses to its third level — BT03. Average-case hardness of NP over samplable distributions therefore cannot be based on worst-case $\mathbf{NP}$-hardness by a non-adaptive reduction unless the polynomial hierarchy collapses.

Notes

• The result generalizes the same conclusion for non-adaptive random self-reductions, whose queries are distributed according to $D$ independently of the input — FF93.
• BT03 draw the same conclusion for non-adaptive reductions basing the security of a one-way function on worst-case $\mathbf{NP}$-hardness — BT03; for one-way functions the consequence improves to $\mathbf{coNP}\subseteq \mathbf{AM}$ (No reduction from NP to OWF) — AGGM06.