Zero-Knowledge - Foundations of Cryptography-A Primer - page 42

do exist for every set in NP (cf. (70)). We comment that the number
of rounds in a protocol is commonly considered the most important
eciency criterion (or complexity measure), and typically one desires
to have it be a constant.
A generic application. As mentioned above, Theorem 4.2 makes
zero-knowledge a very powerful tool in the design of cryptographic
schemes and protocols. This wide applicability is due to two important
aspects regarding Theorem 4.2: Firstly, Theorem 4.2 provides a zero-
knowledge proof for every NP-set, and secondly the prescribed prover
can be implemented in probabilistic polynomial-time when given an
adequate NP-witness. We now turn to a typical application of zero-
knowledge proofs. In a typical cryptographic setting, a user U has a
secret and is supposed to take some action depending on its secret. The
question is how can other users verify that U indeed took the correct
action (as determined by U 's secret and publicly known information).
Indeed, if U discloses its secret then anybody can verify that U took
the correct action. However, U does not want to reveal its secret. Using
zero-knowledge proofs we can satisfy both conflicting requirements (i.e.,
having other users verify that U took the correct action without vio-
lating U 's interest in not revealing its secret). That is, U can prove
in zero-knowledge that it took the correct action. Note that U 's claim
to having taken the correct action is an NP-assertion (since U 's legal
action is determined as a polynomial-time function of its secret and
the public information), and that U has an NP-witness to its valid-
ity (i.e., the secret is an NP-witness to the claim that the action fits
the public information). Thus, by Theorem 4.2, it is possible for U
to eciently prove the correctness of its action without yielding any-
thing about its secret. Consequently, it is fair to ask U to prove (in
zero-knowledge) that it behaves properly, and so to force U to behave
properly. Indeed, “forcing proper behavior” is the canonical application
of zero-knowledge proofs (see (74; 63)).
This paradigm (i.e., “forcing proper behavior” via zero-knowledge
proofs), which in turn is based on the fact that zero-knowledge proofs
can be constructed for any NP-set, has been utilized in numerous differ-