Cryptography Reference
In-Depth Information
Formally, we define a language
def
={
L
(
c
,
u
):
∃
v,
s
s.t.
c
=
C
s
(
v
) and
v>
u
}
Clearly, the language
L
is in
NP
, and the
NP
-witness for (
c
,
u
)
∈
L
is a pair (
v,
s
), as
shown. Hence, Theorem 4.4.11 can be applied.
Additional examples are presented in Exercise 18. Other applications will appear in
Volume 2.
We stress that because it is a general (and in some sense generic) result, the con-
struction underlying Theorem 4.4.11 cannot be expected to provide a practical solution
(especially in simple cases). Theorem 4.4.11 should be viewed as a plausibility argu-
ment: It asserts that there is a wide class of cryptographic problems (that amount to
proving the consistency of a secret-dependent action with respect to some public infor-
mation) that are solvable in principle. Thus, when faced with such a problem
in practice
,
one can infer that a solution does exist. This is merely a first step, to be followed by the
search for a practical solution.
Zero-Knowledge for Any Language in
IIP
Interestingly, the result of Theorem 4.4.11 can be extended “to the maximum,” in the
sense that under the same conditions every language having an interactive proof system
also has a zero-knowledge interactive proof system. Namely:
Theorem 4.4.12:
Suppose that there exists a commitment scheme satisfying the
(non-uniform) secrecy and unambiguity requirements. Then every language in
IP
has a zero-knowledge proof system.
We believe that this extension (of Theorem 4.4.11 to Theorem 4.4.12) does not have
much practical significance. Theorem 4.4.12 is proved by first converting the inter-
active proof for
L
into a public-coin interactive proof with perfect completeness (see
Section 4.2.3). In the latter proof system, the verifier is supposed to send random strings
(regardless of the prover's previous messages) and decide whether or not to accept by
applying some polynomial-time predicate to the full transcript of the communication.
Thus, we can modify this proof system by letting the new prover send commitments
to the messages sent by the original (public-coin-system) prover, rather than sending
these messages in the clear. Once this “encrypted” interaction is completed, the prover
proves in zero-knowledge that the original verifier would have accepted the hidden
transcript (this is an
NP
statement). Thus, Theorem 4.4.12 is proved by applying
Theorem 4.4.11.
4.4.4. Second-Level Considerations
When presenting zero-knowledge proof systems for every language in
, we made
no attempt to present the most efficient construction possible. Our main concern was
to present a proof that is as simple to explain as possible. However, once we know
that zero-knowledge proofs for
NP
NP
exist, it is natural to ask how efficient they can
243