ECCC-Report TR95-038https://eccc.weizmann.ac.il/report/1995/038Comments and Revisions published for TR95-038en-usMon, 10 Jul 1995 07:54:14 +0300
Paper TR95-038
| An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions |
Joe Kilian,
Erez Petrank
https://eccc.weizmann.ac.il/report/1995/038
We consider noninteractive zero-knowledge proofs in the shared random
string model proposed by Blum, Feldman and Micali \cite{bfm}. Until
recently there was a sizable polynomial gap between the most
efficient noninteractive proofs for {\sf NP} based on general
complexity assumptions \cite{fls} versus those based on specific
algebraic assumptions \cite{Da}. Recently, this gap was reduced to a
polylogarithmic factor \cite{Ki}; we further reduce the gap to a
constant factor. Our proof system relies on the existence of one-way
permutations (or trapdoor permutations for bounded provers).
Our protocol is based on the random committed bit model introduced by
Feige, Lapidot and Shamir. We show how to prove that an $n$-gate
circuit is satisfiable, with error probability $1/n^{O(1)}$, using
only $O(n\lg n)$ random committed bits. For this error probability,
this result matches to within a constant factor the number of
committed bits required by the most efficient known {\em interactive}
proof systems.
Mon, 10 Jul 1995 07:54:14 +0300https://eccc.weizmann.ac.il/report/1995/038