Cryptography Reference
In-Depth Information
,
3.
We say that the receiver's view
(
r
m
)
is
ambiguous
if it is both a possible
0
-commitment and a possible
1
-commitment.
The
unambiguity requirement
asserts that for all but a negligible fraction of the
coin tosses of the receiver there exists no sequence of messages (from the sender)
that together with these coin tosses forms an ambiguous receiver view. Namely,
for all but a negligible fraction of the r
poly(
n
)
there is no m such that
(
r
∈{
0
,
1
}
,
m
)
is ambiguous.
The secrecy requirement is a computational one. On the other hand, the
unambiguity
requirement
has an information-theoretic flavor (i.e., it does not refer to computational
powers) and is sometimes referred to as
perfect
(or
absolute
). Thus, a commitment
scheme as in Definition 4.4.1 is sometimes referred to as
computationally hiding
and
perfectly binding
. A dual definition, requiring information-theoretic secrecy and com-
putational infeasibility of creating ambiguities, is presented in Section 4.8.2. (The latter
is referred to as
perfectly hiding
and
computationally binding
.)
Canonical Reveal Phase.
The secrecy requirement refers explicitly to the situation
at the end of the commit phase. On the other hand, we stress that the unambiguity
requirement implicitly assumes that the reveal phase takes the following form:
1.
The sender sends to the receiver its initial private input
v
and the random coins
s
it has
used in the commit phase.
2.
The receiver verifies that
and
s
(together with the coins (
r
) used by
R
in the commit
phase) indeed yield the messages that
R
has received in the commit phase. Verification
is done in polynomial time (by running the programs
S
and
R
).
v
Note that the viability requirement (i.e., asserting that if both parties follow the proto-
col, then at the end of the reveal phase the receiver gets
v
) is implicitly satisfied by this
convention.
4.4.1.2. Construction Based on Any One-Way Permutation
Some
public-key encryption scheme can be used as a commitment scheme. This can
be done by having the sender generate a pair of keys and use the public key together
with the encryption of a value as its commitment to the value. In order to satisfy the
unambiguity requirement, the underlying public-key scheme needs to satisfy additional
requirements (i.e., the set of legitimate public keys should be efficiently recognizable,
and an encryption relative to legitimate public keys should have a unique decryption).
In any case, public-key encryption schemes have additional properties not required
of commitment schemes, and their existence seems to require stronger intractability
assumptions. (Thus, we consider the aforementioned approach to be “conceptually
wrong.”) An alternative construction, presented next, uses any
one-way permutation
.
Specifically, we use a one-way permutation, denoted
f
, and a hard-core predicate for
it, denoted
b
(see Section 2.5). In fact, we can use any 1-1 one-way function.
{
,
}
∗
→{
,
}
∗
be a
Construction 4.4.2 (Simple Bit Commitment):
Let f
:
0
1
0
1
function, and let b
:
{
0
,
1
}
∗
→{
0
,
1
}
be a predicate.
225
