Cryptography Reference
In-Depth Information
n
, it holds that
every two sequences
α,β
∈{
1
,
2
,
3
}
1
p
(
n
)
|
p
u
,v
(
G
,
r
,α
)
−
p
u
,v
(
G
,
r
,β
)
|≤
The Request Obliviousness Sub-Claim is proved using the non-uniform secrecy
of the commitment scheme. The reader should be able to fill out the details of
such a proof at this stage. (Nevertheless, a proof of the sub-claim follows.)
Proof of the Request Obliviousness Sub-Claim:
Assume, on the contrary, that
there exists a polynomial
p
(
·
) and an infinite sequence of integers such that for each
integer
n
(in the sequence) there exists an
n
-vertex graph
G
n
=
(
V
n
,
E
n
), a string
q
(
n
)
, an edge (
u
n
,v
n
)
∈
E
n
, and two sequences
α
n
,β
n
∈{
1
,
2
,
3
}
n
r
n
∈{
0
,
1
}
such that
p
u
n
,v
n
(
G
n
,
r
n
,β
n
)
>
1
p
(
n
)
We construct a circuit family
{
A
n
}
by letting
A
n
incorporate the interactive machine
V
∗
,
the graph
G
n
, and
r
n
,
r
n
,α
n
)
−
p
u
n
,v
n
(
G
n
,
u
n
,v
n
,α
n
,β
n
, all being as in the contradiction hypothesis. On
input
y
(supposedly a sequence of commitments to either
β
n
), circuit
A
n
runs
V
∗
(on input
G
n
, coins
r
n
, and prover's message
y
) and outputs 1 if and only if
V
∗
replies
with (
u
n
,v
n
). Clearly,
α
n
or
is a (non-uniform) family of polynomial-size circuits. The
key observation is that
A
n
distinguishes commitments to
α
n
from commitments to
β
n
,
since
{
A
n
}
Pr
A
n
C
U
(1)
n
(
e
n
)
=
1
=
e
n
))
where the
U
(
i
n
's denote, as usual, independent random variables uniformly distributed
over
{
0
,
1
}
(
e
1
)
,...,
C
U
(
n
)
n
p
u
n
,v
n
(
G
n
,
r
n
,
(
e
1
,...,
n
. Contradiction to the (non-uniform) secrecy of the commitment scheme
follows by a standard hybrid argument (which relates the indistinguishability of se-
quences of commitments to the indistinguishability of single commitments).
Returning to the proof of Claim 4.4.8.1, we now use this sub-claim to upper-bound
the probability that the simulator outputs
. The intuition is simple: Because the
requests of
V
∗
are almost oblivious of the values to which the simulator has
committed itself, it is unlikely that
V
∗
will request to inspect an illegally colored
edge more often than it would if it had made the request without looking at the
commitment. Thus,
V
∗
asks to inspect an illegally colored edge with probability
approximately
⊥
1
Pr
[
M
∗
(
G
)
=⊥
]
≈
1
3
, and so
3
. A more rigorous (but straightfor-
ward) analysis follows.
Let
M
r
(
G
) denote the output of machine
M
∗
on input
G
, conditioned on the
event that it chooses the string
r
in Step 1. We remind the reader that
M
r
(
G
)
=⊥
only in the case in which the verifier, on input
G
, random tape
r
, and a commitment
to some pseudo-coloring (
e
1
,...,
e
n
), asks to inspect an edge (
u
,v
) that is illegally
colored (i.e.,
e
u
=
e
v
). Let
E
(
e
1
,...,
e
n
)
denote the set of edges (
u
,v
∈
E
that are
illegally colored (i.e., satisfy
e
u
=
e
v
) with respect to (
e
1
,...,
e
n
). Then, fixing an
arbitrary
r
and considering all possible choices of
e
)
=
(
e
1
,...,
e
n
)
∈{
1
,
2
,
3
}
n
,
we have
1
3
n
·
Pr
[
M
r
(
G
)
=⊥
]
=
p
u
,v
(
G
,
r
,
e
)
e
∈{
1
,
2
,
3
}
n
(
u
,v
)
∈
E
e
