Cryptography Reference
In-Depth Information
(Recall that
p
u
,v
(
G
,
r
,
e
) denotes the probability that the verifier will ask
t
o inspect
(
u
) when given a sequence of random commitments to the values
e
.) Define
B
u
,v
to be the set of
n
-tuples (
e
1
,...,
,v
n
e
n
)
∈{
1
,
2
,
3
}
satisfying
e
u
=
e
v
. Clearly,
|
B
u
,v
|=
3
n
−
1
, and
n
&(
u
,v
)
∈
E
e
}={
(
e
,
(
u
,v
)) :
e
∈{
1
,
2
,
3
}
n
&
e
u
=
e
v
}
{
(
e
,
(
u
,v
)) :
e
∈{
1
,
2
,
3
}
={
(
e
,
(
u
,v
)):(
u
,v
)
∈
E
&
e
∈
B
u
,v
}
By straightforward calculation we get
1
3
n
·
[
M
r
(
G
)
Pr
=⊥
]
=
p
u
,v
(
G
,
r
,
e
)
n
(
u
,v
)
∈
E
e
e
∈{
1
,
2
,
3
}
1
3
n
·
=
p
u
,v
(
G
,
r
,
e
)
(
u
,v
∈
E
)
e
∈
B
u
,v
p
u
,v
(
G
,
r
,
1
3
n
·
1
2
|
E
|
≤
E
|
B
u
,v
|·
(1
,...,
1))
+
(
u
,v
)
∈
1
6
+
1
3
·
=
p
u
,v
(
G
,
r
,
(1
,...,
1))
(
u
,v
)
∈
E
1
3
where the inequality is due to Eq. (4.2). The claim follows.
1
6
+
=
For simplicity, we assume in the sequel that on common input
G
∈
G
3
C
the prover
gets the
lexicographically first
3-coloring of
G
as auxiliary input. This enables us to
omit the auxiliary input to
P
G
3
C
(which is now implicit in the common input) from
the notation. The argument is easily extended to the general case where
P
G
3
C
gets an
arbitrary 3-coloring of
G
as auxiliary input.
Claim 4.4.8.2:
The ensemble consisting of the output of
M
∗
on input
G
=
(
V
,
E
)
∈
G
3
C
, conditioned on it not being
⊥
, is computationally indistinguish-
able from the ensemble
view
P
G
3
C
}
G
∈
G
3
C
. Namely, for every probabilistic
polynomial-time algorithm
A
, every polynomial
p
(
{
(
G
)
V
∗
·
), and all sufficiently large
graphs
G
=
(
V
,
E
),
Pr
A
view
P
G
3
C
(
G
)
=
1
<
1
[
A
(
M
∗
(
G
))
=
1
|
M
∗
(
G
)
= ⊥
]
−
Pr
V
∗
)
We stress that these ensembles are very different (i.e., the statistical distance
between them is very close to the maximum possible), and yet they are com-
putationally indistinguishable. Actually, we can prove that these ensembles are
indistinguishable also by (non-uniform) families of polynomial-size circuits. At
first glance it seems that Claim 4.4.8.2 follows easily from the secrecy property
of the commitment scheme. Indeed, Claim 4.4.8.2 is proved using the secrecy
property of the commitment scheme, but the proof is more complex than one
might anticipate at first glance. The difficulty lies in the fact that the foregoing
ensembles consist not only of commitments to values but also of openings of
some
234
p
(
|
V
|
