Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR14-097 | 18th January 2016 18:00

Super-Perfect Zero-Knowledge Proofs

RSS-Feed




Revision #1
Authors: Oded Goldreich, Liav Teichner
Accepted on: 18th January 2016 18:00
Downloads: 969
Keywords: 


Abstract:

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.



Changes to previous version:

The main change is the introduction of a more relaxed nonstandard model of PPT machines (see the very beginning of sec 1.2) and its usage in Sec 3.2.


Paper:

TR14-097 | 31st July 2014 09:03

Super-Perfect Zero-Knowledge Proofs


Abstract:

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.



ISSN 1433-8092 | Imprint