Cryptography Reference
In-Depth Information
We remark that
P
is not perfect zero-knowledge even in case
P
is. Also,
P
cannot be
implemented in polynomial-time (even with the help of auxiliary inputs) even if
P
is
(see the following Remark 4.10.6).
Proof Sketch:
To see that (
P
,
V
) is a non-interactive proof system for
L
,we
note that uniformly chosen
s
i
∈{
0
,
1
}
n
induce uniformly distributed bits
r
i
∈
{
0
,
1
}
. This follows from
r
i
=
b
(
f
−
1
(
s
i
)), the fact that
f
is 1-1, and the fact
that
b
(
f
−
1
(
U
n
))
b
(
U
n
) is unbiased. (Note that in case
b
is a hard-core of
f
,
it is almost unbiased (i.e.,
≡
1
2
is a negligible
function). Thus, saying that
b
is a hard-core for
f
essentially suffices.)
To see that
P
is zero-knowledge, note that we can convert an efficient simulator
for
P
into an efficient simulator for
P
. Specifically, for each revealed bit of value
σ
Pr
[
b
(
U
n
)
=
1]
=
±
µ
(
n
), where
µ
n
such that
b
(
r
)
and put
f
(
r
) in the
corresponding position in the common reference string. For each
unrevealed
bit,
we uniformly select a string
s
, we uniformly select a string
r
∈{
0
,
1
}
=
σ
n
and put it in the corresponding position
in the common reference string. The output of the
P
simulator consists of the
common reference string generated as before, all the
r
's generated by the
P
simulator for bits revealed by the
P
simulator, and the output of the
P
simulator.
Using the fact that
b
is a hard-core of
f
, it follows that the output of the
P
simulator is computationally indistinguishable from the verifier's view (when
receiving a proof from
P
).
∈{
0
,
1
}
Remark 4.10.6 (Efficient Implementation of
P
).
As stated earlier, in general,
P
cannot be efficiently implemented given black-box access to
P
. What is needed is the
ability (of
P
)toinvert
f
. On the other hand, for
P
to be zero-knowledge,
f
must
be one-way. The obvious solution is to use a family of trapdoor permutations and let
the prover know the trapdoor. Furthermore, the family should have the property that
its members can be efficiently recognized (i.e., given a description of a function, one
can efficiently decide whether or not it is in the family). In other words,
P
starts by
selecting a permutation
f
over
n
such that it knows its trapdoor and proceeds as
in Construction 4.10.4, except that it also appends the description of
f
to the “proof.”
The verifier acts as in Construction 4.10.4 with respect to the function
f
specified in the
proof. In addition, it checks to see that
f
is indeed in the family. Both the completeness
and the zero-knowledge conditions follow exactly as in the proof of Proposition 4.10.5.
For the soundness condition, we need to consider all possible members of the family
(without loss of generality, there are at most 2
n
such permutations). For each such
permutation, the argument is as before, and our claim thus follows by a counting argu-
ment (as applied in Section 4.10.3.2).
23
{
0
,
1
}
The construction can be extended to arbitrary
trapdoor permutations; details omitted.
We now turn to the construction of proof systems in the Hidden-Bits model. Specifi-
cally, we are going to construct a proof system for the
Hamiltonian-Cycle (HC)
problem
that is
NP
NP
-complete (and thus get proof systems for any language in
). We consider
23
Actually, we also need to repeat the (
P
,
V
) system
O
(
n
) times, so as first to reduce the soundness error to
1
3
·
2
−
n
.
