期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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, Samd 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 Samd oracle for any constant depth d=O(1) with the help of a BPPNP prover. AMSam allows us to conclude that if L is decidable by a k-adaptive randomized oracle algorithm with access to a SamO(1) oracle, then LAM[k]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 NPcoAM and the polynomial hierarchy collapses. The same result holds for any primitive that can be broken by SamO(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(Un), then SWS allows an efficient verifier Arthur to use an all-powerful prover Merlin's help to sample a random yD along with a good multiplicative approximation of the probability py=PryD[y=y]. The crucial feature of SWS is that it extends even to distributions of the form D=f(US), where US is the uniform distribution on an efficiently decidable subset S01n (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 .
