Minimum Resource Zero-Knowledge Proofs.
Joe Kilian, Silvio Micali, Rafail Ostrovsky
Abstract: We use pseudo-random generators to increase the efficiency of zero-knowledge protocols for the circuit satisfiability problem: given a circuit $C$, is there a setting of $x_1,\ldots,x_n$ such that $C(x_1,\ldots,x_n)=1$? Previous solutions required $O(|C|k)$ bits of communication per interaction, where $k$ is the security parameter. This is impractical for circuits that would occur in actual applications. Our solution requires only $O(|C|+k^2)$ communication between the prover and the verifier. Moreover, we show how to squeeze all of the interactions required for (computationally secure) zero-knowledge proofs into a small initial preprocessing stage. This interactive preprocessing stage may occur even before the prover has decided which theorems he is to prove. After the preprocessing stage has been completed, the prover can prove polynomially many theorems of any polynomial size.
comment: Appeared in In Proceedings of 30th annual IEEE Symposium on the Foundations of Computer Science (FOCS-89) October 30 -- November 1, 1989, Research Triangle Park, NC.
Fetch PostScript file of the paper Fetch PDF file of the paper
| Back to Publications List |