Cryptography Reference
In-Depth Information
Construction 4.4.7 (when applied on common input G
=
( V
,
E )) is a proof of knowl-
1
| E |
edge of a 3-coloring with knowledge error 1
; see Exercise 26. By iterating each
construction sufficiently many times, we can get the knowledge error to be exponen-
tially small (see Proposition 4.7.5). In fact, using Proposition 4.7.6, we get proofs of
knowledge with zero error. In particular, we have the following:
Theorem 4.7.7: Assuming the existence of (non-uniformly) one-way functions,
every
NP
-relation has a zero-knowledge system for proofs of knowledge. Fur-
thermore, inputs not in the corresponding language are accepted by the verifier
with exponentially vanishing probability.
4.7.4. Applications
We briefly review some of the applications of (zero-knowledge) proofs of knowledge.
Typically, zero-knowledge proofs of knowledge are used for “mutual disclosure” of the
same information. Suppose that Alice and Bob both claim that they know something
(e.g., a 3-coloring of a common-input graph), but each is doubtful of the other's claim.
Employing a zero-knowledge proof of knowledge in both directions is indeed a (con-
ceptually) simple solution to the problem of convincing each other of their knowledge.
Before describing the applications, let us briefly comment on how their security
is proved. Typically, a zero-knowledge proof of knowledge is used as a sub-protocol,
and rejecting in this sub-protocol means that the verifying party detects cheating. The
proof of security for the high-level protocol is by a simulation argument that utilizes
the knowledge extractor, but invokes it only in case the verifying party does not detect
cheating. Our definition of (the validity condition of) proofs of knowledge guarantees
that the simulation will run in expected polynomial time, regardless of the (a priori
unknown) probability that the verifying party will accept.
In all applications, the proof of knowledge employed has negligible soundness error
(i.e., inputs not in the corresponding language are accepted by the verifier with negligible
probability).
4.7.4.1. Non-Oblivious Commitment Schemes
When using a commitment scheme, the receiver is guaranteed that after the commit
phase the sender is committed to at most one value (in the sense that it can later “reveal”
only this value). Yet the receiver is not guaranteed that the sender “knows” to what value
the sender is committed. Such a guarantee can be useful in many settings and can be
obtained by using a proof of knowledge. For more details, see Section 4.9.2.
4.7.4.2. Protecting against Chosen Message Attacks
An obvious way of protecting against chosen message attacks on a (public-key) en-
cryption scheme is to augment the ciphertext by a zero-knowledge proof of knowledge
of the cleartext. Thus, the benefit (to the adversary) of a chosen message attack is es-
sentially eliminated. However, one should note that the resulting encryption scheme
employs bidirectional communication between the sender and the receiver (of the
269
Search WWH ::




Custom Search