We now turn to the central question of this enterprise, ``Can study of CA cryptosystems teach anything fundamental about the nature of complexity in dynamical systems or the strength of cryptological methods?" The answer hinges on whether the physical reasoning underlying the construction of CA cryptosystems can be properly connected to the computer-science measures of complexity used in cryptology. Only a few general indications can be given here as to where this connection might come from.
Cryptology 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 mearly 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.
The competition between cryptosystem builders and cryptanalysts is a superb model of co-evolution. As the strength of one improves the destructive methods of the other improve as well. This advance is of course not always in even steps; relevant input from other fields touching at foundational issues could cause better progress than cryptology's internal dynamics would allow.
The CA cryptosystem described in the text models a physical process which is the sum of random variables. We expect that if the sum contains a sufficient number of terms, that is, if a sufficient number of rounds are used in the encryption of each message block, then the ciphertext can be made as close to truly random as desired. The final quality of randomness should not depend on the message encrypted. Thus, if the system is strong at all, it should be strong in the average case. Computer science measures of complexity for the most part deal with worst-case difficulty of problems. Worst-case complexity is usually of little interest in physics, and should be of little interest in practical cryptology. Cryptosystems based on physical principles may push cryptology in this direction.
Let us now pick up the question from the other end. ``What can a dynamical systems theorist learn from an excursion into cryptology?" To start, that unpredictability is a concept meaningful only in relationship with 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 [4] 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 cryptology, may find new uses in dynamical systems theory. The best uses may consist of stripping off the purely ``cryptic" aspects of a dynamical system's complex behavior, to reveal a central core of properties of real physical relevance.