Zero-Knowledge Proof Systems - Foundations of Cryptography: Basic Tools - page 286

calculation shows that because G n is not 3-colorable there must exist a vertex
for which the prover is able to reveal at least two different colors. Hence, we
can construct a polynomial-size circuit incorporating P ∗ , G n , and y n that violates
the (non-uniform) unambiguity condition. Contradiction to the hypothesis of the
proposition follows, and this completes the proof.

Combining Propositions 4.8.4 and 4.8.9, we get the following:

Corollary 4.8.10: If non-uniformly one-way permutations exist, then every
language in NP has a perfect zero-knowledge argument.

ZK Proofs versus Perfect ZK Arguments: Which to Prefer?
Propositions 4.4.8 and 4.8.9 exhibit a kind of trade-off between the strength of the
soundness and zero-knowledge properties. The protocol of Proposition 4.4.8 offers
computational zero-knowledge and “perfect” soundness, whereas the protocol of
Proposition 4.8.9 offers perfect zero-knowledge and only computational soundness.
We remark that the two results are not obtained under the same assumptions: The con-
clusion of Proposition 4.4.8 is valid as long as one-way functions exist, whereas the
conclusion of Proposition 4.8.9 seems to require a (probably) stronger assumption. Yet
one may ask which of the two protocols we should prefer, assuming that they are both
valid (i.e., assuming that the underlying complexity assumptions hold). The answer de-
pends on the setting (i.e., application) in which the protocol is to be used. In particular,
one should consider the following issues:

• The relative importance attributed to soundness and zero-knowledge in the specific
application. In case of clear priority for one of the two properties, a choice should be
made accordingly.
• The computational resources of the various users in the application. One of the users
may be known to be in possession of much more substantial computing resources, and it
may be desirable to require that he/she not be able to cheat, not even in an information-
theoretic sense.
• The soundness requirement refers only to the duration of the execution, whereas in many
applications the zero-knowledge property may be of concern for a long time afterward.
If that is the case, then perfect zero-knowledge arguments do offer a clear advantage
(over zero-knowledge proofs).

4.8.4. Arguments of Poly-Logarithmic Efficiency

NP
can be obtained by combining the idea of an authentication tree with results regard-
ing probabilistically checkable proofs (PCPs). In particular, assuming the existence
of very strong collision-free hashing functions, one can construct a computationally
sound (zero-knowledge) proof for any language in

A dramatic improvement in the efficiency of zero-knowledge arguments for

, using only poly-logarithmic
amounts of communication and randomness. The interesting point in that statement is
the mere existence of such extremely efficient arguments, let alone their zero-knowledge

NP