Cryptography Reference
In-Depth Information
known to everybody because they were sent over a broadcast
channel). Furthermore, the sender's input is determined by
its commitment (as sent in Step 1), and its random-input
is similarly determined (in Step 2). Thus, the next message
(as determined by the original protocol) is a function of pub-
licly known strings (i.e., the said commitments as well as the
other messages sent over the broadcast channel). Moreover,
the assertion that the next message was indeed computed
correctly is an NP-assertion, and the sender knows a corre-
sponding NP-witness (i.e., its own input and random-input as
well as the corresponding decommitment information). Thus,
the sender can prove in zero-knowledge (to each of the other
parties) that the message it is sending was indeed computed
according to the original protocol.
The above compilation was first outlined in (75; 74). A detailed
description and full proofs appear in (63; 67).
A secure coin-tossing protocol.
Using a commitment scheme
(see Section 4.3), we outline a secure (ordinary as opposed to aug-
mented) coin-tossing protocol, which originates in (28).
Step C1
:
Party 1 uniformly selects
σ
∈{
0
,
1
}
and sends Party 2 a
commitment, denoted
c
,to
σ
.
Step C2
:
Party 2 uniformly selects
σ
∈{
0
,
1
}
, and sends
σ
to
Party 1.
Step C3
σ
, and sends
σ
along with
the decommitment information, denoted
d
, to Party 2.
Step C4
:
Party 1 outputs the value
σ
⊕
:
Party 2 checks whether or not (
σ, d
) fit the commitment
c
it
has obtained in Step 1. It outputs
σ
σ
if the check is satisfied
and halts with output
⊥
otherwise (indicating that Party 1 has
essentially aborted the protocol prematurely).
Outputs: Party 1 always outputs
b
de
=
σ
⊕
σ
, whereas Party 2 either
⊕
outputs
b
or
⊥
.
Intuitively, Steps C1-C2 may be viewed as “tossing a coin into the
well”. At this point (i.e., after Step C2) the value of the coin is deter-
