Cryptography Reference
In-Depth Information
respective
ly
) of t
h
e second sender. Without loss of generality, we can assume
that both
s
0
and let
s
σ
=
s
1
···
s
n
(with
s
j
∈{
and
s
1
are in
{
0
,
1
,
2
}
n
0
,
1
,
2
}
).
The strong unambig
u
ity pro
p
erty asserts that for a uniformly selected
r
∈{
0
,
1
}
n
the probability t
h
at
s
0
and
s
1
are 0-opening and 1-opening, respectively, of the
receiver's view (
r
f
(
r
)) is at most 2
−
n
.
Let us denote by
R
σ
the set of all strings
r
,
∈{
0
,
1
}
n
for which the sequence
s
σ
is a possible
σ
-opening of the receiver's view (
r
,
f
(
r
)). Namely,
r
:(
≡
π
r
i
s
i
(mod 3)
R
σ
=
∀
i
)
f
i
(
r
)
+
σ
where
r
=
r
1
···
r
n
, and
f
(
r
)
=
f
1
(
r
)
···
f
n
(
r
). Then the strong unambiguity
property asserts that
|
R
0
∩
R
1
|≤
2
−
n
n
·|{
0
,
1
}
|
. That is:
|
R
0
∩
R
1
Claim 4.11.6.1:
|≤
1.
Proof:
Suppose, on the contrary, that
α,β
∈
R
0
∩
R
1
(and
α
=
β
). Then there
exists an
i
such that
α
i
=
β
i
and, without loss of generality,
α
i
=
0 (and
β
i
=
1).
By the definition of
R
σ
it follows that
≡
π
0
s
i
(mod 3)
f
i
(
α
)
≡
π
0
s
i
+
1 (mod 3)
f
i
(
β
)
≡
π
1
s
i
(mod 3)
f
i
(
f
i
(
α
)
≡
π
1
s
i
+
β
)
1
(mod 3)
Contradiction follows as in the motivating discussion. That is, using the first two
equations and the fact that
π
0
is the identity, we have
s
i
+
1
≡
s
i
(mod 3), and
combining this with the last two equations, we have
π
1
s
i
+
1
=
π
1
s
i
≡
π
1
s
i
+
1
(mod 3)
in contradiction to the (readily verified) fact that
π
1
(
s
+
1 mod 3)
≡
π
1
(
s
)
+
1
(mod 3) for every
s
∈{
,
,
}
0
1
2
.
This completes the proof of the proposition.
Remark 4.11.7 (Parallel Executions).
The proof extends to the case in which many
instances of the protocol are executed in parallel. In particular, by
t
parallel executions
of Construction 4.11.5, we obtain a two-sender commitment scheme for
t
-bit-long
strings. Note that we are content in asserting that the probability that the verifier's view
has two conflicting openings is at most 2
−
n
(or even
t
·
2
−
n
), rather than seeking error
reduction (i.e., a probability bound of 2
−
t
·
n
).
4.11.3. Perfect Zero-Knowledge for
NNNP
NP
Two-prover perfect zero-knowledge proof systems for any language in
follow
easily by modifying Construction 4.4.7. The modification consists of replacing the bit-
commitment scheme used in Construction 4.4.7 with the two-sender bit-commitment
