Cryptography Reference
In-Depth Information
easy
x
f(x)
HARD
Figure 2.1:
One-way functions: an illustration.
2.1. One-Way Functions: Motivation
As stated in the introductory chapter, modern cryptography is based on a gap between
efficient algorithms provided for the legitimate users and the computational infeasibility
of abusing or breaking these algorithms (via illegitimate adversarial actions). To illus-
trate this gap, we concentrate on the cryptographic task of secure data communication,
namely, encryption schemes.
In secure encryption schemes, the legitimate users should be able to easily decipher
the messages using some private information available to them, yet an adversary (not
having this private information) should not be able to decrypt the ciphertext efficiently
(i.e., in probabilistic polynomial time).
1
On the other hand, a non-deterministic machine
can quickly decrypt the ciphertext (e.g., by guessing the private information). Hence,
the existence of secure encryption schemes implies that there are tasks (e.g., “break-
ing” encryption schemes) that can be performed by non-deterministic polynomial-time
machines, yet cannot be performed by deterministic (or even randomized) polynomial-
time machines. In other words, a necessary condition for the existence of secure
encryption schemes is that
NP
BPP
P
=
NP
not be contained in
(and thus
).
P
=
NP
is a necessary condition for modern cryptography, it is not a
sufficient one. Suppose that the breaking of some encryption scheme is
Although
NP
-complete.
P
=
NP
Then,
implies that this encryption scheme is hard to break in the worst case,
but it does not rule out the possibility that the encryption scheme is easy to break almost
always. In fact, one can construct “encryption schemes” for which the breaking problem
is
NP
-complete and yet there exists an efficient breaking algorithm that succeeds 99%
of the time. Hence, worst-case hardness is a poor measure of security. Security requires
hardness in most cases, or at least “average-case hardness.” A necessary condition for
the existence of secure encryption schemes is thus the existence of languages in
NP
1
This “private information” is called a key; see Chapter 5.
