Cryptography Reference
In-Depth Information
schemes. This is especially true when
huge
amounts of information need to be secretly
communicated.
The second (“modern”) approach, as followed in this topic, is based on
computational
complexity
. This approach is based on the fact that
it does not matter whether or not
the ciphertext contains information about the plaintext
, but rather
whether or not this
information can be efficiently extracted
. In other words, instead of asking whether or not
it is
possible
for the wire-tapper to extract specific information, we ask whether or not it
is
feasible
for the wire-tapper to extract this information. It turns out that the new (i.e.,
“computational-complexity”) approach offers security even if the key is much shorter
than the total length of the messages sent via the encryption scheme. For example, one
can use “pseudorandom generators” (discussed later) that expand short keys into much
longer “pseudo-keys,” so that the latter are as secure as “real keys” of comparable length.
In addition, the computational-complexity approach allows the introduction of con-
cepts and primitives that cannot exist under the information-theoretic approach. A
typical example is the concept of
public-key encryption schemes
. Note that in the pre-
ceding discussion we concentrated on the decryption algorithm and its key. It can be
shown that the encryption algorithm must get, in addition to the message, an auxiliary
input that depends on the decryption key. This auxiliary input is called the
encryp-
tion key
. Traditional encryption schemes, and in particular all the encryption schemes
used over the millennia preceding the 1980s, operate with an encryption key equal
to the decryption key. Hence, the wire-tapper in these schemes must be ignorant of
the encryption key, and consequently the
key-distribution problem
arises (i.e., how
two parties wishing to communicate over an insecure channel can agree on a secret
encryption/decryption key).
1
The computational-complexity approach allows the in-
troduction of encryption schemes in which the encryption key can be known to the
wire-tapper without compromising the security of the scheme. Clearly, the decryption
key in such schemes is different from the encryption key, and furthermore it is infeasi-
ble to compute the decryption key from the encryption key. Such encryption schemes,
called
public-key schemes
, have the advantage of trivially resolving the key-distribution
problem, because the encryption key can be publicized.
In Chapter 5, which will appear in the second volume of this work and will be devoted
to encryption schemes, we shall discuss private-key and public-key encryption schemes.
Much attention is devoted to defining the security of encryption schemes. Finally, con-
structions of secure encryption schemes based on various intractability assumptions are
presented. Some of the constructions presented are based on pseudorandom generators,
which are discussed in Chapter 3. Other constructions use specific one-way functions
such as the RSA function and/or the operation of squaring modulo a composite number.
1.1.2. Pseudorandom Generators
It turns out that pseudorandom generators play a central role in the construction of
encryption schemes (and related schemes). In particular, pseudorandom generators
1
The traditional solution is to exchange the key through an alternative channel that is secure, alas “more
expensive to use,” for example, by a convoy.
