Cryptography Reference
In-Depth Information
of the values. Furthermore, the choice of which commitments are to be opened
depends on the entire sequence of commitments. (We take advantage of the fact
that the number of such openings is a constant.)
Proof: Let m ( G ) denote the distribution of M ( G ) conditioned on M ( G )
=⊥
.
For any algorithm A , we denote the distinguishing gap of A , regarding the en-
sembles in the claim, by
ε A ( G ); that is,
Pr
1
A view P G 3 C
( G ) =
ε A ( G ) def
[ A ( m ( G ))
=
=
Pr
1]
(4.3)
V
Our goal is to prove that for every probabilistic polynomial-time algorithm A ,
the value of ε A ( G ) is negligible as a function of the number of vertices in G .
Recall that for G = ( V , E ) both m ( G ) and view P G 3 C
V ( G ) are sequences of the
form ( r , ( α 1 ,...,α | V | ) , ( u ,v ) , ( s u u , s v v )), where r ∈{ 0 , 1 }
q ( | V | ) ,( u ,v ) E ,
σ u = σ v ∈{ 1 , 2 , 3 } , α u = C s u ( σ u ), and α v = C s v ( σ v ). In both cases, the pair ( u ,v )
is called the verifier's request .
Given a graph G
E two random
variables describing, respectively, the output of M and the view of V in a real
interaction in the case in which the verifier's request equals ( u ,v ). Specifically:
µ u ,v ( G ) describes M ( G ) (equivalently, m ( G )) conditioned on M ( G ) (equiva-
lently, m ( G )) having the verifier's request equal to ( u
=
( V
,
E ), we define for each edge ( u
,v
)
,v
).
ν u ,v ( G ) describes view P G 3 C
( G ) conditioned on view P G 3 C
V
( G ) having the verifier's
V
).
Let p u ,v ( G ) denote the probability that m ( G ) has the verifier's request equal
to ( u
request equal to ( u
,v
). Similarly, let q u ,v ( G ) denote the probability that view P G 3 C
,v
( G ) has the
V
verifier's request equal to ( u
).
Assume, contrary to the claim, that the ensembles mentioned in the claim are
computationally distinguishable. Then one of the following cases must occur.
,v
Case 1: There is a non-negligible difference between the probabilistic profile of
the request of V when interacting with P G 3 C and that of the verifier's request in
the output represented by m ( G ). Formally, 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 ) and an edge ( u n ,v n )
E n such that
p u n ,v n ( G n )
q u n ,v n ( G n ) >
1
p ( n )
Otherwise, for every polynomial p , all but finitely many G 's, and all edges ( u ,v )
in such G = ( V , E ), it holds that
1
p ( | V | )
|
p u ,v ( G )
q u ,v ( G )
|≤
(4.4)
Case 2: An algorithm distinguishing the foregoing ensembles also does so con-
ditioned on V making a particular request. Furthermore, this request occurs with
non-negligible probability that is about the same for both ensembles. Formally,
there exists a probabilistic polynomial-time algorithm A , a polynomial p ( · ), and
235
Search WWH ::




Custom Search