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

We study perfect zero-knowledge proofs (

). Unlike statistical zero-knowledge, where many fundamental questions have been answered, virtually nothing is known about these proofs.

We consider reductions that yield hard and complete problems in the statistical setting. The issue with these reductions is that they introduce errors into the simulation, and therefore they do not yield analogous problems in the perfect setting. We overcome this issue using an

error shifting technique

. This technique allows us to remove the error from the simulation. Consequently, we obtain the first complete problem for the class of problems possessing non-interactive perfect zero-knowledge proofs (

), and the first hard problem for the class of problems possessing public-coin

proofs.

We get the following applications. Using the error shifting technique, we show that the notion of zero-knowledge where the simulator is allowed to fail is equivalent to the one where it is not allowed to fail. Using our complete problem, we show that under certain restrictions

is closed under the

OR

operator. Using our hard problem, we show how a

constant-round, perfectly hiding

instance-dependent commitment may be obtained (this would collapse the round complexity of public-coin

proofs to a constant).