Cryptography Reference
In-Depth Information
Construction 4.11.5 (A Two-Sender Bit Commitment):
Preliminaries:
Let
π
0
and
π
1
denote two fixed permutations over
{
0
,
1
,
2
}
such
π
0
is the identity permutation and
π
1
is a permutation consisting of a single
that
transposition, say
(1
,
2)
. Namely,
π
1
(1)
=
2
,
π
1
(2)
=
1
, and
π
1
(0)
=
0
.
Common input:
The security parameter n (in unary).
Sender's input:
σ
∈{
0
,
1
}
.
A convention:
Suppose that the content of the senders' random tape encodes a
uniformly selected s
n
.
=
s
1
···
s
n
∈{
0
,
1
,
2
}
Commit phase:
1.
The receiver uniformly selects r
n
=
r
1
···
r
n
∈{
0
,
1
}
and sends r to the first
sender.
2.
For each i , the first sender computes c
i
def
=
π
r
i
(
s
i
)
+
σ
mod 3
and sends c
1
···
c
n
to the receiver.
We remark th
a
t the
second
sender could have opened the commitment either way if
it had known
r
(sent
by
the receiver to the
first
sender). The point is that the second
sender does not know
r
, and this fact drastically limits its ability to cheat.
Proposition 4.11.6:
Construction 4.11.5 constitutes a two-sender bit-commitment
scheme.
Proof:
The security property follows by observing that for every choice of
r
∈
{
n
.
The (strong) unambiguity property is proved by contradiction. As a motivation,
we first consider the execution of the preceding protocol, with
n
equal to 1, and
show that it is impossible for the two senders
always
to be able to open the
commitments both ways. Consider any pair, (
s
0
0
,
1
}
n
the message sent by the first sender is uniformly distributed over
{
0
,
1
,
2
}
s
1
), such that
s
0
is a possible
0-opening and
s
1
is a possible 1-opening, both with respect to the receiver's
view. We stress that these
s
σ
's must match all possible receiver's views (or else
the opening does not always succeed). It follows that for each
r
,
∈{
0
,
1
}
both
π
r
(
s
0
) and
π
r
(
s
1
)
1 mod 3 must fit the message received by the receiver (in the
commit phase) in response to message
r
sent by it. Hence,
π
r
(
s
0
)
≡
π
r
(
s
1
)
+
1
(mod 3) holds for each
r
∈{
0
,
1
}
. Contradiction follows because no two
s
0
+
,
s
1
∈
{
0
,
1
,
2
}
can satisfy both
π
0
(
s
0
)
≡
π
0
(
s
1
)
+
1 (mod 3), and
π
1
(
s
0
)
≡
π
1
(
s
1
)
+
1
(mod 3), the reason being that the first equality implies
s
0
≡
s
1
+
1
(mod 3),
which combined with the second equality yields
π
1
(
s
1
+
1 mod 3)
≡
π
1
(
s
1
)
+
1
(mod 3), whereas for every
s
∈{
0
,
1
,
2
}
it holds that
π
1
(
s
+
1 mod 3)
≡
π
1
(
s
)
+
1
(mod 3).
We now turn to the actual proof of the strong unambiguity property. The arbi-
trary (deterministic) strategy of the first sender is captured by a function, denoted
f
, mapping
n
-bit-long strings into
s
equences in
{
,
,
}
n
. Thus, the r
ec
eiv
er
's
0
1
2
view, when using coin sequence
r
=
r
1
···
r
n
∈{
0
,
1
}
n
, consists of (
r
,
f
(
r
)).
Let
s
0
and
s
1
denote arbitrary opening attempts (i.e., 0-opening and 1-opening,
