Cryptography Reference
In-Depth Information
polynomial-time reduction (proving implication in its probabilistic formalization) al-
ways implies a non-uniform polynomial-time reduction (proving the statement in its
non-uniform formalization), but the converse is not always true.
8
Finally, we mention that intractability assumptions concerning worst-case complex-
ity (e.g.,
) will not suffice, because we shall
not be satisfied
with their cor-
responding consequences. Cryptographic schemes that are guaranteed to be
hard to
break only in the worst case
are useless. A cryptographic scheme must be unbreakable
in “most cases” (i.e., “typical cases”), which implies that it will be
hard to break on the
average
. It follows that because we are not able to prove that “worst-case intractability”
implies analogous “intractability for the average case” (such a result would be consid-
ered a breakthrough in complexity theory), our intractability assumption must concern
average-case complexity.
P
=
NP
1.3.5. Oracle Machines
The original utility of oracle machines in complexity theory was to capture notions of
reducibility. In this topic (mainly in Chapters 5 and 6) we use oracle machines mainly
for a different purpose altogether - to model an adversary that may use a cryptosystem
in the course of its attempt to break the system. Other uses of oracle machines are
discussed in Sections 3.6 and 4.7.
Loosely speaking, an oracle machine is a machine that is augmented so that it can
ask questions to the outside. We consider the case in which these questions (called
queries) are answered consistently by some function
f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
, called the
oracle. That is, if the machine makes a query
q
, then the answer it obtains is
f
(
q
). In
such a case, we say that the oracle machine is given access to the oracle
f
.
Definition 1.3.8 (Oracle Machines):
A (deterministic/probabilistic)
oracle ma-
chine
is a (deterministic/probabilistic) Turing machine with an additional tape,
called the
oracle tape
, and two special states, called
oracle invocation
and
oracle appeared
.
The computation of the deterministic oracle machine
M
on
input
x
and with access to the oracle
f
:
}
∗
is defined by the
successive-configuration relation
. For configurations with states different from
oracle invocation
, the next configuration is defined as usual. Let
{
0
,
1
}
∗
→{
0
,
1
be a config-
uration in which the state is
oracle invocation
and the content of the oracle tape
is q. Then the configuration following
γ
, except that the state is
oracle appeared
, and the content of the oracle tape is f
(
q
)
. The string q is called
M's
query
, and f
(
q
)
is called the
oracle reply
. The computation of a probabilis-
tic oracle machine is defined analogously. The output distribution of the oracle
machine M , on input x and with access to the oracle f , is denoted M
f
(
x
)
.
γ
is identical to
γ
We stress that the running time of an oracle machine is the number of steps made
during its computation and that the oracle's reply to each query is obtained in a single
step.
8
The current paragraph may be better understood in the future, after seeing some concrete examples.
