Efficient Non-Interactive Zero-Knowledge Proofs of Circuit Satisfiability
Joan Boyar, René Peralta · 1994
We show how to construct a "zero-knowledge proof" that a circuit of size m is satisfiable. The proof is a string of length O(m lg m) which is constructed (and can be verified) using a trusted random string of length O(m lg m). The probability of failure or of cheating is exponentially small in a security parameter which is defined independently Supported in part by NSF Grant CCR-9207204. of the circuit size. Our methods assume that a Quadratic Residuosity Bit Commitment Scheme is available as a primitive and does not consider the cost of establishing this scheme, only the cost of using it. Thus, these "proofs" are essentially non-interactive zero-knowledge proofs, with a couple of changes to the standard definition, though they can easily be modified to fit the standard definition. The techniques used yield more efficient "proofs" than those previously known. 1 Introduction A non-interactive zero-knowledge proof system is a protocol that allows a prover to convince a verifier tha...