Cryptography Reference
In-Depth Information
to efficiently provide an answer for such a problem. This question can be phrased
in the single most important open question in theoretical computer science and
complexity theory:
Is
NP
=
P
or
NP
=
P
?
If this question is answered in the affirmative (i.e.,
NP
=
P
), then every
problem (function) in
is theoretically solvable (computable) in polynomial
time. It is, however, widely believed and conjectured that
NP
P
=
NP
.The
P
=
NP
conjecture is supported by our intuition that solving a problem is usually
more involved than verifying a solution. Empirical evidence toward the conjectured
inequality is given by the fact that literally thousands of problems in
,coming
from a wide variety of mathematical and scientific disciplines, are not known to
be solvable in polynomial time (in spite of extensive research attempts aimed at
providing efficient algorithms to solve them).
If
NP
, then there is no computationally secure cryptographic system
in a mathematically strong sense. Nevertheless, there may still exist cryptographic
systems that are computationally secure for all practical purposes, provided that the
complexity ratio between using the system and breaking it is a polynomial of suffi-
ciently high degree. An example to illustrate this point is Merkle's Puzzles addressed
in Section 16.2.1. Also, all unconditionally (i.e., information-theoretically) secure
cryptographic systems remain unaffected and secure even if
P
=
NP
P
=
NP
.
6.6.2.1
Polynomial Reducibility
It is sometimes useful to compare the relative difficulties of two (or more) compu-
tational problems. This is where the notion of polynomial reducibility comes into
play. In short, a function
f
is
polynomially reducible
to a function
g
if there ex-
ists a(nother) function
h
that can be computed in polynomial time so that
f
(
x
)=
g
(
h
(
x
)) for every input
x
. Hence, we can compute
f
by first computing
h
(in polyno-
mial time) and then computing
g
.If
g
is efficiently computable, then so is
f
(because
we only require a polynomial number of invocations of
g
). If, however,
g
is not
efficiently computable, then the notion of polynomial reducibility is not particularly
useful. The notion of a polynomial-time reduction for decision problems can now be
defined as suggested in Definition 6.10.
}
∗
be two deci-
sion problems.
D
1
is said to
polytime reduce
to
D
2
(denoted as
D
1
≤
P
D
2
), if there
is an algorithm that solves
D
1
which uses, as a subroutine, an algorithm for solving
D
2
, and which runs in polynomial time if this algorithm does.
Definition 6.10 (Polynomial-time reduction)
Let
D
1
,D
2
⊆{
0
,
1
