Cryptography Reference
In-Depth Information
Upon receiving the message r ( from the receiver), the sender commits to value
v
∈{
n
0
,
1
}
by uniformly selecting s
∈{
0
,
1
}
and sending G
(
s
)
if
v
=
0
, and
r otherwise.
2.
(Canonical) reveal phase:
In the reveal phase, the sender reveals the string s used
in the commit phase. The receiver accepts the value
0
if G
(
s
)
G
(
s
)
⊕
=
α
and accepts the
value
1
if G
(
s
)
⊕
r
=
α
, where
(
r
,α
)
is the receiver's view of the commit phase.
Such a definition of the (canonical) reveal phase allows the receiver to accept both
values, but we shall show that that happens very rarely (if at all).
Proposition 4.4.5:
If G is a pseudorandom generator, then the protocol presented
in Construction 4.4.4 constitutes a bit-commitment scheme.
Proof:
The secrecy requirement follows the fact that
G
is a pseudorandom gen-
erator. Specifically, let
U
k
denote the random variable uniformly distributed on
strings of length
k
. Then for every
r
∈{
0
,
1
}
3
n
, the random variables
U
3
n
and
U
3
n
⊕
r
are identically distributed. Hence, if it is feasible to find an
r
∈{
0
,
1
}
3
n
such that
G
(
U
n
) and
G
(
U
n
)
r
are computationally distinguishable, then either
U
3
n
and
G
(
U
n
) are computationally distinguishable or
U
3
n
⊕
⊕
r
are computationally distinguishable. In either case, contradiction to the pseudo-
randomness of
G
follows.
We now turn to the unambiguity requirement. Following the motivating discus-
sion, we call
r
∈{
0
,
1
}
r
and
G
(
U
n
)
⊕
3
n
good
if the sets
{
G
(
s
):
s
∈{
0
,
1
}
n
}
and
{
G
(
s
)
⊕
r
:
s
∈
3
n
yields a collision between the seeds
s
1
and s
2
if
G
(
s
1
)
=
G
(
s
2
)
⊕
r
. Clearly,
r
is good if it does not yield a collision
between any pair of seeds. On the other hand, there is at most one string
r
that
yields a collision between a given pair of seeds (
s
1
,
s
2
); that is,
r
=
G
(
s
1
)
⊕
G
(
s
2
).
Because there are at most (
2
n
n
{
0
,
1
}
}
are disjoint. We say that
r
∈{
0
,
1
}
2
)
<
2
2
n
possible pairs of seeds, fewer than 2
2
n
strings
will yield collisions between pairs of seeds, and so all the other 3
n
-bit-long strings
are good. It follows that with probability at least 1
−
2
2
n
−
3
n
the receiver selects
a good string, in which case its view (
r
,α
) is unambiguous (since if
r
is good
and
G
(
s
1
)
=
α
holds for some
s
1
, then
G
(
s
2
)
=
α
⊕
r
must hold for all
s
2
's). The
unambiguity requirement follows.
4.4.1.4. Extensions
The definition and the constructions of bit-commitment schemes are easily extended to
general commitment schemes, enabling the sender to commit to a string rather than to a
single bit. Actually, for the purposes of the rest of this section, we need a commitment
scheme by which one can commit to a ternary value. Extending the definition and the
constructions to deal with this special case is even more straightforward.
In the rest of this section we shall need commitment schemes with a seemingly
stronger secrecy requirement than defined earlier. Specifically, instead of requiring
secrecy with respect to all polynomial-time machines, we require secrecy with respect
to all (not necessarily uniform) families of polynomial-size circuits. Assuming the
227