ECCC-Report TR14-097https://eccc.weizmann.ac.il/report/2014/097Comments and Revisions published for TR14-097en-usMon, 18 Jan 2016 18:00:14 +0200
Revision 1
| Super-Perfect Zero-Knowledge Proofs |
Oded Goldreich,
Liav Teichner
https://eccc.weizmann.ac.il/report/2014/097#revision1We 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. Mon, 18 Jan 2016 18:00:14 +0200https://eccc.weizmann.ac.il/report/2014/097#revision1
Paper TR14-097
| Super-Perfect Zero-Knowledge Proofs |
Oded Goldreich,
Liav Teichner
https://eccc.weizmann.ac.il/report/2014/097We 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. Thu, 31 Jul 2014 09:03:58 +0300https://eccc.weizmann.ac.il/report/2014/097