Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-001 | 30th December 2009 19:32

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 (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|$.

ISSN 1433-8092 | Imprint