Cryptography Reference
In-Depth Information
The computation of a Turing machine
M
on inputs of length
n
can be simulated
by a single circuit (with
n
input nodes) having size
O
((
|
M
|+
n
+
t
(
n
))
2
), where
t
(
n
) is a bound on the running time of
M
on inputs of length
n
. Thus, a non-uniform
sequence of polynomial-time machines can be simulated by a non-uniform family of
polynomial-size circuits. The converse is also true, because machines with polynomial
description lengths can incorporate polynomial-size circuits and simulate their compu-
tations in polynomial time. The thing that is nice about the circuit formulation is that
there is no need to repeat the polynomiality requirement twice (once for size and once
for time) as in the first formulation.
Convention.
For the sake of simplicity, we often take the liberty of considering circuit
families
{
C
n
}
n
∈N
, where each
C
n
has poly(
n
) input bits rather than
n
.
1.3.4. Intractability Assumptions
We shall consider as
intractable
those tasks that cannot be performed by probabilistic
polynomial-time machines. However, the adversarial tasks in which we shall be inter-
ested (“breaking an encryption scheme,” “forging signatures,” etc.) can be performed
by non-deterministic polynomial-time machines (because the solutions, once found,
can be easily tested for validity). Thus, the computational approach to cryptography
(and, in particular, most of the material in this topic) is
interesting
only if
NP
is not
BPP
P
=
NP
contained in
).
7
We use the phrase “not in-
teresting” (rather than “not valid”) because all our statements will be of the form “if
intractability assumption
then
useful consequence
,” Such a statement re-
mains valid even if
(which certainly implies
P
=
NP
(or if just
intractability assumption
, which is
P
=
NP
never weaker than
, is wrong); but in such a case the implication is of little
interest (because everything is implied by a fallacy).
In most places where we state that “if
intractability assumption
then
useful consequence
,” it will be the case that
useful consequence
either im-
plies
intractability assumption
or implies some weaker form of it, which in turn
implies
. Thus, in light of the current state of knowledge in complex-
ity theory, we cannot hope to assert
NP
\
BPP
= ∅
useful consequence
without any intractability
assumption.
In a few cases, an assumption concerning the limitations of probabilistic polynomial-
time machines shall not suffice, and we shall use instead an assumption concerning the
limitations of non-uniform polynomial-time machines. Such an assumption is of course
stronger. But also the consequences in such a case will be stronger, since they will also
be phrased in terms of non-uniform complexity. However, because all our proofs are ob-
tained by reductions, an implication stated in terms of probabilistic polynomial time is
stronger (than one stated in terms of non-uniform polynomial time) and will be preferred
unless it is either not known or too complicated. This is the case because a probabilistic
7
We remark that
NP
is not known to contain
BPP
. This is the reason we state the foregoing conjecture
as
NP
is not contained in
BPP
, rather than
BPP
=
NP
. Likewise, although “sufficiently strong” one-way
functions imply
BPP
=
P
, this equality is not known to hold unconditionally.
