__
TR95-038 | 2nd July 1995 00:00
__

#### An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions

**Abstract:**
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.