Super-Perfect Zero-Knowledge Proofs

Webpage for a paper by Oded Goldreich and Liav Teichner


We initiate a study of super-perfect zero-knowledge proof systems. Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time. In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated by a strict probabilistic polynomial-time that is allowed to fail with probability at most one half.

We show that two types of perfect zero-knowledge proof systems can be transformed into super-perfect ones. The first type includes the perfect zero-knowledge interactive proof system for Graph Isomorphism and other systems of the same form, including perfect zero-knowledge arguments for NP. The second type refers to perfect non-interactive zero-knowledge proof systems. We also present a super-perfect non-interactive zero-knowledge proof system for the set of Blum integers.

Material available on-line

Back to either Oded Goldreich's homepage or general list of papers.