Cryptography Reference
In-Depth Information
Adaptive soundness:
We say that
(
P
,
V
)
is
adaptively sound
if for every n and
poly(
n
)
n
poly(
n
)
every pair of functions
:
{
0
,
1
}
→
(
{
0
,
1
}
\
L
)
and
:
{
0
,
1
}
→
poly(
n
)
,
{
0
,
1
}
1
3
Pr
,
,
=
≤
[
V
(
(
R
)
R
(
R
))
1]
poly(
n
)
.
where R is a random variable uniformly distributed in
{
0
,
1
}
Adaptive zero-knowledge:
We say that
(
P
V
)
is
adaptively zero-knowledge
if
there exist two probabilistic polynomial-time algorithms M
1
and M
2
such that
for every function
,
poly(
n
)
n
:
{
0
,
1
}
→
(
{
0
,
1
}
∩
L
)
the ensembles
{
(
R
n
,
(
R
n
)
,
M
(1
n
)
P
(
}
n
∈N
are computationally indistinguishable,
where R
n
is a random variable uniformly distributed in
(
R
n
)
,
R
n
))
}
n
∈N
,
and
{
poly(
n
)
, and M
(1
n
)
{
0
,
1
}
denotes the output of the following randomized process:
1.
(
r
M
1
(1
n
)
,
s
)
←
←
2.
x
(
r
)
3.
π
←
M
2
(
x
,
s
)
4.
Output
(
r
)
(That is, M
1
generates a pair
(
r
,
x
,π
s
)
consisting of a supposedly common reference
string r and auxiliary information s to be used by M
2
. The latter, given an adaptively
selected input x and the auxiliary information s, generates an alleged proof
,
π
.We
stress that x can depend on r , but not on s.)
As usual, the error probability (in the adaptive-soundness condition) can be reduced
(from
3
)downto2
−
poly(
|
x
|
)
. Also, any non-interactive proof system (i.e., of non-adaptive
soundness) can be transformed into a system that is adaptively sound by merely reducing
the error probability and applying the union bound; that is, for every
:
{
0
,
1
}
poly(
n
)
→
n
poly(
n
)
poly(
n
)
,wehave
(
{
0
,
1
}
\
L
) and
:
{
0
,
1
}
→{
0
,
1
}
Pr
[
V
(
(
R
)
,
R
,
(
R
))
=
1]
≤
L
Pr
[
V
(
x
,
R
,
(
R
))
=
1]
x
∈{
0
,
1
}
n
\
2
n
≤
·
max
x
∈{
0
,
1
}
\
L
{
Pr
[
V
(
x
,
R
,
(
R
))
=
1]
}
n
In contrast to the foregoing trivial transformation (from non-adaptive to adaptive sound-
ness), we do not know of a simple transformation of non-interactive zero-knowledge
proofs into ones that are adaptively zero-knowledge. Fortunately, however, the exposi-
tion in Section 4.10.2 extends to the adaptive setting. (The key idea is that the reference
string in these proof systems can be generated obliviously of the common input.
29
)We
obtain the following:
Theorem 4.10.16:
Assuming the existence of one-way permutations,
30
each
NP
language
in
has
a
non-interactive
proof
system
that
is
adaptively
29
Specifically, this is obvious for the simulator presented in the proof of Proposition 4.10.9. We stress that
this simulator determines the values of all hidden bits independently of the common input (i.e., either they form a
random unuseful matrix or they are “effectively” all zeros). The simulator for the proof of Proposition 4.10.5 can
be easily modified to work for such hidden-bit model simulators.
30
See footnote 25.
