The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a major open problem in computational complexity.
In this paper, we provide strong evidences that current techniques cannot establish NP-hardness of MCSP, even under polynomial-time Turing reductions or randomized reductions: Specifically, we introduce the notion of black-box reduction to MCSP, which captures all the currently known reductions. We say that a reduction to MCSP is black-box if the reduction can be generalized to a reduction to MCSP$^A$ for any oracle A, where MCSP$^A$ denotes an oracle version of MCSP. We prove that essentially no language is reducible to MCSP via a polynomial-time Turing reduction in a black-box way. We also show that the class of languages reducible to MCSP via a black-box randomized reduction that makes at most one query is contained in AM and coAM. Thus, NP-hardness of MCSP cannot be established via such black-box reductions unless the polynomial hierarchy collapses.
We also extend the previous results to the case of more general reductions: We prove that establishing NP-hardness of MCSP via a polynomial-time nonadaptive reduction implies ZPP $\neq$ EXP, and that establishing NP-hardness of approximating circuit complexity via a polynomial-time Turing reduction also implies ZPP $\neq$ EXP. Along the way, we prove that approximating Levin's Kolmogorov complexity is provably not EXP-hard under a polynomial-time Turing reduction, which is of independent interest.

Changed the term "black-box reductions" into "oracle-independent reductions". Added more intuitions to proofs. Modified the introduction.

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a major open problem in computational complexity.
In this paper, we provide strong evidences that current techniques cannot establish NP-hardness of MCSP, even under polynomial-time Turing reductions or randomized reductions: Specifically, we introduce the notion of black-box reduction to MCSP, which captures all the currently known reductions. We say that a reduction to MCSP is black-box if the reduction can be generalized to a reduction to MCSP$^A$ for any oracle A, where MCSP$^A$ denotes an oracle version of MCSP. We prove that essentially no language is reducible to MCSP via a polynomial-time Turing reduction in a black-box way. We also show that the class of languages reducible to MCSP via a black-box randomized reduction that makes at most one query is contained in AM and coAM. Thus, NP-hardness of MCSP cannot be established via such black-box reductions unless the polynomial hierarchy collapses.
We also extend the previous results to the case of more general reductions: We prove that establishing NP-hardness of MCSP via a polynomial-time nonadaptive reduction implies ZPP $\neq$ EXP, and that establishing NP-hardness of approximating circuit complexity via a polynomial-time Turing reduction also implies ZPP $\neq$ EXP. Along the way, we prove that approximating Levin's Kolmogorov complexity is provably not EXP-hard under a polynomial-time Turing reduction, which is of independent interest.