Cryptography Reference
In-Depth Information
encrypted message). (Definitions and alternative constructions of encryption schemes
secure against chosen message attacks will be presented in Chapter 5 of Volume 2.)
4.7.4.3. A Zero-Knowledge Proof System for
GNI
The interactive proof of Graph Non-Isomorphism (
GNI
) presented in Construction
4.2.8 is not zero-knowledge (unless
GNI
). A cheating verifier can construct
an arbitrary graph
H
and learn whether or not
H
is isomorphic to the first input graph
by sending
H
as a query to the prover. There is an even more appealing refutation of
the claim that Construction 4.2.8 is auxiliary-input zero-knowledge (e.g., the verifier
can check whether or not its auxiliary input is isomorphic to one of the common-
input graphs). We observe, however, that Construction 4.2.8 “would have been zero-
knowledge” if the verifier had always known the answers to its queries (as is the case for
an honest verifier). Thus, we can modify Construction 4.2.8 to obtain a zero-knowledge
proof for
GNI
by having the verifier prove to the prover that he (i.e., the verifier) knows
the answer to his query graph (i.e., that he knows an isomorphism to the appropriate
input graph), and the prover answers the query only if she is convinced of this claim.
Certainly, the verifier's proof of knowledge should
not
yield the answer (otherwise
the prover could use that information in order to cheat, thus foiling the soundness
requirement). If the verifier's proof of knowledge is perfect zero-knowledge, then cer-
tainly it does not yield the answer. In fact, it suffices that the verifier's proof of knowledge
is
witness-independent
(as defined in Section 4.6).
∈
BPP
4.7.5. Proofs of Identity (Identification Schemes)
Identification schemes are useful in large distributed systems in which the users are not
acquainted with one another. In such distributed systems, one wishes to allow users to
authenticate themselves to other users. This goal is achieved by identification schemes,
defined next. In the sequel, we shall also see that identification schemes are intimately
related to proofs of knowledge. We hint that a person's identity can be linked to his
ability to do something and in particular to his ability to prove knowledge of some sort.
4.7.5.1. Definition
Loosely speaking, an identification scheme consists of a
public file
containing
records
for each user and an
identification protocol
. Each (public) record consists of the name (or
identity) of a user and auxiliary
identification information
to be used when invoking the
identification protocol (as discussed later). The public file is established and maintained
by a trusted party that vouches for the authenticity of the records (i.e., that each record
has been submitted by the user whose name is specified in it). All users can read the
public file at all times. Alternatively, the trusted party can supply each user with a
signed copy of its public record. Suppose, now, that
Alice
wishes to prove to
Bob
that it is indeed she who is communicating with him. To this end,
Alice
invokes
the identification protocol, with the (public-file) record corresponding to her name as a
parameter.
Bob
verifies that the parameter in use indeed matches
Alice
's public record
270
