On the communication complexity of zero-knowledge proofs

The fact that there are zero-knowledge proofs for all languages in NP (see [15], [6], and [5]) has, potentially, enormous implications to cryptography. For cryptographers, the issue is no longer “which languages in NP have zeroknowledge proofs” but rather “which languages in NP have practical zeroknowledge proofs.” Thus, the concrete complexity of zero-knowledge proofs for different languages must be established. In this paper we study the concrete complexity of the known general methods for constructing zero-knowledge proofs. We establish that circuit-based methods, which can be applied in either the GMR or the BCC model, have the potential of producing proofs which can be used in practice. Then we introduce several techniques which greatly reduce the concrete complexity of circuit-based proofs, and we show that these techniques lead to zero-knowledge proofs of knowledge. Finally, we show how to combine the techniques of Kilian, Micali, and Ostrovsky, for designing zero-knowledge proofs with only two envelopes, with some of our techniques for reducing the number of bits which the prover must commit to. Supported in part by NSA Grant No. MDA90488-H-2006. Supported in part by NSF Grant No. CCR-8909657.