Chapter 8 has described several of the classical
models of cryptography in which the decryption key was the same as or easily
derivable from the encryption key. This meant that the corresponding encryption
and decryption algorithms were closely related in the sense that one could be
easily deduced from the other. Such cryptographic systems are called *
symmetric-key* or *conventional* systems, and their security relies
exclusively on the secrecy of the keys. Other examples of private-key
systems are the Data Encryption Standard (DES) [24] and IDEA
[12], in which users of the system who share a secret key can
communicate securely over an unsecure channel. In all of the private-key
systems, two users who wish to correspond must have a common key *
before* the communication starts, and in practice, establishing a common
secret key can be expensive, difficult, and sometimes nearly impossible,
especially in a large network where the users need not know each other.

In 1976, Diffie and Hellman [7] introduced a revolutionary new
concept called *public-key cryptography* based on the simple observation that
the encryption and decryption could be separated; i.e., they recognized
that a knowledge of the encryption key (or equivalently, the encryption
algorithm) need not imply a knowledge of the decryption key (or algorithm). In
such a system, the encryption key can be made public, say in a public directory,
while the decryption key can be kept secret. Anyone wishing to send a message
to a person in the directory can simply look up the public encryption key for
that person and use it to encrypt the message. Then, assuming the decryption key
is known only to the intended receiver of the message, only that person can
decrypt the message.

Of course in such a public-key system it must be computationally infeasible to deduce the decryption key (or the decryption algorithm) from the public key (or the public encryption algorithm), even when general information about the system and how it operates is known. This leads to the idea of one-way functions.

A function *f* is called a *one-way function* if for any *x* in the
necessarily large domain of *f*, *f*(*x*) can be efficiently computed but for
virtually all *y* in the range of *f*, it is computationally infeasible to
find any *x* such that *f*(*x*)=*y*.

Public-key cryptography requires a special set of one-way functions where , the so-called *key space*, is a large set of
possible *keys*, and is a map from a plaintext space to a
ciphertext space . The one-way nature of implies that for
virtually all ciphertexts it is computationally infeasible to
recover the plaintext *m* from a given *k* and *c*. However, since the
legitimate recipient of the message must be able to recover *m* from *c*,
more is required of these one-way functions. Specifically, each must
have an inverse , and this inverse must be easily obtainable given
some additional secret information *d*. The extra information *d* is called
a *trap-door* of and the functions themselves are called
*trap-door one-way functions*. It is also required that, with a knowledge
of , be easy to compute for all *c* in the ciphertext space.
Thus, a public-key cryptosystem consists of a family of trap-door one-way
functions.

Before proceeding, we will make a few remarks on the length of messages. For a
given key *k*, the function usually acts only on plaintexts of fixed
length whereas, in practice, a message can be of arbitrary length. However,
the message can be cut into appropriate pieces, called blocks, so that can
act on each block. The whole message is then encrypted by encrypting each block
individually. This operating mode is called the *Electronic Code Book*
(ECB) mode. (Other operating modes include *Cipher Block Chaining* (CBC)
mode, *Cipher Feedback* (CFB) mode, and *Output Feedback* (OFB) mode
[24].) The point here is that the plaintext space (i.e., the domain of
) may be finite but a message of arbitrary length can be encrypted
using .

To summarize we give our first model of public-key cryptography.

The key space is also called the *public-key space*, and the set of
trap-doors *d* is called the *private-key space*. Relative to (3), it is
also required that random keys and their corresponding trapdoors *d*
be easy to generate.

In practice, the complete description of all the components (1)-(3) of a cryptosystem is public knowledge. A person (user) who wants to become a part of the communication network can proceed as follows:

- Use (3) to generate a random key and the corresponding
trap-door
*d*. - Place the encryption function (or equivalently the key
*k*) in a public directory (say in the user's directory or home page), keeping*d*and the decryption function secret.

Now suppose that Bob wants to send a message *m* to a user Alice. To do this, he
simply looks up her public enciphering function and computes
which he sends to Alice. On receiving *c*, Alice computes

thereby recovering the message. An
eavesdropper might intercept *c* and
can obtain from public files, but cannot find *m* from *c* without
knowledge of (or equivalently ).

Actually, it is currently unknown as to whether one-way functions truly exist;
indeed, a proof of the existence of such functions would settle the famous
**P**=**NP** problem of computer science.
However, there are a number of functions that are believed to be one-way.
For example, it is assumed by experts that integer
multiplication is a one-way function because it is very easy to multiply
large integers, but it seems very hard to factor large numbers using the current
knowledge
and technology. This assumption is the basis for
several public-key cryptosystems including
the RSA and Rabin cryptosystems, discussed in Section 9.2.

In the above model of public-key cryptography, two
identical plaintext messages *m* are always encrypted into the same ciphertext
, and in the ECB mode, this feature can cause some leaking of
information. For example, if the cryptosystem were used to encrypt personnel
data and the salary fields were encrypted separately, then by
simply looking at the ciphertexts one could identify people with the same
salary. A natural question arises: Is it possible to design a public-key system
in which such identical plaintexts are encrypted to different ciphertexts?
Surprisingly, the answer is yes! The idea is to use random numbers (also referred to as
redundant information or nonces).

To explain this idea more fully, suppose with each there is also
associated a large set , called a *randomization set*,
and a map

In order to encrypt a plaintext with such a map, one
picks a random number and computes the ciphertext

Consequently, in the ECB mode of operation, a sequence of plaintext
blocks will be encrypted to a sequence
, where and each
is chosen independently and randomly from for .
The set is usually large, so the chance of picking the same *r* is small
and the ciphertext values will generally be different even when the
corresponding plaintext blocks are identical.

Here again, just as in our first model of public-key cryptography, each is
required to be a one-way function with a trap door, but it need not be fully
invertible since the recipient does not need to recover *r*.
What is needed for decryption is that be partially invertible; i.e.,
there needs to exist a function such that
, for all and all
The function is called a partial inverse of since it recovers
only part of the input
to . We call a one-way function with this property
a *partial-trap-door one-way function*, and we give our
second model of public-key cryptography.

Again, the elements are called the public keys and the
partial-trap-doors
*d* the private keys.
Obviously, the deterministic model is a special case of the
probabilistic model in which has only one element.
In order for the probabilistic model to be useful and secure,
the following properties are needed.

- P1.
- Given a public key
*k*it is easy to compute for and . - P2.
- Given a private key
*d*, it is easy to compute for . - P3.
- Knowing
*k*and it is infeasible to decide for any whether*m*can be encrypted to*c*under . Thus, it is infeasible to determine or*d*from the general information about the cryptosystem. - P4.
- It is easy to generate a random key
and the corresponding private key
*d*.

In the deterministic model it was required that it be infeasible to
determine *m* from a knowledge of only and *c* (as is one-way).
The corresponding
requirement P3 for the probabilistic model is much stronger because if one
can not even decide whether a plaintext *m* can be encrypted to a given *c*,
then certainly one can not find a plaintext that can be encrypted to *c*.
In this connection we note that in the deterministic model, it is
trivial to decide if a plaintext can be encrypted to a given
ciphertext , as one can simply compute and check whether or
not it is *c*. Requirement P3 also implies that even when an adversary has a
potentially matched pair (*m*, *c*) of plaintext and ciphertext, he or she can not
even verify that there exists such that
. Therefore, a probabilistic cryptosystem can provide a higher
level of security than a deterministic one.

The first probabilistic public-key cryptosystem was given by McEliece in 1978 (see [24]). In this system, the trap-door is based on the fact that the encoding process for error-correcting codes can be easy whereas decoding can be hard. In 1985 ElGamal [8] proposed a probabilistic system whose trap-door is based on the fact that exponentiation in a finite field (to be described later) is easy, but the inverse process, the so-called discrete logarithm problem, can be hard. The ElGamal system is a modification of the Diffie-Hellman key exchange scheme [7], whose security is also based on the discrete logarithm problem. Both the ElGamal and the Diffie-Hellman systems will be discussed in Section 9.3.

We close our general discussion of cryptographic models
with a few remarks concerning a further
generalization of property P3 which required that it be hard to
decide whether a given plaintext *m* can be encrypted to a given ciphertext
*c*. Even under this condition, there can still be leaking of
information. More specifically, it can happen that the probability that *m*
is encrypted to a given *c* is significantly different for different
values of *m*; consequently, for a given *c* it is possible to infer some
partial probabilistic information about the plaintext space. To
avoid such leaking, one can replace P3 by the following
stronger condition.

- P3.
- Given
*k*and , it is infeasible to infer any partial information about*m*.

In the discussions above we have tacitly assumed that the adversary
was passive in that he or she could only eavesdrop on a communication.
However, if the adversary were active and could inject or alter messages,
then some systems (e.g., the Rabin and ElGamal systems, discussed
later) are vulnerable to an *adaptive chosen ciphertext attack*, in
which the adversary is assumed so powerful that he or she can obtain the
decryptions of many ciphertexts
of his or her own making, though *not* the target ciphertext.
Recently, Cramer and Shoup [6]
proposed a cryptosystem that is secure against such an attack and is believed to be
practical as well.

Sun Oct 17 11:04:53 EDT 1999