Cryptography: Theory and Practice by Douglas Stinson CRC Press, CRC Press LLC ISBN: 0849385210 Pub Date: 03/17/95 |
Previous | Table of Contents | Next |
In 1949, Claude Shannon published a paper entitled Communication Theory of Secrecy Systems in the Bell Systems Technical Journal. This paper had a great influence on the scientific study of cryptography. In this chapter, we discuss several of Shannons ideas.
There are two basic approaches to discussing the security of a cryptosystem.
1This is a similar situation to proving that a problem is NP-complete: it proves that the given problem is at least as difficult as any other NP-complete problem, but it does not provide an absolute proof of the computational difficulty of the problem.
When we discuss the security of a cryptosystem, we should also specify the type of attack that is being considered. In Chapter 1, we saw that neither the Shift Cipher, the Substitution Cipher nor the Vigenere Cipher is computationally secure against a ciphertext-only attack (given a sufficient amount of ciphertext).
What we will do in this section is to develop the theory of cryptosystems that are unconditionally secure against a ciphertext-only attack. It turns out that all three of the above ciphers are unconditionally secure if only one element of plaintext is encrypted with a given key!
The unconditional security of a cryptosystem obviously cannot be studied from the point of view of computational complexity, since we allow computation time to be infinite. The appropriate framework in which to study unconditional security is probability theory. We need only elementary facts concerning probability; the main definitions are reviewed now.
DEFINITION 2.1 Suppose X and Y are random variables. We denote the probability that X takes on the value x by p(x), and the probability that Y takes on the value y by p(y). The joint probability p(x, y) is the probability that X takes on the value x and Y takes on the value y. The conditional probability p(x|y) denotes the probability that X takes on the value x given that Y takes on the value y. The random variables X and Y are said to be independent if p(x, y) = p(x)p(y) for all possible values x of X and y of Y.
Joint probability can be related to conditional probability by the formula
Interchanging x and y, we have that
From these two expressions, we immediately obtain the following result, which is known as Bayes Theorem.
THEOREM 2.1 (Bayes Theorem)
If p(y) > 0, then
COROLLARY 2.2
X and Y are independent variables if and only if p(x|y) = p(x) for all x, y.
Throughout this section, we assume that a particular key is used for only one encrypion. Let us suppose that there is a probability distribution on the plaintext space, . We denote the a priori probability that plaintext x occurs by . We also assume that the key K is chosen (by Alice and Bob) using some fixed probability distribution (often a key is chosen at random, so all keys will be equiprobable, but this need not be the case). Denote the probability that key K is chosen by . Recall that the key is chosen before Alice knows what the plaintext will be. Hence, we make the reasonable assumption that the key K and the plaintext x are independent events.
The two probability distributions on and induce a probability distribution on . Indeed, it is not hard to compute the probability that y is the ciphertext that is transmitted. For a key , define
That is, C(K) represents the set of possible ciphertexts if K is the key. Then, for every , we have that
We also observe that, for any and , we can compute the conditional probability, (i.e., the probability that y is the ciphertext, given that x is the plaintext) to be
It is now possible to compute the conditional probability (i.e., the probability that x is the plaintext, given that y is the ciphertext) using Bayes Theorem. The following formula is obtained:
Observe that all these calculations can be performed by anyone who knows the probability distributions.
We present a toy example to illustrate the computation of these probability distributions.
Example 2.1
Let with . Let with . Let , and suppose the encryption functions are defined to be ; ; and . This cryptosystem can be represented by the following encryption matrix:
We now compute the probability distribution . We obtain
Now we can compute the conditional probability distributions on the plaintext, given that a certain ciphertext has been observed. We have:
We are now ready to define the concept of perfect secrecy. Informally, perfect secrecy means that Oscar can obtain no information about plaintext by observing the ciphertext. This idea is made precise by formulating it in terms of the probability distributions we have defined, as follows.
Previous | Table of Contents | Next |
Copyright © CRC Press LLC