Cryptography Reference
In-Depth Information
v
∈{
,
}
1.
Commit phase:
To commit to value
0
1
(using security parameter n), the
n
sender uniformly selects s
∈{
0
,
1
}
and sends the pair
(
f
(
s
)
,
b
(
s
)
⊕
v
)
to the
receiver.
2.
(Canonical) reveal phase:
In the reveal phase, the sender reveals the bit
v
and the
string s used in the commit phase. The receiver accepts the value
v
if f
(
s
)
=
α
and b
(
s
)
⊕
v
=
σ
, where
(
α,σ
)
is the receiver's view of the commit phase.
{
,
}
∗
→{
,
}
∗
be a
1-1
one-way function, and let
Proposition 4.4.3:
Let f
:
0
1
0
1
b
:
}
be a hard-core predicate of f . Then the protocol presented
in Construction 4.4.2 constitutes a bit-commitment scheme.
{
0
,
1
}
∗
→{
0
,
1
Proof:
The secrecy requirement follows directly from the fact that
b
is a hard-
core of
f
. The unambiguity requirement follows from the 1-1 property of
f
.In
fact, there exists
no
ambiguous receiver view. Namely, for each possible receiver
view (
α,σ
), there is a unique
s
∈{
0
,
1
}
|
α
|
such that
f
(
s
)
=
α
, and hence a unique
v
∈{
0
,
1
}
such that
b
(
s
)
⊕
v
=
σ
.
4.4.1.3. Construction Based on Any One-Way Function
We now present a construction of a bit-commitment scheme that is based on the weakest
assumption possible: the existence of one-way functions. Proving that the assumption
is indeed minimal is left as an exercise (i.e., Exercise 13). On the other hand, by the
results in Chapter 3 (specifically, Theorems 3.3.3 and 3.5.12), the existence of one-way
functions implies the existence of pseudorandom generators expanding
n
-bit strings
into 3
n
-bit strings. We shall use such a pseudorandom generator in the construction
presented next.
We start by motivating the construction. Let
G
be a pseudorandom generator satis-
fying
|
G
(
s
)
|=
3
·|
s
|
. Assume that
G
has the property that the sets
{
G
(
s
):
s
∈{
0
,
1
}
n
}
and
{
G
(
s
)
⊕
1
3
n
:
s
∈{
0
,
1
}
n
}
are disjoint, where
α
⊕
β
denotes the bit-by-bit XOR
of the strings
α
and
β
. Then the sender can commit itself to the bit
v
by uniformly
n
3
n
k
k
-bit-
long string). Unfortunately, the foregoing assumption cannot be justified in general, and
a slightly more complex variant is required. The key observation is that for most strings
r
∈{
0
,
1
}
selecting
s
∈{
0
,
1
}
and sending the message
G
(
s
)
⊕
v
(
v
denotes the all-
v
3
n
the sets
{
G
(
s
):
s
∈{
0
,
1
}
n
n
}
are disjoint. Such
a string
r
is called
good
. This observation suggests the following protocol: The receiver
uniformly selects
r
∈{
0
,
1
}
}
and
{
G
(
s
)
⊕
r
:
s
∈{
0
,
1
}
3
n
, hoping that it is good, and sends
r
to the sender. Hav-
ing received
r
, the sender commits to the bit
v
by uniformly selecting
s
∈{
0
,
1
}
n
and
sending the message
G
(
s
)if
v
=
0, and
G
(
s
)
⊕
r
otherwise.
Construction 4.4.4 (Bit Commitment under General Assumptions):
Let G
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
be a function such that
|
G
(
s
)
|=
3
·|
s
|
for all s
∈{
0
,
1
}
∗
.
1.
Commit phase:
To receive a commitment to a bit (using security parameter n), the receiver
uniformly selects r
∈{
0
,
1
}
3
n
and sends it to the sender.
