Cryptography Reference
In-Depth Information
interactive proof, with negligible error probability, for the corresponding language.
16
Clearly the resulting proof systems are constant-round and use public coins. Hence,
unless the corresponding languages are in
BPP
, these resulting proof systems
are not
black-box zero-knowledge.
Theorem 4.5.11 is sometimes interpreted as pointing to an inherent limitation of
interactive proofs with public coins (also known as
Arthur-Merlin
games). Such proofs
cannot be both
round-efficient
(i.e., have constant number of rounds and negligible
error) and black-box zero-knowledge (unless they are trivially so, i.e., the language
is in
BPP
). In other words,
when constructing round-efficient zero-knowledge proof
systems
(for languages not in
BPP
),
one should use “private coins”
(i.e., let the verifier
send messages depending upon, but not revealing, its coin tosses). This is indeed the
approach taken in Section 4.9.
4.6.
∗
Witness Indistinguishability and Hiding
In light of the non-closure of zero-knowledge under parallel composition (see
Section 4.5.4), alternative “privacy” criteria that are preserved under parallel composi-
tion are of practical and theoretical importance. Two notions, called witness indistin-
guishability and witness hiding, that refer to the “privacy” of interactive proof systems
(of languages in
NP
) are presented in this section. Both notions seem weaker than zero-
knowledge, yet they suffice for some specific applications.
We remark that witness indistinguishability and witness hiding, like zero-knowledge,
are properties of the prover (and, more generally, of any interactive machine).
4.6.1. Definitions
In this section we confine ourselves to proof systems for languages in
NP
. Recall that
a
witness relation
for a language
L
∈
NP
is a binary relation
R
L
that is polynomially
bounded (i.e., (
x
,
y
)
∈
R
L
implies
|
y
|≤
poly(
|
x
|
)), is polynomial-time-recognizable
and characterizes
L
by
L
={
x
:
∃
y
s.t. (
x
,
y
)
∈
R
L
}
For
x
∈
L
,any
y
satisfying (
x
,
y
)
∈
R
L
is called a
witness
(for the membership
x
∈
L
).
We let
R
L
(
x
) denote the set of witnesses for the membership
x
L
; that is,
R
L
(
x
)
def
∈
=
{
y
:(
x
,
y
)
∈
R
L
}
.
16
In fact, a super-logarithmic number of repetitions will suffice in the case of Construction 4.3.8, as well as
for a modified version of Construction 4.4.7. The modified proof system invokes Construction 4.4.7 on the graph
resulting from the input graph by applying a special polynomial-time reduction that is guaranteed by the so-called
PCP theorem. Specifically, this reduction reduces
G
3
C
to itself, so that non-members of
G
3
C
are mapped into
graphs for which every three-way partition of the vertex set has at least a constant fraction of violating edges (i.e.,
edges with both endpoints on the same side of the partition). Let
0 be the constant guaranteed by the PCP
theorem. Then the resulting proof system has perfect completeness and soundness error at most 1
−
ε
, and so a
super-logarithmic number of repetitions will yield negligible error probability.
ε>
