Theory and Models

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.

While we shall not describe any systems with property P3, we do give a few references. The first probabilistic cryptosystem proven to satisfy P3 was given by Goldwasser and Micali [10], and later Blum and Goldwasser [4] gave a more efficient system.

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.