Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR08-068 | 3rd July 2008 00:00

Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs


Authors: Lior Malka
Publication: 29th July 2008 18:10
Downloads: 4090


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 constructed 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 (J.Cryptology 91), and this leads to a new perfectly-hiding instance-dependent commitment for NIPZK problems with a small soundness error.

ISSN 1433-8092 | Imprint