Cryptography Reference
In-Depth Information
2.
Let
σ
∈{
0
,
1
}
. We say that a joint view (of an interaction),
((
r
,
m
)
,
(
s
,
m
))
, has
-opening
(with respect to
F
∗
and
p
(
a feasible
σ
·
))
if on input
(
m
,
(
s
,
m
)
,σ
)
,
algorithm F
∗
outputs, with probability at least
1
p
(
n
)
, a string s
such that m
describes the messages received by R when R uses local coins r and interacts
with machine S that uses local coins s
and input
(
/
1
n
)
.
σ,
(Remark: We stress that s
may, but need not, equal s. The output of algorithm
F
∗
has to satisfy
a
relation that depends on only part of the input (i.e., the
receiver's view
(
r
,
m
)
); the sender's view (i.e.,
(
s
,
m
)
) is supplied to algorithm
F
∗
as additional help.)
3.
We say that a joint view is
ambiguous with respect to
F
∗
and
p
(
)
if it has both
a feasible
0
-opening and a feasible
1
-opening
(with respect to
F
∗
and
p
(
·
·
))
.
The
unambiguity (or binding) requirement
asserts that for all but a negligible
fraction of the coin tosses of the receiver it is infeasible for the sender to inter-
act with the receiver, so that the resulting joint view is ambiguous with respect
to some probabilistic polynomial-time algorithm F
∗
and some positive polyno-
mial p
(
)
. Namely, for every probabilistic polynomial-time interactive machine S
∗
,
probabilistic polynomial-time algorithm F
∗
, positive polynomials p
(
·
)
,
and all sufficiently large n, the probability that the joint view of the interaction
between R and S
∗
, on common input
1
n
, is ambiguous, with respect to F
∗
and
p
(
·
)
and q
(
·
·
/
)
, is smaller than
1
q
(
n
)
.
In the formulation of the unambiguity requirement,
S
∗
describes the (cheating) sender
strategy in the commit phase, whereas
F
∗
describes its strategy in the reveal phase.
Hence, it is justified (and in fact necessary) to pass the sender's view of the interaction
(between
S
∗
and
R
) to algorithm
F
∗
. The unambiguity requirement asserts that any
efficient strategy
S
∗
will fail to yield a joint view of interaction that can later be (effi-
ciently) opened in two different ways supporting two different values. As usual, events
occurring with negligible probability are ignored.
One can consider a relaxation of the secrecy condition in which the probability
ensembles
}
n
∈N
are required to be statistically
close, rather than identically distributed. We choose not to do so because the cur-
rently known constructions achieve the more stringent condition. Furthermore, use
of the weaker notion of a perfectly hiding commitment scheme (in Section 4.8.3)
yields almost-perfect zero-knowledge arguments rather than perfect zero-knowledge
ones.
As in Definition 4.4.1, the secrecy requirement refers explicitly to the situation at
the end of the commit phase, whereas the unambiguity requirement implicitly assumes
that the reveal phase takes the following canonical form:
{
S
(0)
,
R
∗
(1
n
)
}
n
∈N
and
{
S
(1)
,
R
∗
(1
n
)
1.
The sender sends to the receiver its initial private input,
v
, and the random coins,
s
,it
has used in the commit phase.
2.
The receiver verifies that
and
s
(together with the 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
and
R
).
v
