A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP

摘要

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 (citeauthor{BogdanovT06}, SIAM J. of Comp. '06 and citeauthor{AkaviaGGM06}, FOCS '06) or to one-way permutations (citeauthor{Brassard79} FOCS '79). The main technical tool we use to prove the above is a new constant-round public-coin protocol ($SWS$), which we believe to be of interest in its own right, 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 -n-na random $y getsr D$ along with a good multiplicative approximation of the probability $p_y = Pr_{y' getsr D}[y' = y]$. The crucial feature of $SWS$ is that it extends even to distributions of the form $D = f(U_cs)$, where $U_cs$ is the uniform distribution on an efficiently decidable subset $cs subseteq zo^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 $|cs|$.