next up previous
Next: Cryptosystems Based on Integer Up: Mathematical Models in Public-Key Previous: Mathematical Models in Public-Key

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 tex2html_wrap_inline542 where tex2html_wrap_inline544, the so-called key space, is a large set of possible keys, and tex2html_wrap_inline546 is a map from a plaintext space tex2html_wrap_inline548 to a ciphertext space tex2html_wrap_inline550. The one-way nature of tex2html_wrap_inline546 implies that for virtually all ciphertexts tex2html_wrap_inline554 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 tex2html_wrap_inline546 must have an inverse tex2html_wrap_inline568, and this inverse must be easily obtainable given some additional secret information d. The extra information d is called a trap-door of tex2html_wrap_inline546 and the functions tex2html_wrap_inline546 themselves are called trap-door one-way functions. It is also required that, with a knowledge of tex2html_wrap_inline568, tex2html_wrap_inline580 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 tex2html_wrap_inline546 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 tex2html_wrap_inline546 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 tex2html_wrap_inline546) may be finite but a message of arbitrary length can be encrypted using tex2html_wrap_inline546.

To summarize we give our first model of public-key cryptography.
The key space tex2html_wrap_inline544 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 tex2html_wrap_inline618 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:

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 tex2html_wrap_inline636 and computes tex2html_wrap_inline638 which he sends to Alice. On receiving c, Alice computes
thereby recovering the message. An eavesdropper might intercept c and can obtain tex2html_wrap_inline636 from public files, but cannot find m from c without knowledge of tex2html_wrap_inline652 (or equivalently tex2html_wrap_inline654).

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 tex2html_wrap_inline554, 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 tex2html_wrap_inline618 there is also associated a large set tex2html_wrap_inline662, called a randomization set, and a map
In order to encrypt a plaintext tex2html_wrap_inline666 with such a map, one picks a random number tex2html_wrap_inline668 and computes the ciphertext
Consequently, in the ECB mode of operation, a sequence of plaintext blocks tex2html_wrap_inline672 will be encrypted to a sequence tex2html_wrap_inline674, where tex2html_wrap_inline676 and each tex2html_wrap_inline678 is chosen independently and randomly from tex2html_wrap_inline662 for tex2html_wrap_inline682. The set tex2html_wrap_inline662 is usually large, so the chance of picking the same r is small and the ciphertext values tex2html_wrap_inline688 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 tex2html_wrap_inline546 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 tex2html_wrap_inline546 be partially invertible; i.e., there needs to exist a function tex2html_wrap_inline696 such that tex2html_wrap_inline698, for all tex2html_wrap_inline666 and all tex2html_wrap_inline702 The function tex2html_wrap_inline568 is called a partial inverse of tex2html_wrap_inline546 since it recovers only part of the input to tex2html_wrap_inline546. We call a one-way function tex2html_wrap_inline546 with this property a partial-trap-door one-way function, and we give our second model of public-key cryptography.

Again, the elements tex2html_wrap_inline618 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 tex2html_wrap_inline662 has only one element. In order for the probabilistic model to be useful and secure, the following properties are needed.

Given a public key k it is easy to compute tex2html_wrap_inline746 for tex2html_wrap_inline666 and tex2html_wrap_inline668.
Given a private key d, it is easy to compute tex2html_wrap_inline754 for tex2html_wrap_inline756.
Knowing k and tex2html_wrap_inline756 it is infeasible to decide for any tex2html_wrap_inline666 whether m can be encrypted to c under tex2html_wrap_inline546. Thus, it is infeasible to determine tex2html_wrap_inline568 or d from the general information about the cryptosystem.
It is easy to generate a random key tex2html_wrap_inline618 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 tex2html_wrap_inline546 and c (as tex2html_wrap_inline546 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 tex2html_wrap_inline666 can be encrypted to a given ciphertext tex2html_wrap_inline756, as one can simply compute tex2html_wrap_inline796 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 tex2html_wrap_inline668 such that tex2html_wrap_inline804. 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.

Given k and tex2html_wrap_inline822, it is infeasible to infer any partial information about m.

While we shall not describe any systems with property P3tex2html_wrap_inline818, we do give a few references. The first probabilistic cryptosystem proven to satisfy P3tex2html_wrap_inline818 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.

next up previous
Next: Cryptosystems Based on Integer Up: Mathematical Models in Public-Key Previous: Mathematical Models in Public-Key

Shuhong Gao
Sun Oct 17 11:04:53 EDT 1999