Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs.
Lior Malka · 2008
Abstract. We study the question whether the number of rounds in public-coin perfect zero-knowledge (PZK) proofs can be collapsed to a constant. Despite extensive research into the round complexity of interactive and zero-knowledge protocols, there is no indication how to address this question. Furthermore, the main tool to tackle this question is instance-dependent commitments, but currently such schemes are only statistically hiding, whereas we need perfectly hiding schemes. We give the first perfectly hiding instance-dependent commitment scheme. This scheme can be con-structed from any problem that has a PZK proof. We then show that obtaining such a scheme that is also constant-round is not only sufficient, but also necessary to collapse the number of rounds in PZK proofs. Hence, we show an equivalence between the tasks of obtaining the commitment, and collapsing the rounds. Our idea also yields an elegant equivalence between zero-knowledge and commitments. In the second part of the paper we construct a non-interactive, perfectly hiding scheme whose binding property holds on all but an exponentially small fraction of the inputs. Informally, this shows that the rounds in public-coin PZK proofs can be collapsed if we can guarantee that the prover is not choosing its randomness from a small set. We formalize this condition using a preamble, which we then apply to some simple cases. An interesting consequence of independent interest is that we use the circuits from the study of NIPZK in the commitment scheme of Naor [39], and this leads to a new perfectly-hiding instance-dependent commitment for NIPZK problems with a small soundness error. Key words: constant-round, perfect zero-knowledge, instance-dependent commitment schemes. 1