Cryptography Reference
In-Depth Information
1.
Setting the random tape of V
∗
: Let
q
(
·
) denote a polynomial bounding the running time
of
V
∗
. The simulator
M
∗
starts by uniformly selecting a string
r
q
(
n
)
∈{
0
,
1
}
to be used
as the content of the local random tape of
V
∗
.
2.
Simulating the prover's first step
(P1): The simulator
M
∗
uniformly and independently
selects
n
values
e
1
,...,
n
to be used
e
n
∈{
1
,
2
,
3
}
and
n
random strings
s
1
,...,
s
n
∈{
0
,
1
}
for committing to these values. The simulator computes, for each
i
∈
V
, a commitment
C
s
i
(
e
i
).
3.
Simulating the verifier's first step
(V1): The simulator
M
∗
initiates an execution of
V
∗
by placing
G
on
V
∗
's common-input tape, placing
r
(selected in Step 1) on
V
∗
's
local random tape, and placing the sequence (
d
1
,...,
d
i
=
d
n
) (constructed in Step 2) on
V
∗
's incoming-message tape. After executing a polynomial number of steps of
V
∗
, the
simulator can read the outgoing message of
V
∗
, denoted
m
. Again, we assume without
loss of generality that
m
∈
E
and let (
u
,v
)
=
m
. (Actually,
m
∈
E
is treated as in Step P2
) is set to be some predetermined edge of
G
.)
4.
Simulating the prover's second step
(P2): If
e
u
=
of
P
G
3
C
; namely, (
u
,v
e
v
, then the simulator halts with output
e
v
)).
5.
Failure of the simulation:
Otherwise (i.e.,
e
u
=
(
G
,
r
,
(
d
1
,...,
d
n
)
,
(
s
u
,
e
u
,
s
v
,
e
v
), the simulator halts with output
⊥
.
Using the hypothesis that
V
∗
is polynomial-time, it follows that so is the simulator
M
∗
.
It is left to show that
M
∗
outputs
1
2
⊥
with probability at most
and that, conditioned on
not outputting
, the simulator's output is computationally indistinguishable from the
verifier's view in a “real interaction with
P
G
3
C
.” The proposition will follow by running
the simulator
n
times and outputting the first output different from
⊥
⊥
. We now turn to
proving the two claims.
Claim 4.4.8.1:
For every sufficiently large graph
G
=
(
V
,
E
), the probability
1
that
M
∗
(
G
)
2
.
(Actually, a stronger claim can be proved: For every polynomial
p
and all
sufficiently large graphs
G
=⊥
is bounded above by
=
(
V
,
E
), the probability that
M
∗
(
G
)
=⊥
is bounded
1
3
1
above by
+
)
.)
p
(
|
V
|
Proof:
Let us denote by
p
u
,v
(
G
,
r
,
(
e
1
,...,
e
n
)) the probability, taken over all the
choices of
s
1
,...,
s
n
∈{
0
,
1
}
n
, that
V
∗
, on input
G
, random coins
r
, and prover
message (
C
s
1
(
e
1
)
,...,
C
s
n
(
e
n
)), replies with the message (
u
,v
). We assume, for
simplicity, that
V
∗
always answers with an edge of
G
(since otherwise its message
is treated as if it were an edge of
G
). We first claim that for every sufficiently
large graph
G
=
(
V
,
E
), every
r
∈{
,
}
q
(
n
)
, every edge (
u
,v
∈
E
, and every
0
1
)
two sequences
α,β
∈{
1
,
2
,
3
}
n
, it holds that
1
|
p
u
,v
(
G
,
r
,α
)
−
p
u
,v
(
G
,
r
,β
)
|≤
(4.2)
2
|
E
|
Actually, we can prove the following sub-claim.
Request Obliviousness Sub-Claim:
For every polynomial
p
(
·
), every suffi-
q
(
n
)
, every edge (
u
,v
)
∈
E
, and
ciently large graph
G
=
(
V
,
E
), every
r
∈{
0
,
1
}
