Cryptography Reference
In-Depth Information
phase the second sender sends the content of the joint random tape (used by the first
sender in the commit phase) to the receiver. We stress again that the two senders cannot
exchange information between themselves throughout the entire commit and reveal
process; thus, in particular, the second sender does not know the messages sent by the
receiver to the first sender during the commit phase.
Definition 4.11.4 (Two-Sender Bit Commitment):
A
two-sender bit-commit-
ment scheme
is a triplet of probabilistic polynomial-time interactive machines,
denoted
(
S
1
,
S
2
,
R
)
, for the two-partner model satisfying the following:
Input specification:
The common input is an integer n presented in unary, called
the
security parameter
. The two partners, called the
senders
, have an auxiliary
private input
v
∈{
0
,
1
}
.
Secrecy:
The
0
-commitment and the
1
-commitment are identically distributed.
Namely, for every probabilistic (not necessarily polynomial-time) machine R
∗
interacting with the first sender (i.e., S
1
), the random variables
,
R
∗
(1
n
)
S
1
(0)
R
∗
(1
n
)
are identically distributed.
and
S
1
(1)
,
Unambiguity:
Preliminaries: For simplicity,
v
∈{
0
,
1
}
and n
∈ N
are implicit in
all notations.
1.
As in Definition 4.4.1, a
receiver's view of an interaction
with the (first) sender,
denoted
(
r
m
)
, consists of the random coins used by the receiver, d
en
oted r , and
the sequence of messages received from the ( first) sender, denoted m.
2.
Let
,
σ
∈{
0
,
1
}
.
We say that the string s is a
possible
σ
-opening
of the receiver's
view
(
r
m
)
if m describes the messages received by R when R uses local coins r
and interacts with machine S
1
, which uses local coins s and input
(
,
1
n
)
.
3.
Let S
1
be an arbitrary program for the first sender. Let p be a real and
σ,
σ
∈
{
-opening of
the receiver's view of the interaction with
S
1
if for every random variable X
(representing the string sent by the second sender in the reveal phase)
, which is
statistically independent of the receiver's coin tosses, the probability that X is a
possible
0
,
1
}
. We say that p is an
upper bound on the probability of a
σ
-opening of the receiver's view of an interaction with S
1
σ
is at most p.
That is,
S
1
,
(1
n
)]
p
(The probability is taken over the coin tosses of the receiver, the strategy
S
1
, and
the random variable
X
.)
4.
Let S
1
Pr
[
Xisa
σ
-opening of
R
≤
be as before, and for each
σ
∈{
0
,
1
}
let p
σ
be an upper bound on the
-opening of the receiver's view of the interaction with S
1
.Wesay
that
the receiver's view of the interaction with
S
1
is unambiguous
if p
0
+
probability of a
σ
p
1
≤
2
−
n
.
The
unambiguity requirement
asserts that for every program for the first sender
S
1
the receiver's interaction with S
1
is unambiguous.
1
+
In the formulation of the unambiguity requirement, the random variables
X
represent
possible strategies of the second sender. Such a strategy may depend on the random
