Cryptography Reference
In-Depth Information
1.
Secrecy
(or
hiding
): At the end of the first phase, the other party, called the
receiver
, does
not gain any knowledge of the sender's value. This requirement has to be satisfied even
if the receiver tries to cheat.
2.
Unambiguity
(or
binding
): Given the transcript of the interaction in the first phase, there
exists at most one value that the receiver can later (i.e., in the second phase) accept as
a legal “opening” of the commitment. This requirement has to be satisfied even if the
sender tries to cheat.
In addition, one should require that the protocol be
viable
, in the sense that if both parties
follow it, then at the end of the second phase the receiver gets the value committed to
by the sender. The first phase is called the
commit phase
, and the second phase is
called the
reveal phase
. We are requiring that the commit phase yield no knowledge
(at least no knowledge of the sender's value) to the receiver, whereas the commit phase
does “bind” the sender to a unique value (in the sense that in the reveal phase the
receiver can accept only this value). We stress that the protocol is efficient in the sense
that the predetermined programs of both parties can be implemented in probabilistic
polynomial time. Without loss of generality, the reveal phase may consist of merely
letting the sender send, to the receiver, the original value and the sequence of random
coin tosses that it has used during the commit phase. The receiver will accept the value
if and only if the supplied information matches its transcript of the interaction in the
commit phase. The latter convention leads to the following definition (which refers
explicitly only to the commit phase).
Definition 4.4.1 (Bit-Commitment Scheme):
A
bit-commitment scheme
is a
pair of probabilistic polynomial-time interactive machines, denoted
(
S
,
R
)(
for
sender
and
receiver)
, satisfying the following:
Input specification:
The
common input
is an integer n presented in unary (serving
as the security parameter).
The
private input
to the sender is a bit, denoted
v
.
Secrecy (or hiding):
The receiver (even when deviating arbitrarily from the pro-
tocol) cannot distinguish a commitment to
0
from a commitment to
1
. Namely, for
every probabilistic polynomial-time machine R
∗
interacting with S, the probability
ensembles describing the output of R
∗
in the two cases, namely
{
S
(0)
,
R
∗
(1
n
)
}
n
∈N
R
∗
(1
n
)
and
{
S
(1)
,
}
n
∈N
, are computationally indistinguishable.
Unambiguity (or binding):
Preliminaries to the requirement
:
1.
A receiver's view of an interaction
with the sender, denoted
(
r
m
)
, consists
of the random coins used by the receiver
(
r
)
and the sequence of messages
received from the sender
(
m
)
.
2.
Let
,
σ
∈{
0
,
1
}
. We say that a receiver's view (of such intera
cti
on),
(
r
,
m
)
,is
a
possible
-commitment
if there exists a string s such that m describes the
messages received by R when R uses local coins r and interacts with machine
S that uses local coins s and has input
(
σ
1
n
)
.
(Using the not
ati
on of Definition 4.3.3, we say that
(
r
σ,
,
m
)
is a
possible
σ
-
view
S
(
σ,
1
n
,
s
)
commitment
if
(
r
,
m
)
=
.)
R
(1
n
,
r
)
