Cryptography Reference
In-Depth Information
Proof:
Intuitively,
V
∗∗
captures the functionality of
V
∗
during each single phase.
By the
functionality of V
∗
during a phase
we mean the way
V
∗
transforms the
content of its work tapes at the beginning of the phase to their content at the
end of the phase, as well as the way
V
∗
determines the messages it sends during
this phase. Indeed, this transformation depends on the messages received dur-
ing the current phase. We stress that we can effect this transformation without
“reverse-engineering” (the code of)
V
∗
, but rather by emulating its execution
while monitoring all its tapes. Details follow.
In order to facilitate this process, we first modify
V
∗
so that all its “essen-
tial” activities refer only to its work tapes. Machine
V
∗
can be slightly modified
so that it starts its execution by reading the common input, the random input,
and the auxiliary input into special regions in its work tape and never accesses
the aforementioned read-only tapes again. Likewise,
V
∗
is modified so that it
starts each active period
11
(see Definition 4.2.2) by reading the current incoming
message from the communication tape to a special region in the work tape (and
never accesses the incoming-message tape again during this period). Actually,
this description should be modified so that
V
∗
copies only a polynomially long
(in the common input) prefix of each of these tapes, the polynomial being the one
bounding the running time of (the original)
V
∗
.
(Formally speaking, given an arbitrary
V
∗
, we construct a machine
W
∗
that emulates
V
∗
in a way that satisfies the foregoing conditions; that is,
W
∗
will satisfy these
conditions even if
V
∗
does not. Machine
W
∗
will have several extra work tapes that
will be designated as the common-input, random-input, auxiliary-input, and incoming-
communication tapes of
V
∗
. Machine
W
∗
will start by copying its own common input,
random input, and auxiliary input to the corresponding designated tapes. Likewise,
W
∗
will start each active period by copying the current incoming message from its
own communication tape to the corresponding designated tape (i.e., the incoming-
communication tape of
V
∗
). After completing these copying activities,
W
∗
just emu-
lates the execution of
V
∗
. Clearly,
W
∗
satisfies the requirements postulated. Thus,
formally speaking, whenever we later refer to
V
∗
, we mean
W
∗
.)
Consider an interaction of
V
∗
(
z
) with
P
Q
, on common input
x
. By the foregoing
modification, the interaction consists of
Q
(
) phases, so that, except in the
first phase, machine
V
∗
never accesses its common-input, random-input, and
auxiliary-input tapes. (In the first phase, machine
V
∗
starts by copying the content
of these tapes into its work tapes and never accesses the former tapes again.)
Likewise, when executing the current phase, machine
V
∗
does not try to read
messages of
previous
phases from its incoming-communication tape (yet it may
read these “old” messages from storage in its work tapes). Considering the content
of the
work tapes of V
∗
at the end of
each
of the
Q
(
|
x
|
|
x
|
) phases (of interaction
with
P
Q
) naturally leads us to the construction of
V
∗∗
.
We are now finally ready present the construction of
V
∗∗
: On common input
x
and auxiliary input
z
, machine
V
∗∗
starts by copying
z
into the work tape of
11
Recall that an
active period
during an execution of an interactive machine
M
consists of the steps
M
takes
from the time the last message is received up to the time at which
M
completes sending its response message.