Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-132 | 8th December 2009 18:57

How to Achieve Perfect Simulation and a Complete Problem for Non-interactive Perfect Zero-Knowledge


Authors: Lior Malka
Publication: 10th December 2009 04:12
Downloads: 1408


Perfect zero-knowledge (PZK) proofs have been constructed in various settings and they are
also interesting from a complexity theoretic perspective. Yet, virtually nothing is known about them. This is in contrast to statistical zero-knowledge proofs, where many general results have been proved using an array of tools, none of which apply to PZK. To overcome this barrier we introduce a new error shifting technique. This technique helps to achieve perfect simulation and may be useful also in contexts outside of zero-knowledge. Using this technique, we give the first complete problem for the class of problems admitting non-interactive perfect zero-knowledge (NIPZK) proofs, and the first hard problem for the class
of problems admitting public-coin PZK proofs. We hope that our technique and complete problems will
facilitate the study of perfect zero-knowledge proofs.

ISSN 1433-8092 | Imprint