Cryptography Reference
In-Depth Information
•
In Section 4.10 we discuss
non-interactive zero-knowledge
proofs. The notion of witness
indistinguishability (defined in Section 4.6) is a prerequisite for the results presented in
Section 4.10.3.1.
•
In Section 4.11 we discuss
multi-prover
proof systems.
We conclude, as usual, with a miscellaneous section (Section 4.12).
Teaching Tip.
The interactive proof system for Graph Non-Isomorphism (presented
in Section 4.2) and the zero-knowledge proof of Graph Isomorphism (presented in
Section 4.3) are merely illustrative examples. Thus, one should avoid analyzing those
examples in detail.
4.1. Zero-Knowledge Proofs: Motivation
An archetypical cryptographic problem consists of providing mutually distrustful par-
ties with a means of disclosing (predetermined) “pieces of information.” It refers to
settings in which parties posses secrets, and they wish to reveal parts of these secrets.
The secrets are fully or partially determined by some publicly known information, and
so it makes sense to talk about revealing the correct value of the secret. The question is
how to allow verification of newly revealed parts of the secret without disclosing other
parts of the secret. To clarify the issue, let us consider a specific example.
Suppose that all users in a system keep backups of their entire file systems,
encrypted using their secret keys, in publicly accessible storage media. Suppose
that at some point, one user, called
Alice
, wishes to reveal to another user, called
Bob
, the cleartext of some record in one of her files (which appears in her backup).
A trivial “solution” is for
Alice
simply to send the (cleartext) record to
Bob
. The
problem with this “solution” is that
Bob
has no way of verifying that
Alice
has
really sent him the true record (as appearing encrypted in her public backup),
rather than just sending him an arbitrary record.
Alice
could prove that she sent
the correct record simply by revealing to
Bob
her secret key. However, doing so
would reveal to
Bob
the contents of all her files, which is certainly something that
Alice
does not want. The question is whether or not
Alice
can convince
Bob
that she has indeed revealed the correct record without yielding any additional
“knowledge.”
An analogous problem can be phrased formally as follows. Let
f
be a one-way
permutation
and
b
a hard-core predicate with respect to
f
. Suppose that one party,
A
, has a string
x
, whereas another party, denoted
B
, has only
f
(
x
). Furthermore,
suppose that
A
wishes to reveal
b
(
x
) to party
B
, without yielding any further
information. The trivial “solution” is to let
A
send
b
(
x
)to
B
, but, as explained
earlier,
B
will have no way of verifying that
A
has really sent the correct bit
(and not its complement). Party
A
could indeed prove that it has sent the correct
bit (i.e.,
b
(
x
)) by sending
x
as well, but revealing
x
to
B
would be much more
than what
A
originally had in mind. Again, the question is whether or not
A
can
convince
B
that it has indeed revealed the correct bit (i.e.,
b
(
x
)), without yielding
any additional “knowledge.”
