We investigate the question of what languages can be decided efficiently with the help of a recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash functions or, more generally, statistically hiding commitments. The oracle we consider, $Sam_d$ where $d$ is the recursion depth, is based on the identically-named oracle defined in the work of Haitner et al. (FOCS '07). Our main result is a constant-round public-coin protocol ``$AMSam$'' that allows an efficient verifier to emulate a $Sam_d$ oracle for any constant depth $d = O(1)$ with the help of a $BPP^{NP}$ prover. $AMSam$ allows us to conclude that if $L$ is decidable by a $k$-adaptive randomized oracle algorithm with access to a $Sam_{O(1)}$ oracle, then $L \in AM[k] \cap coAM[k]$.
The above yields the following corollary: assume there exists an $O(1)$-adaptive reduction that bases constant-round statistically hiding commitment on $NP$-hardness, then $NP \subseteq coAM$ and the polynomial hierarchy collapses. The same result holds for any primitive that can be broken by $Sam_{O(1)}$ including collision-resistant hash functions and $O(1)$-round oblivious transfer where security holds statistically for one of the parties. We also obtain non-trivial (though weaker) consequences for $k$-adaptive reductions for any $k = poly(n)$. Prior to our work, most results in this research direction either applied only to non-adaptive reductions (Bogdanov and Trevisan, SIAM J. of Comp. '06) or to primitives with special regularity properties (Brassard79 FOCS '79, Akavia et al, FOCS '06).
The main technical tool we use to prove the above is a new constant-round public-coin protocol ($SWS$) that we believe may be interesting in its own right, and that guarantees the following. Given an efficient function $f$ on $n$ bits, let $D$ be the output distribution $D = f(U_n)$, then $SWS$ allows an efficient verifier Arthur to use an all-powerful prover Merlin's help to sample a random $y \gets D$ along with a good multiplicative approximation of the probability $p_y = \Pr_{y' \gets D}[y' = y]$. The crucial feature of $SWS$ is that it extends even to distributions of the form $D = f(U_S)$, where $U_S$ is the uniform distribution on an efficiently decidable subset $S \subseteq {0,1}^n$ (such $D$ are called efficiently samplable with \emph{post-selection}), as long as the verifier is also given a good approximation of the value $|S|$.
