An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions

We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum et al. 5]. Until recently there was a sizable polynomial gap between the most efficient noninteractive proofs for NP based on general complexity assumptions 11] versus those based on specific algebraic assumptions 7]. Recently, this gap was reduced to a polylogarithmic factor 17]; 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 stated in the hidden bit model introduced by Feige et al. 11]. 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 interactive proof systems. Received 20 November 1995 and revised 7 October 1996