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 s izable polynomial gap between the most efficient noninteractive proofs for NP based on general complexity assumptions [11] versus those base d on specific algebraic assumptions [7]. Recently, this gap was reduce d to a polylogarithmic factor [17]; we further reduce the gap to a con stant factor. Our proof system relies on the existence of one-way perm utations (or trapdoor permutations for bounded provers).Our protocol i s stated in the hidden bit model introduced by Feige et al. [11]. We s how how to prove that an n-gate circuit is satisfiable, with error pro bability 1/n(0(1)), using only O(n lg n) random committed bits. For th is error probability, this result matches to within a constant factor the number of committed bits required by the most efficient known inte ractive proof systems.