Cryptography

The development of theory is often driven by applications. We will look at one application, cryptography, which engages complex systems theory at its roots. Cryptography is not unique in this, and this section is meant to stand for a larger discussion on the relationship of theory and application.

What is cryptography?

A cryptographer's ideal encryption scheme is an operation on a message which renders the message fully meaningless to anyone who does not possess a decryption key, yet in no way degrades the meaning extractable by anyone who does possess the key. An ideal practical code is in addition fast on both encryption and decryption, uses a key of manageable size, and produces no expansion of the data upon encryption.

A provable ideal practical encryption method in this sense in not yet known. For the state of the art see e.g. [5]. Cryptographic research proceeds by the proposition of cryptosystems, followed by attempts to break the the proposed systems. To break a cryptosystem means to discover the meaning of messages encrypted by the system without being handed the secret key. It is generally assumed in academic cryptography that the mechanism of encryption in all its detail is known to the cryptanalyst, the only information lacking being the secret key. Breaking a cryptosystem means reconstructing the key through observations of the cryptosystem in operation. The type of observations on and manipulations of the cryptosystem which are performed determine the mode of cryptanalytic attack. The first kind of attack is passive attack, in which the cryptanalyst can only make observations on the cryptosystem as it performs. In a ciphertext-only attack, the cryptanalyst has access only to a stream of ciphertext coming from a cryptosystem loaded with its secret key. The cryptanalyst attempts to find statistical regularities in the stream of ciphertext, departures from randomness which might reveal the nature of the key. All but the most naive cryptosystems produce ciphertext with a high degree of randomness, so that a cryptosystem which falls prey to this kind of attack is considered very weak. A stronger passive attack allows the cryptanalyst observations both of a stream of ciphertext and the corresponding message stream which produced it. This is called a known-plaintext attack. Again, cryptography has progressed to the point where cryptosystems susceptible to a known-plaintext attack hold little interest.

More important are the active attacks. Here cryptanalysts can opt to have plaintext of their choosing encrypted and see the ciphertext which results (a chosen-plaintext attack). Similarly, a chosen-ciphertext attack permits ciphertext of the cryptanalyst's design to be compared with the corresponding plaintext. By current cryptographic standards, a good cryptosystem must resist attacks which permit both plaintext and ciphertext to be chosen, and according to any strategy preferred by the cryptanalyst.

The reader unfamiliar with these concepts should take a moment to consider the cryptanalysis of the so-called Caesar cipher, reputed to have been used by Caesar to communicate with his troops. It consists of a pair of concentric rings. On each ring the letters of the alphabet are written in order. The key of the system is the displacement of the outer ring with respect to the inner ring. To send an encrypted message, the sender emits in sequence the letters on the inner ring which correspond to the letters on the outer ring contained in the message. The receiver reverses the process, reading off from the outer ring letters which correspond to the letters on the inner ring received. While a fair amount of ciphertext might be required in a passive ciphertext-only attack before the key is guessed, a ciphertext-plaintext pair for a single letter reveals the key in any other attack.

Cryptography and complex systems theory.

When we describe a dynamical system as ``complex" we mean that aspects of its behavior bear a cryptic relationship with the simple evolution laws which define it. One way to unpack the meaning of "cryptic" in complex systems theory is to connect it with more precise meanings in cryptography. To bridge dynamical systems and cryptography one may attempt to make codes based on dynamical systems and use methods of cryptography to evaluate them.

Cryptography and complex systems theory are linked by methodology as well as subject matter. It should be obvious that all of the cryptographer's methods of attack have analogies in the methods of a dynamical systems theorist. The analogies are particularly tight in the study of so-called iterated cryptosystems. An iterated cryptosystem is one in which a cryptographically weak transformation is applied repeatedly to a message, so that the composed transformation is strong. The most well-known and well-used cryptosystem is an iterated cryptosystem. It is known as the Data Encryption Standard, or DES. The DES encryption/decryption algorithm consists of 16 rounds of a transformation designed to fully mix message information together with random key information.

Cryptosystems based on cellular automata.

The following thoughts on how to produce an ideal practical encryption scheme must be natural as they have occurred independently to a number of students of dynamical systems: The future state of a (chaotic) dynamical system depends sensitively on its initial state. After enough time has elapsed the initial condition is forgotten. Yet, since the system is deterministic, the same trajectory will always be traced out from the same initial condition. Let the secret key of the cryptosystem be the initial state of a publicly known dynamical system. Then a user sharing a key with another can send a secret message by combining it with the trajectory swept out by the dynamical system operating on the secret initial state. Anyone who does not know the initial state would not be able to recreate the trajectory and thus would not be able to disentangle it from the encrypted message.

One version of this idea[17] employs cellular automaton rule 30 to generate temporal sequences which have a high degree of randomness[18]. The secret key is the initial state of the system. Senders run the initial state forward under the rule, and XOR's the temporal sequence generated with their message to produces a ciphertext. Receivers then run the same cellular automaton forward on the same initial state to reproduce the temporal sequence. XORing again recovers the plaintext. Note that: 1) the key is a state of the system, 2) the message is encrypted by combining it with an information stream generated by forward iteration of the system, and 3) the message is decrypted by combining the ciphertext with an information stream again generated by forward iteration of the system.

Consideration of inverse as well as forward iteration of dynamical systems opens up some new ways to use dynamical systems for encryption. One possibility, which again has occurred independently to a number of investigators, is to concentrate on reversible dynamical systems. Using a reversible dynamical system, a message can be encrypted by encoding it as a state of the system and then running the system forward in time some distance. The resulting state is the ciphertext. To decrypt the ciphertext, the system is inverse iterated the same number of time steps as were used in encryption, recovering the plaintext as a state of the system. Note the contrast with the systems considered above in which only forward iteration is used. In those systems, the key is a state of the system and the system is fixed. When forward and inverse iteration is used, the key is the dynamical system itself. The key operates directly on the message to encrypt and decrypt it, while in the previous systems the information generated by the dynamical system is combined indirectly, so to speak, externally, with the message information.

Reversible CA may be particularly valuable in public-key encryption. A public-key cryptosystem uses two keys, one key is used for encryption, the other for decryption. One key is held in private, the other rendered public. Kari [13] has proposed a system in which the public key is a cellular automaton inverse to the private key cellular automaton. The security of public-key cryptosystems depends on the difficulty of finding the private key given knowledge of the public key and/or chosen plain and ciphertext. Kari bases much of his reasoning on a result of his [14] which shows that even deciding whether a given cellular automaton in more than one dimension has an inverse is impossible. In general, the mathematical theory of cellular automata which is relevant to cryptography is more well-developed than the theory of irreversible cellular automata. In particular, one knows that if a cellular automaton has an inverse, that inverse is also a cellular automaton. Many practical problems remain, however, concerning how to choose good public-key/private-key pairs, how these should be applied to encrypt a message, etc.

Consider now a system proposed by Habutsu et. al. [12]. This system uses both forward and inverse iteration of a dynamical system. The very significant difference here is that the dynamical system used by Habutsu et al. is irreversible. An irreversible system is one in which some states have none, or more than one, antecedent state. A very simple such map is the tent map. The (surjective) tent map is a map of the unit interval composed of two line segments, one beginning at (0,0) and running to (,1), the other beginning at (,1) and running to (1,0). The secret key of this system is the parameter which specifies the location of the peak of the tent. Under the tent map, all points but one have two preimages. Habutsu et al. use this fact to encrypt by 1) encoding a message as a state of the system, and 2) running the system backward in time by choosing one of the two preimages of this state at random. This process is repeated many times, resulting in a ciphertext. A receiver of the ciphertext who knows the secret key can decrypt the message by running the tent map forward in time the same number of iterations as were used in encryption. This interesting system has a number of practical problems, some linked to the linearity of the tent map which have been cryptanalytically exploited by Biham [2], some linked to the continuity of the map which can lead to round-off errors. These round-off error problems do not occur in the cellular automaton based system to which we now turn.

The problems of linearity and round-off error can be solved by using CA instead of smooth dynamical systems. A cryptosystem illustrating this idea has been developed [9]. In this system, a message is encoded as a state of the system, and various cellular automaton rules are applied to it to produce a new state which is the ciphertext. To decrypt, the same cellular automaton rules are applied in reverse order. The cellular automata employed are derived from a secret key. The system uses both reversible and irreversible cellular automaton rules. During encryption, irreversible rules are iterated backwards in time. To go backward from a given state, one of the possible predecessor states is selected at random. This process can be repeated many times. Backward iteration thus serves to mix random information with the message information. A particular kind of partially linear irreversible rule which is such that a random predecessor state for any given state can be rapidly built. Reversible rules are also used for some stages of encryption to provide full non-linearity. Figure 3 gives some idea of how this system works. Full details are beyond the scope of this article, and may be found in [10].

  
Figure 3: A cellular automaton cryptosystem.

It is useful to briefly consider an attack on one stage of the encryption. It contains the lesson which is the main point of this section. In this stage, an irreversible cellular automaton is run backward by repeated and randomly selecting preimages. The number of preimages grows like , where r is the radius of the rule, and n is the number of backward iterations. The space of rules which could generate the ciphertext is of size . The rule can be chosen so that no statistical information is contained in the preimages. Given all this, one could expect that for r and n sufficiently large, no effective procedure could find the cellular automata which relates a ciphertext to the corresponding plaintext, and claim that the system is ultimately complex.

But note the following [16]: If we knew two configurations adjacent in time, and , then we could read off the cellular automaton rule by comparing the two configurations. If the configurations were sufficiently long, then every possible neighborhood would occur in and we could find which state each neighborhood maps to by looking at the state of the corresponding cell in . Without loss of generality, let us assume the neighborhood of all 0's maps to 0. We then chose a ciphertext which consists of all 0's, but for a few 1's near the middle. The result of decrypting by running forward in time is a new configuration . Recall that n is large enough that we learn nothing by comparing and . If we know then we could decrypt it to find and then, by comparing and , we could read off the cellular automaton rule which is the key of the system, thereby breaking it. We do not know , it is some state generated internally in the cryptographic apparatus. We do know something about , however. It too only contains a few 1's near the center, and is otherwise 0. This because the rule is of finite radius and the influence of the 1's in the center of cannot propagate very far under the action of the rule applied once. So we test all possible candidates for ; there are not that many of them. One of them will produce a coherent result: no neighborhood in will have two different images in . This coherent result yields the key.

What have we learned?

Cryptography has made strides over the last two decades toward founding its investigations on solid principles. These strides have been in the direction of attaching quantitative measures derived from computer science to the difficulty of breaking cryptosystems using various attacks. That is, one no longer asks if a system is unbreakable in some absolute sense, but rather how long must a computer of a given type work to break the system, how much memory space will it take up in the process etc. A well-developed mathematical theory supports these investigations.

Still, if one digs further into these foundations, one finds voids. It is merely a conjecture that prime factorization is a hard problem, albeit a conjecture which has strongly resisted disproof. If it were to be disproved, then many well-studied cryptosystems based on number theory would collapse. Likewise, evaluation of cryptosystems in terms of computer-science notions of tractability depend on an assumption concerning the inequality of the classes P and NP.

The effective measure of the quality of a cryptosystem remains in practice what it has always been. The longer a cryptosystem is in wide use in plain view of well-trained well-motivated and intelligent cryptanalysts without being broken, the better it is. Is it the same for complex systems? The suggestion is that unpredictability and complexity are concepts meaningful only in relationship with a specification of the set of prediction tools at ones disposal, and of how much force one is willing to use to apply them. Once the set of tools is specified, the issue is stated in a syntactic framework. Roughly, if the dynamics is represented in a highly coded fashion then for prediction our mechanism to expand the code into readability must be equal to the task. A new collection of tools, a shift in the semantic power available, may render an unpredictable system orderly. Unpredictability thus has as much to do with a level of comprehension of the correct representation of a system as it does with the distribution over the classes in a given representation (see Crutchfield [3] for a related discussion). A powerful tool, well-adapted to the given system, may pull out enough predictability from it that it would be considered ``broken" by the cryptanalyst, even though worthwhile mysteries may remain for the physicist. Some cryptanalytic tools, sharpened to the demanding standards of cryptography, may find new uses in complex systems theory. The best uses may consist of stripping off the purely ``cryptic" aspects of a complex system's behavior, to reveal a central core of properties of real physical and biological relevance.