Revision #1 Authors: Oded Goldreich, Liav Teichner

Accepted on: 18th January 2016 18:00

Downloads: 289

Keywords:

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.

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.

TR14-097 Authors: Oded Goldreich, Liav Teichner

Publication: 31st July 2014 09:03

Downloads: 1187

Keywords:

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.