Cryptography Reference
In-Depth Information
and
(
x
,
r
) are identically distributed for every
x
and
r
. Observe that once
r
is
fixed, the message sent by
V
∗
, on common input
x
, random tape
r
, and incoming
message
H
, is uniquely defined. Let us denote this message by
µ
v
∗
(
x
,
r
,
H
). We
show that both
ν
(
x
,
r
) and
µ
(
x
,
r
) are uniformly distributed over the set
=
(
H
,ψ
):
H
=
ψ
G
v
∗
(
x
,
r
,
H
)
def
C
x
,
r
where (again)
ψ
(
G
) denotes the graph obtained from
G
by relabeling the vertices
using the permutation
ψ
(i.e., if
G
=
(
V
,
E
), then
ψ
=
(
V
,
F
), so that (
u
,v
∈
(
G
)
)
E
iff (
∈
F
). The proof of this statement is rather tedious and is
unrelated to the subjects of this topic (and hence can be skipped with no damage).
ψ
(
u
)
,ψ
(
v
))
The proof is slightly non-trivial because it relates (at least implicitly) to the automor-
phism group of the graph
G
2
(i.e., the set of permutations
(
G
2
) is identical
with
G
2
, not just isomorphic to
G
2
). For simplicity, consider first the special case in
which the automorphism group of
G
2
consists of merely the identity permutation (i.e.,
G
2
=
π
(
G
2
) if and only if
π
is the identity permutation). In this case, (
H
,ψ
)
∈
C
x
,
r
if and only if
H
is isomorphic to (both
G
1
and)
G
2
and
π
for which
π
ψ
is the (unique) isomorphism
|
V
2
|
between
H
and
G
v
∗
(
x
,
r
,
H
)
. Hence,
C
x
,
r
contains exactly
! pairs, each containing a
different graph
H
as the first element. In the general case, (
H
,ψ
)
∈
C
x
,
r
if and only
if
H
is isomorphic to (both
G
1
and)
G
2
and
ψ
is an isomorphism between
H
and
v
∗
(
x
G
v
∗
(
x
,
r
,
H
)
. We stress that
H
) is the same in all pairs containing
H
. Let aut(
G
2
)
denote the size of the automorphism group of
G
2
. Then each
H
(isomorphic to
G
2
)
appears in exactly aut(
G
2
) pairs of
C
x
,
r
, and each such pair contains a different iso-
morphism between
H
and
G
v
∗
(
x
,
r
,
H
)
. The number of different
H
's that are isomorphic
to
G
2
is
|
V
2
|
!
/
aut(
G
2
), and so
|
C
x
,
r
|=|
V
2
|
! also in the general case.
We first consider the random variable
,
r
,
r
) (describing the suffix of
m
∗
(
x
)). Re-
call that
µ
(
x
,
r
) is defined by the following two-step random process. In the
first
step,
one selects uniformly a pair (
µ
(
x
,
permutation), and sets
H
=
ψ
(
G
τ
). In the
second
step, one outputs (i.e., sets
µ
(
x
,
r
) to) (
ψ
(
G
τ
)
,ψ
)if
v
∗
(
x
τ,ψ
), over the set of pairs (
{
1
,
2
}×
) pair otherwise). Hence, each graph
H
(iso-
morphic to
G
2
) is generated, at the first step, by exactly aut(
G
2
) different (1
,
r
,
H
)
=
τ
(and ignores the (
τ,ψ
,
·
)-pairs
(i.e., the pairs (1
,ψ
) satisfying
H
=
ψ
(
G
1
)) and by exactly aut(
G
2
) different (2
,
·
)-
pairs (i.e., the pairs (2
aut(
G
2
) pairs yield the
same graph
H
and hence lead to the same value of
v
∗
(
x
,
r
,
H
). It follows that out of the
2
,ψ
) satisfying
H
=
ψ
(
G
2
)). All these 2
·
(
G
τ
), only the aut(
G
2
)
pairs satisfying
τ
=
v
∗
(
x
,
r
,
H
) lead to an output. Hence, for each
H
(that is isomor-
phic to
G
2
), the probability that
·
aut(
G
2
) pairs of the form (
τ,ψ
) that yield the graph
H
=
ψ
µ
(
x
,
r
)
=
(
H
,
·
) equals aut(
G
2
)
/
(
|
V
2
|
!). Furthermore,
for each
H
(that is isomorphic to
G
2
),
1
|
V
2
|
!
=
ψ
G
v
∗
(
x
,
r
,
H
)
if
H
Pr
[
µ
(
x
,
r
)
=
(
H
,ψ
)]
=
0
otherwise
(
x
,
r
) is uniformly distributed over
C
x
,
r
.
We now consider the random variable
µ
Hence
r
) (describing the suffix of the veri-
fier's view in a “real interaction” with the prover). Recall that
ν
(
x
,
ν
(
x
,
r
) is defined by
selecting uniformly a permutation
π
(over the set
V
2
) and setting
ν
(
x
,
r
)
=
(
π
(
G
2
)
,π
)
v
∗
(
x
if
is the iso-
morphism between
G
1
and
G
2
. Clearly, for each
H
(that is isomorphic to
G
2
), the
probability that
,
r
,π
(
G
2
))
=
2, and
ν
(
x
,
r
)
=
(
π
(
G
2
)
,π
◦
φ
) otherwise, where
φ
ν
(
x
,
r
)
=
(
H
,
·
) equals aut(
G
2
)
/
(
|
V
2
|
!). Furthermore, for each
H
(that
