A constant-round public-coin protocol for sampling with size, and applications
Report ID: TR-867-09Author: Xiao, David / Mahmoody Ghidary, Mohammad / Haitner, Iftach
Date: 2009-09-00
Pages: 19
Download Formats: |PDF|
Abstract:
We present a constant-round public-coin protocol between an efficient verifier and an all-powerful (but possibly cheating) prover that achieves the following. Take as input an efficiently verifiable set S, an approximation s roughly equal to |S|, and an efficiently computable partition f : S -> {0,1}* where f(x) = f(x') if and only if x, x' belong to the same set of the partition. Then the verifier outputs with high probability a uniformly random x <- S along with a number s_x that approximates the size of the set |f^{-1}(f(x))|.
Our main application is to rule out certain black-box reductions from the worst-case hardness of SAT to the task of breaking the binding of a constant-round statistically hiding commitment scheme. Specifically, we show that the existence of a k-adaptive randomized reduction for the above task implies that coNP has a O(k)-round public-coin interactive protocol, namely coNP is contained in AM[k]. As corollaries, we derive the following:
- A O(1)-adaptive reduction implies that the Polynomial Hierarchy collapses to the second level (Boppana et al., Inf. Proc. Letters 1987).
- A polylog(n)-adaptive reduction implies the Exponential Hierarchy collapses to its third level (Pavan et al., Theor. Comp. Sci. 2007).
- A o(n)-adaptive reduction improves the round-complexity of the best known interactive proof for UNSAT (the language of unsatisfiable formulas).
Our impossibility result holds even if the hiding property of the commitment scheme is only guaranteed to hold against honest receivers.
Naturally, our result extends to any primitive that implies constant-round statistically hiding commitment via a black-box proof of security. Most notably, this includes collision resistant hash functions, as well as constant-round protocols for single-server private information retrieval and oblivious transfer with statistical security for one of the parties.