In this paper, we consider ZKIPs for promise problems. A promise problem is a pair of predicates (Q,R). A Turning machine T solves the promise problem (Q,R) if, for every x satisfying Q(x), machine T halts and it answers "yes" iff R(x). When ¬Q (x), we do not care what T does. First, we define "promised BPP" which is a promise problem version of BPP. Then, we prove that a promise problem (Q,R) has a 3-move interactive proof system which is black-box simulation zero knowledge if and only if (Q,R) ∈ promised BPP. Next, we show a "4-move" perfect ZKIPs (black-box simulation) for a promise problem of Quadratic Residuosity and that of Blum Numbers under no cryptographic assumption.

We show that, if NP language L has an invulnerable generator and if L has an honest verifier standard statistical ZKIP, then L has a 5 move statistical ZKIP. Our class of languages involves random self reducible languages because they have standard perfect ZKIPs. We show another class of languages (class K) which have standard perfect ZKIPs. Blum numbers and a set of graphs with odd automorphism belong to this class. Therefore, languages in class K have 5 move statistical ZKIPs if they have invulnerable generators.

We define the communication complexity of a perfect zero-knowledge interactive proof (ZKIP) as the expected number of bits communicated to achieve the given error probabilities (of both the completeness and the soundness). While the round complexity of ZKIPs has been studied greatly, no progress has been made for the communication complexity of those. This paper shows a perfect ZKIP whose communication complexity is 11/12 of that of the standard perfect ZKIP for a specific class of Quadratic Residuosity.