ECCC-Report TR08-068https://eccc.weizmann.ac.il/report/2008/068Comments and Revisions published for TR08-068en-usTue, 29 Jul 2008 18:10:23 +0300
Paper TR08-068
| Instance-Dependent Commitment Schemes and the Round Complexity of Perfect Zero-Knowledge Proofs |
Lior Malka
https://eccc.weizmann.ac.il/report/2008/068We 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.
Tue, 29 Jul 2008 18:10:23 +0300https://eccc.weizmann.ac.il/report/2008/068