Cryptography Reference
In-Depth Information
the sequence of commitments generated either by the prover or by the simulator.
Following is an overview of the construction. The
n
th circuit gets a sequence
of 3
n
commitments and produces from it a sequence of
n
commitments (part of
which is a subsequence of the input). When the input sequence to the circuit is
taken from one distribution, the circuit generates a subsequence corresponding
to the sequence of commitments generated by the prover. Likewise, when the
input sequence (to the circuit) is taken from the other distribution, the circuit will
generate a subsequence corresponding to the sequence of commitments generated
by the simulator. We stress that the circuit does so without knowing from which
distribution the input is taken. After generating an
n
-long sequence, the circuit
feeds it to
V
∗
, and depending on
V
∗
's behavior the circuit may feed part of the
sequence to algorithm
A
(mentioned in Case 2). Following is a detailed description
of the circuit family.
Let us denote by
ψ
n
the (lexicographically first) 3-coloring of
G
n
=
(
V
n
,
E
n
)
used by the prover, where
V
n
={
1
,...,
n
}
. We construct a circuit family, denoted
{
, by letting
A
n
incorporate the interactive machine
V
∗
, the “distinguishing”
algorithm
A
, the graph
G
n
, the 3-coloring
A
n
}
ψ
n
, and the edge (
u
n
,v
n
), all being
as guaranteed in Case 2. The input to circuit
A
n
will be a sequence of commit-
ments to 3
n
values, each in
. The circuit will distinguish commitments to
a uniformly chosen 3
n
-long sequence from commitments to the fixed sequence
1
n
2
n
3
n
(i.e., the sequence consisting of
n
1-values, followed by
n
2-values, fol-
lowed by
n
3-values). Following is a description of the operation of
A
n
. In this
description, for
e
{
1
,
2
,
3
}
∈{
1
,
2
,
3
}
, we denote by
C
(
e
) the random variable obtained by
n
and outputting
C
s
(
e
). We extend this notation to
sequences over
{
1
,
2
,
3
}
(i.e.,
C
(
e
1
,...,
e
t
)
=
C
(
e
1
)
,...,
C
(
e
t
), where indepen-
dent randomization is used in each commitment).
uniformly selecting
s
∈{
0
,
1
}
Operation of A
n
:
On input
y
y
3
n
) (where each
y
i
supposedly is a
commitment to an element of
{
1
,
2
,
3
}
), the circuit
A
n
proceeds as follows:
=
(
y
1
,...,
A
n
first selects uniformly a permutation
π
over
{
1
,
2
,
3
}
and computes
φ
(
i
)
=
π
(
ψ
n
(
i
)) for each
i
∈
V
n
.
φ
,φ
v
n
)) is uniformly distributed among the six possible pairs
Note that (
(
u
n
)
(
of distinct elements of
{
1
,
2
,
3
}
.
For each
i
∈
V
n
\{
u
n
,v
n
}
, the circuit sets
c
i
=
y
φ
(
i
)
·
n
−
n
+
i
(i.e.,
c
i
=
y
i
if
φ
(
i
)
=
1,
c
i
=
3).
Note that each
y
j
is used at most once and that 2
n
y
n
+
i
if
φ
(
i
)
=
2, and
c
i
=
y
2
n
+
i
if
φ
(
i
)
=
+
2ofthe
y
j
's are not used
at all.
n
and sets
c
u
n
=
The circuit uniformly selects
s
u
n
,
s
v
n
∈{
0
,
1
}
C
s
u
n
(
φ
(
u
n
)) and
c
v
n
=
C
s
v
n
(
v
n
)).
In case
y
is taken from the distribution
C
(1
n
2
n
3
n
), the sequence
c
1
,...,
φ
(
c
n
just
formed is distributed exactly as the sequence of commitments sent by the prover
in Step P1. On the other hand, suppose that
y
is uniformly distributed among all
possible commitments to all possible 3
n
-long sequences (i.e.,
y
is formed by uni-
formly selecting
3
n
and outputting
C
(
c
n
just formed is distributed exactly as the sequence of commitments formed by the
α
∈{
1
,
2
,
3
}
α
)). Then the sequence
c
1
,...,
