Cryptography Reference
In-Depth Information
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
) and an edge (
u
n
,v
n
)
∈
E
n
such that the
following conditions hold:
1
p
(
n
)
|
p
u
n
,v
n
(
G
n
)
−
q
u
n
,v
n
(
G
n
)
|
<
q
u
n
,v
n
(
G
n
)
>
1
3
·
p
(
n
)
2
|Pr
[
A
(
µ
u
n
,v
n
(
G
n
))
=
1]
− Pr
[
A
(
ν
u
n
,v
n
(
G
n
))
=
1]
|
>
1
p
(
n
)
The fact that if Case 1 does not hold, then Case 2 does hold follows by breaking
the probability space according to the edge being revealed. The obvious details
follow:
Consider an algorithm
A
that distinguishes the simulator's output from the real in-
teraction for infinitely many graphs
G
=
(
V
,
E
), where the distinguishing gap is a
reciprocal of a polynomial in the size of
G
; i.e.,
ε
A
(
G
)
>
1
/
poly(
|
V
|
). Let req
u
,v
(
α
)
denote the event that
in transcript
α
, the verifier's request equals
(
u
,v
). Then there
must be an edge (
u
)in
G
such that
Pr
[
A
(
m
∗
(
G
))
=
1 & req
u
,v
(
m
∗
(
G
))]
−
Pr
A
view
P
G
3
C
V
∗
,v
(
G
)
=
1 & req
u
,v
view
P
G
3
C
(
G
)
≥
ε
A
(
G
)
|
E
|
V
∗
Note that
[req
u
,v
(
m
∗
(
G
))]
p
u
,v
(
G
)
=
Pr
V
∗
(
G
)
Pr
[
A
(
µ
u
,v
(
G
))
=
1]
=
Pr
[
A
(
m
∗
(
G
))
=
1
|
req
u
,v
(
m
∗
(
G
))]
Pr
[
A
(
ν
u
,v
(
G
))
=
1]
=
Pr
A
view
P
G
3
C
V
∗
=
Pr
req
u
,v
view
P
G
3
C
q
u
,v
(
G
)
(
G
)
=
1
req
u
,v
view
P
G
3
C
(
G
)
V
∗
Thus, omitting
G
from some of the notations, we have
|≥
ε
A
(
G
)
|
|
p
u
,v
·
Pr
[
A
(
µ
u
,v
(
G
))
=
1]
−
q
u
,v
·
Pr
[
A
(
ν
u
,v
(
G
))
=
1]
E
|
)
def
|
ε
A
(
G
)
2
|
E
(i.e., so that
ε
A
(
G
)
p
(
|
V
|
)
) and using Eq. (4.4) (with
p
=
2
Setting
p
(
|
V
|
=
|
E
|
=
1
3
p
(
|
V
|
)
2
and
3
p
2
), we get
|
p
u
,v
−
q
u
,v
|
<
1
|
q
u
,v
·
Pr
[
A
(
µ
u
,v
(
G
))
=
1]
−
q
u
,v
·
Pr
[
A
(
ν
u
,v
(
G
))
=
1]
|
>
p
(
|
V
|
)
for all but finitely many of these
G
's. Thus, both
q
u
,v
>
1
/
p
(
|
V
|
) and
|
Pr
[
A
(
µ
u
,v
(
G
))
=
1]
−
Pr
[
A
(
ν
u
,v
(
G
))
=
1]
|
>
1
/
p
(
|
V
|
)
follow.
Case 1 can immediately be discarded because it leads easily to contradiction
(to the non-uniform secrecy of the commitment scheme): The idea is to use the
Request Obliviousness Sub-Claim appearing in the proof of Claim 4.4.8.1. Details
are omitted. We are thus left with Case 2.
We are now going to show that Case 2 also leads to contradiction. To this
end we shall construct a circuit family that will distinguish commitments to
different sequences of values. Interestingly, neither of these sequences will equal
236
