Everything in NP can be argued in perfect zero-knowledge in a bounded number of rounds (extended abstract

A perfect zero-knowledge interactive protocol allows a prover to con-vince a verifier of the validity of a statement in a way that does not give the verifier any additional information [GMR, GMW]. Such protocols take place by the exchange of messages back and forth between the prover and the verifier. An important measure of efficiency for these protocols is the number of rounds in the interaction. In previously known perfect zero-knowledge protocols for statements concerning NP-complete problems [BCC], at least k rounds were necessary in order to prevent one party from having a probability of undetected cheating reater than 2-k. In this paper, we give the first perfect zero-knowledge protocol that offers arbitrarily high security for any statement in NP with a constant number of rounds (under the assumption that it is possible to find a prime p with known factoriza-tion of p-1 such that it is infeasible to compute discrete logarithms modulo p even for someone who knows the factors of p- l, or more gen-erally under the assumption that one-way group homomorphisms exist). All these protocols are BCC-arguments rather than GMR-proofs [BC3]. t Supported inpart by Canada NSERC grant A4107