Cryptography Reference
In-Depth Information
to a function specifying the behavior of
P
(i.e., the messages it sends in response to
particular messages it may receive). We require that the (expected) running time of the
extractor, on input
G
and with access to an oracle specifying
P
's messages, be inversely
related (by a factor polynomial in
|
G
|
) to the probability that
P
convinces
V
to accept
G
.
In case
P
always convinces
V
to accept
G
, the extractor runs in expected polynomial
time. The same holds in case
P
convinces
V
to accept with noticeable probability.
(We stress that the latter special cases do not suffice for a satisfactory definition; see
advanced comment in Section 4.7.1.4.)
4.7.1.2. Technical Preliminaries
}
∗
be a binary relation. Then
R
(
x
)
def
def
=
}
∗
×{
Let
R
⊆{
0
,
1
0
,
1
={
s
:(
x
,
s
)
∈
R
}
and
L
R
{
R
, then we call
s
a
solution
for
x
. We say that
R
is
polynomially bounded
if there exists a polynomial
p
such that
x
:
∃
s
s.t. (
x
,
s
)
∈
R
}
.If(
x
,
s
)
∈
|
s
|≤
p
(
|
x
|
) for all
(
x
-
relation
if
R
is polynomially bounded and, in addi-
tion, there exists a polynomial-time algorithm for deciding membership in
R
(indeed, it
follows that
L
R
∈
NP
,
s
)
∈
R
. We say that
R
is an
NP
). In the sequel, we confine ourselves to polynomially bounded
relations. In fact, all the applications presented in this topic refer to
NP
-relations.
We wish to be able to consider in a uniform manner all potential provers, without
making distinctions based on their running time, internal structure, and so forth. Yet
we observe that these interactive machines can be given auxiliary input that will enable
them to “know” and to prove more. Likewise, they may have the good fortune to select a
random input that will be more enabling than another. Hence, statements concerning the
knowledge of the prover refer not only to the prover's program but also to the specific
auxiliary and random inputs it receives. Therefore, we fix an interactive machine as
well as all the inputs (i.e., the common input, the auxiliary input, and the random
input) to this machine. For such a prover
inputs template, we consider both the
acceptance probability (of the verifier) when interacting with this template and the use
of this template as an oracle to a “knowledge extractor.” This motivates the following
definition.
+
Definition 4.7.1 (Message-Specification Function):
Denote by P
x
,
y
,
r
(
m
)
the
message sent by machine P on co
m
mon input x , auxiliary input y, and random
input r , after receiving messages m. The function P
x
,
y
,
r
is called the
message-
specification function
of machine P with common input x , auxiliary input y, and
random input r .
An oracle machine with access to the function
P
x
,
y
,
r
will represent the knowledge of
machine
P
on common input
x
, auxiliary input
y
, and random input
r
. This oracle
machine, called the knowledge extractor, will try to find a solution to
x
(i.e., an
s
∈
R
(
x
)). The running time of the extractor will be required to be inversely related to
the corresponding acceptance probability (of the verifier when interacting with
P
on
common input
x
and when
P
has auxiliary input
y
and random input
r
.)
