Cryptography Reference
In-Depth Information
We stress that the terminology just suggested is inconsistent with the exposition in
Section 4.4 (in which schemes such as in Definition 4.4.1 were referred to as “commit-
ment schemes,” without the extra qualification of “perfectly binding”).
20
Furthermore,
the terminology just suggested is inconsistent with significant parts of the literature, in
which a variety of terms can be found.
21
4.8.2.1. Definition
Loosely speaking, a perfectly hiding commitment scheme is an efficient
two-phase
two-party protocol through which the
sender
can commit itself to a
value
such that the
following two conflicting requirements are satisfied:
1.
(
Perfect
)
secrecy
(or
hiding
): At the end of the
commit phase
, the
receiver
does not gain
any
information
about the sender's value.
2.
Unambiguity
(or
binding
): It is infeasible for the sender to interact with the receiver, so
the commit phase is successfully terminated, and yet later it is feasible for the sender to
perform the
reveal phase
in two different ways, leading the receiver to accept (as legal
“openings”) two different values.
Using conventions analogous to those in Section 4.4.1, we state the following definition.
Again,
S
and
R
are the specified strategies of the commitment's sender and receiver,
respectively.
Definition 4.8.2 (Perfectly Hiding Bit-Commitment Scheme):
A
perfectly hid-
ing bit-commitment scheme
is a pair of probabilistic polynomial-time interac-
tive machines, denoted
(
S
,
R
)
, 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 (hiding):
For every probabilistic (not necessarily polynomial-time) ma-
chine R
∗
interacting with S, the random variables describing the output of R
∗
in the
two cases, namely
S
(0)
,
R
∗
(1
n
)
and
S
(1)
,
R
∗
(1
n
)
, are identically distributed.
Unambiguity (binding):
Preliminaries: For simplicity,
are
implicit in all notations. Fix any probabilistic polynomial-time algorithm F
∗
and
any polynomial p
(
v
∈{
0
,
1
}
and n
∈ N
)
.
1.
As in Definition 4.4.1, a
receiver's view of an interaction
with the sender, denoted
(
r
·
m
)
, consists of the random coins used by th
e r
eceiver (i.e., r ) and the sequence
of messages received from the sender (i.e., m). A
sender's view
of the same
interaction, denoted
(
s
,
m
)
, consists of the random coins used by the sender
(i.e., s) and the sequence of messages received from the receiver (i.e., m). A
joint view
of the interaction is a pair consisting of corresponding receiver and
sender views of the same interaction.
,
20
The extra qualification was omitted from the terminology of Section 4.4 in order to simplify the basic text.
21
For example, as in Section 4.4, many works refer to schemes such as in Definition 4.4.1 merely by the term
“commitment schemes,” and many refer to schemes such as in Definition 4.8.2 by the term “perfect commitment
schemes.” Furthermore, in some works the term “commitment schemes” means schemes such as in Definition 4.8.2.
