Cryptography Reference
In-Depth Information
input that is shared by the two senders, but is independent of the receiver's random
coins (since information on these coins, if any, is only sent to the first sender). The
strategies employed by the two senders determine, for each possible coin-tossing of
the receiver, a pair of probabilities corresponding to their success in a 0-opening and a
1-opening. (In fact, bounds on these probabilities are determined merely by the strategy
of the first sender.) The unambiguity condition asserts that the average of these pairs,
taken over all possible receiver's coin tosses, is a pair that sums up to at most 1
2
−
n
.
Intuitively, this means that the senders cannot do more harm than deciding at random
whether to commit to 0 or to 1. Both the secrecy and unambiguity requirements are
information-theoretic (in the sense that no computational restrictions are placed on the
adversarial strategies). We stress that we have implicitly assumed that the reveal phase
takes the following canonical form:
1.
The second sender sends to the receiver the initial private input
+
v
and the random coins
s
used by the first sender in the commit phase.
2.
The receiver verifies that
and
s
(together with the private coins (i.e.,
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
1
and
R
).
v
Consider the pairs (
p
0
,
p
1
) assigned to each strategy
S
1
in the unambiguity condition
of Definition 4.11.4. We note that the highest possible value of
p
0
+
p
1
is attainable
by deterministic strategies for both senders.
32
Thus, it suffices to consider an arbitrary
deterministic strategy
S
1
for the first sender and fixed
σ
-openings, denoted
s
σ
, for
σ
∈{
0
,
1
}
. The unambiguity condition thus says that for every such
S
1
,
s
0
, and
s
1
,
σ
∈{
0
,
1
}
Pr
[
s
σ
is a
S
1
,
(1
n
)]
2
−
n
σ
-opening of
R
≤
1
+
In fact, for the construction presented next, we shall establish a stronger condition:
Strong unambiguity condition:
For every deterministic strategy S
1
and
every pair of strings
(
s
0
,
s
1
)
,
s
σ
is a
S
1
,
2
−
n
Pr
[
∀
σ
∈{
0
,
1
}
,
σ
-opening of
R
(1
n
)]
≤
(Clearly, if the unambiguity condition is violated, then so is the strong unambiguity
condition.)
4.11.2.2. A Construction
By the foregoing conventions, it suffices to explicitly describe the commit phase (in
which only the first sender takes part).
there exists a string
s
σ
maximizing the probability that any fixed string is a
σ
-opening of
S
1
,
R
(1
n
). Thus, the probability that
s
σ
is
a
32
We use an averaging argument. First note that for every (probabilistic)
S
1
and
σ
S
1
,
(1
n
) is an upper bound on the probability that
X
(as in the definition) is a
σ
-opening of
R
σ
-opening of
S
1
,
R
(1
n
). Similarly, fixing such a pair (
s
0
,
s
1
), we view
S
1
as a distribution over deterministic strategies for the
first sender and consider the sum of the two probabilities assigned to each such strategy
S
∗∗
1
. Thus, there exists a
deterministic strategy
S
∗∗
1
for which this sum is at least as large as the sum associated with
S
1
.
