Cryptography Reference
In-Depth Information
3.3 From Unconditional Security to Computational Security:
Pseudo-Random Generators and One-Way Functions
The one-time pad is secure in the strongest possible sense but it is not a practical
solution to securely exchange huge quantities of information, as the secret key must
also be huge. To reach the goal of securely exchanging information using short keys,
the definition of security must be relaxed. Starting with the idea that randomness
of ciphertexts is what provides security we will aim for ciphertexts that, without
being random, look random to a computationally bounded adversary. Hence we will
weaken the security requirement in twoways: wewill aimfor encryption schemes that
are secure only against
efficient adversaries
i.e., adversaries that run in probabilistic
polynomial time and, on the other hand, we will require only that the adversary can
be successful with very small probability. The first weakening is necessary because,
if short keys are used, an adversary with unbounded computational resources can
always mount a brute-force attack to recover the key with high probability. The
second is also necessary because, even with limited computational resources, the
adversary can guess a key with a nonzero (although very small) probability of finding
the correct one.
The idea of modeling the adversary as a probabilistic polynomial-time algorithm
(or PPT algorithm for short) is consistent with the identification of efficient computa-
tionwith the kind carried out by these algorithms.Moreover, from the cryptographer's
point of view, it is safer to assume that the adversary is as powerful as possible within
realistic bounds and it is conceivable—although not proven—that the use of proba-
bilistic algorithms might provide additional power. On the other hand, probabilistic
algorithms are essential for cryptography and honest parties
1
must use them too to
generate keys and also for encryption.
The main tools required to formalize the concept of security are pseudo-random
generators and one-way functions.Wewill explain their basic properties and how they
are used but we do not include detailed proofs of some theoretical results because they
are outside the scope of this topic. These proofs may be found in topics dealing with
the theoretical foundations of cryptography such as [86, 87] or the more introductory
text [109].
3.3.1 Pseudo-Random Generators
To formalize the concept of computational security just outlined we need to make
precise what is meant by “the adversary is successful with very small probability”.
The idea is to define the notion of
negligible success probability
by requiring that
the adversary, modeled by a PPT algorithm, should be unlikely to succeed even after
repeating an attack a polynomial number of times. This leads in a natural way to the
following concept:
1
The term honest is used here as a synonym of legitimate and is devoid of ethical content.
