Cryptography Reference
In-Depth Information
σ
∈{
. The second commitment scheme is a perfectly hiding commitment
scheme (see Section 4.8.2). For simplicity, we assume that this scheme has a com-
mit phase in which the receiver sends one message to the sender, which then replies
with a single message (e.g., Construction 4.8.5). Let us denote by
P
m
,
s
(
1
,
2
,
3
}
α
) the (perfectly
hiding) commitment of the sender to the string
α
, upon receiving message
m
(from the
receiver) and when using coins
s
.
Construction 4.9.1 (A Round-Efficient Zero-Knowledge Proof for
G
3
C
):
def
=|
Common
input:
A
simple
(3-colorable)
graph
G
=
(
V
,
E
)
.
Let
n
V
|
,
def
=
t
n
·|
E
|
, and V
={
1
,...,
n
}
.
Auxiliary input to the prover:
A 3-coloring of G, denoted
ψ
.
Prover's preliminary step (P0):
The prover invokes the commit phase of the perfectly
hiding commitment scheme, which results in sending to the verifier a message m.
Verifier's preliminary s
tep
(V0):
The verifier uniformly and independently selects
a sequence of t edges, E
def
=
E
t
, and sends the prover a
ra
ndom commitment to these
e
dges. Namely, the verifier uniformly selects
s
((
u
1
,v
1
)
,...,
(
u
t
,v
t
))
∈
poly(
n
)
and sends P
m
,
s
(
E
)
to the prover.
∈{
0
,
1
}
Motivating remark:
At this point the verifier is committed (in a computational
sense) to a sequence of t edges. Because this commitment is of perfect secrecy, the
prover obtains no information about the edge sequence.
Prover's step (P1):
The prover uniformly and independently selects t permu-
tations,
)
def
π
1
,...,π
t
, over
{
1
,
2
,
3
}
and sets
φ
j
(
v
=
π
j
(
ψ
(
v
))
for each
v
∈
V
and
1
t . The prover uses the (perfectly binding, computationally hiding)
commitment scheme to commit itself to colors of each of the vertices accord-
ing to each 3-coloring. Namely, the prover uniformly and independently selects
s
1
,
1
,...,
≤
j
≤
n
, computes c
i
,
j
=
s
n
,
t
∈{
0
,
1
}
C
s
i
,
j
(
φ
j
(
i
))
for each i
∈
V and
1
≤
j
≤
t,
and sends c
1
,
1
,...,
c
n
,
t
to the verifier.
Verifier's step (V1):
The verifier
pe
rforms the (canonical) reveal phase of its com-
mitme
nt
,
yi
elding the sequence E
=
((
u
1
,v
1
)
,...,
(
u
t
,v
t
))
. Namely, the verifier
sends
(
s
,
E
)
to the prover.
Motivating remark:
At this point the entire commitment of the verifier is revealed.
The verifier now expects to receive, for each j , the colors assigned by the
j
th
coloring to vertices u
j
and
v
j
(the endpoints of the j th edge in the sequence E).
Prover's step (P2):
The prover checks that the message just received from the
verifier is indeed a valid revealing of the commitment made by the verifier at
Step
V0
. Otherwise the prover halts immediately. Let us denote the sequence of
t edges, just revealed, by
(
u
1
,v
1
)
(
u
t
,v
t
)
. The prover uses the (canonical)
reveal phase of the perfectly binding commitment scheme in order to reveal to the
verifier, for each j , the j th coloring of vertices u
j
and
,...,
v
j
. Namely, the prover sends
to the verifier the sequence of quadruples
s
u
1
,
1
,φ
1
(
u
1
)
v
1
)
,...,
s
u
t
,
t
,φ
t
(
u
t
)
v
t
)
,
s
v
1
,
1
,φ
1
(
,
s
v
t
,
t
,φ
t
(
Verifier's step (V2):
The verifier checks whether or not, for each j , the values in
the j th quadruple constitute a correct revealing of the commitments c
u
j
,
j
and c
v
j
,
j
and whether or not the corresponding values are different. Namely, upon receiving
