Cryptography Reference
In-Depth Information
language L is
unboundedly zero-knowledge
if for every polynomial p there
exists a probabilistic polynomial-time algorithm M such that the following two
ensembles are computationally indistinguishable:
1.
{
((
x
1
,...,
x
p
(
n
)
)
,
U
n
,
(
P
(
x
1
,
U
n
)
,...,
P
(
x
p
(
n
)
,
U
n
)))
}
x
1
,...,
x
p
(
n
)
∈
L
n
ε
2.
{
M
(
x
1
,...,
x
p
(
n
)
)
}
x
1
,...,
x
p
(
n
)
∈
L
n
ε
def
=
where L
L
∩{
0
,
1
}
.
We comment that the non-interactive proof systems presented earlier (e.g., Construc-
tion 4.10.4) are not unboundedly zero-knowledge; see Exercise 34.
We now turn to the construction of unboundedly zero-knowledge (non-interactive)
proof systems. The underlying idea is to facilitate the simulation by potentially prov-
ing a fictitious assertion regarding a portion of the common reference string. The as-
sertion that will be potentially proved (about this portion) will have the following
properties:
1.
The assertion holds for a negligible fraction of the strings of the same length. Thus,
adding this potential ability does not significantly affect the soundness condition.
2.
Strings satisfying the assertion are computationally indistinguishable from uniformly
distributed strings of the same length. Thus, it will be acceptable for the simulator to use
such strings, rather than uniformly chosen ones (used in the real proof system).
3.
The decision problem for the assertion is in
NP
. This will allow a reduction to an
NP
-complete problem.
An immediate assertion, concerning strings, that comes to mind is being produced by
a pseudorandom generator. This yields the following construction, where
G
denotes
such a generator.
Construction 4.10.12 (An Unboundedly Zero-Knowledge Non-Interactive
Proof System):
Let G
:
{
0
,
1
}
→{
0
,
1
}
2
, let L
1
be an
NP
-complete lan-
NP
NP
guage, let L be an arbitrary
language, and consider the following
language:
(
x
,
p
):
x
∈
L
def
={
∃
w
∈{
}
|
x
|
s.t.
G
(
w
)
L
2
0
,
1
=
p
}
Consider a standard reduction of L
2
to L
1
, and let q be a polynomial such that
3
-
bit-long instances of L
2
are mapped to q
(
)
-bit-long instances of L
1
. Let
(
P
,
V
)
be an ordinary non-interactive proof system for L
1
, and suppose that for some
polynomial q
the system
(
P
,
V
)
uses a common reference string of length q
(
)
for assertions of length q
(
-
witness for membership in L
1
, and let n
=
q
(
)
+
2
. Following is a specification
of a non-interactive proof system for L
)
. Suppose that P takes as auxiliary input an
NP
∈
NP
:
}
.
Common input:
x
∈{
0
,
1
2
and s
n
−
2
.
Common reference string:
r
=
(
p
,
s
)
, where p
∈{
0
,
1
}
∈{
0
,
1
}
