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.