Cryptologia: Biopolitics and intuitive algebra in the mathematization of cryptology? A review of Sha

ABSTRACT: Communication theory of secrecy systems as well as information theory in terms of Claude E. Shannon not only explains the solvability but also explores the theoretical secrecy of cryptograms by modeling information sources in higher order statistics, socalled a priori transition probabilities. In order to understand messages as stochastic processes in time, the mathematical theory of communication is historically traced back to World War II and into two fields of knowledge: biopolitics and intuitive algebra.

KEYWORDS: Algebraic theory of cryptology, genetics and cryptology, history of information theory.

In 1948 the electrical engineer Claude Elwood Shannon published his famous "A Mathematical Theory of Communication." Shannon's notion of information or entropy fundamentally changed the epistemology of science in the twentieth century. Not only communication engineering, but also biology, psychology, sociology, linguistics, and philosophy as well as media theory and other branches of science changed their methodical background thereafter. The main step in communication theory was to model an information source by stochastic processes.

The statistical properties of a message have long been studied in practical cryptanalysis, and it is obvious that information theory is a spinoff from cryptological research during World War II. At least, Shannon gave a new theory to secrecy, putting the mathematization of cryptology right ahead in comparison to practical secrecy. In 1949 a paper that he had written earlier, "Communication Theory of Secrecy Systems", was published. The output of his research on information theory, which coincides with research in cryptology during World War II, goes back to the memorandum "A Mathematical Theory of Cryptography" from 1945. This paper was split into "A Mathematical Theory of Communication" (MTC) and "Communication Theory of Secrecy Systems" (CTS), both published in the Bell System Technical Journal. Shannon's first memorandum was declassified in 1957, and we can now look at some small but historically significant differences between the two versions.

Before we trace the differences in Shannon's papers, we first have to state that nothing of theoretical importance appeared in the 1949 paper that was not in the 1945 memorandum. Some words had been changed and some paragraphs deleted. But the changes are not only of an editorial nature: Besides removing paragraphs concerning the theoretical secrecy of Vernam systems, multiple substitution systems, and the practical secrecy of Vigenere systems, one difference in the mathematization of cryptology is of great importance. Shannon removed some hints concerning the genealogy of his theory.

Part One of the "Communication Theory of Secrecy Systems" deals with the mathematics, whereas "A Mathematical Theory of Cryptography" deals with the foundations and algebraic structures of secrecy systems. Therefore the famous formula for information and entropy H = - E pi log(pi) is derived in 1949 but deduced in 1945. The way Shannon builds up his theory is documented much better in "A Mathematical Theory of Cryptography." These changes in the topics are related to deletions in the "Communication Theory of Secrecy Systems."

One missing paragraph explains in more detail what Shannon called "difficult epistemological questions connected with the theory of secrecy, or in fact with any theory which involves questions of probability (particular a priori probabilities, Bayes' Theorem, etc.) when applied to a physical situation." [6, p. 28]

"With regard to the application of the mathematical theory of probability to physical situations", Shannon wrote in the paragraph subsequently removed, "there are two main theories or ways of setting up the correspondence [in a communication system].

1. "The frequency theory. Probability is correlated with regard to the frequency of an event. This is the correspondence used by the practicing statistician, in principle by the physicists, etc.

2. "The degree of belief approach. Probability is a subjective phenomena and measures one's degree of belief in the occurrence of an event. This approach is seen often in the work of historians, judges, and in everyday life. Although this latter approach has often been attacked as meaningless we cannot agree with this opinion. In the first place the intuitive approach can be given a rigorous mathematical foundation. This has been done in-a very elegant way by B. O. Koopman. Essentially one need only assume that a subject be capable of making probability judgements (Event A is more or less probable than event B or they are equiprobable) and his judgements be self consistent (e.g. if he judges A more probable than B and B more probable than C he should judge A more probable than C). One can even establish numerical data by the use of a `standard gauge', for example a roulette wheel, and thus relate the subjective and the frequency probabilities. In the second place, on pragmatic grounds one can hardly see the subjective applications, since almost all of our event decisions are based on this sort of probability judgements. Cryptographic work involves both types of applications. In the use of frequency tables, significance tests etc., the cryptanalyst is following the frequency approach. In the 'intuitive' methods of cryptanalysis (probable words etc.) the degree of belief approach is more in evidence." [6, p. 29]

We can see that in this removed paragraph Shannon refers to two approaches in cryptology, the frequency approach and the intuitive method. Whereas the frequency approach is well known to cryptologists, the intuitive method mark a remarkable point in Shannon's theory of cryptography. The possibility of decoding messages by the well-known a priori transition probabilities in an intercepted message is not only the breakthrough in the theory of communication, but also a new way to determine the secrecy of a communication system. As we learn from information theory, the stochastic structure of a message leads to the economical compression of data which not only optimizes the transmission capacity of a channel but also decreases the decodability of a message. This is because the structure of the message converges with maximal compression to indecipherable noise. Shannon's notion of redundancy explains the possibility of solving a cryptogram and can be quantified by measuring the stochastic structure of a message.

In the years of working out the mathematical theory of cryptography from 1940 up to 1945, Shannon was involved with two important institutions. First, the Bell Laboratories, where he was involved in the design of fire-control systems and in Project X, a privacy communication system for telephone and speech data transmission (also called 'Sigsaly' or 'Ciphony I', merged together from 'Cipher' and 'Telephony').[1, p. 296] During the construction of a secret speech line between Franklin D. Roosevelt and Winston Churchill in 1942, he met the English code-breaker Alan M. Turing. At Bell Labs, Shannon could work out a technical side of communication systems, especially pulse code modulation (PCM) and its consequences for future digital communication systems.[4, p. 70ff] Not only speech and telegraph transmission systems on a strategical level, but also the communication links between ground control station and head of guided projectiles in a tactical situation had to be secret and unjammable.

The fact that Shannon refers to intuitive logic leads to the second institution Shannon was involved in: the mathematical formalization of communication theory, especially the theory of stochastic structures in information sources. This was started under Hermann Weyl at the Institute for Advanced Study in Princeton.1 Weyl, a German mathematician and former pupil of David Hilbert, who converted from formalism to intuitionism, guided Shannon at Princeton in questions concerning formal systems.

At first it seems obvious that the modeling of stochastic structures in cryptograms was a countermeasure to cryptographic processes of World War II. The German secrecy systems, mainly Enigma, operated by multiple substitution of letters. The western Allies were interested not only in breaking the German and Japanese codes, but also in the theoretical secrecy of communication devices. The a priori transition probabilities as a structure of languages or signals for guidance had not been mentioned by the Germans as a possible method in cryptoglogy. Reducing the a priori probabilities in a message therefore means to encode a message in the assumption that the enemy is aware of the same methods in codebreaking. The transition probability mirrors the insufficiency of encoding messages by the Germans.

But the 'mathematical' structure and the `algebraic foundation' of this probabilistic theory did not result from practical application, but out of a "rigorous logic basis", as Shannon puts it. In the theorization of statistic properties in communication systems, Shannon refers to the work of B. O. Koopman in probability theory as a branch of intuitive logic: "The Axioms and Algebra of Intuitive Probability" from 1940 and "Intuitive Probabilities and Sequences" from 1941. For the history of cryptology, it is therefore still unknown in what way the intuitionist Hermann Weyl and the methods in intuitive logic and probability affected the mathematical theory of cryptology, but an axiomatic background as well as a logic of probabilistic judgments is implied in the deduction of information quantity. This is quite important, because we otherwise cannot understand why Shannon's formalization brings out the so called a priori transition probabilities. These probabilities exactly mark the new theoretical approach of Shannon: to observe not only letter frequencies in space, but also transition probabilities in between letters or other n-gram structures in time.

Although Shannon's statistical approach to model information sources was supported by intuitive logic, the way of modeling an information source in a statistical manner is historically still unclear. Shannon himself had not used statistical methods in his very first draft of communication theory mentioned in a letter to his mentor Vannevar Bush in February 1939.[7, p. 455] Then "it was in 1940 that I [Shannon] first started modeling information as a stochastic process or a probabilistic process." [5, p. 168] The main theoretical research in this time was his doctoral dissertation completed in 1940. His thesis lies in the field of biopolitics, is entitled "An Algebra for Theoretical Genetics." [7, pp. 891-920], and was carried out for the Eugenics Record Office in Cold Spring Harbour. It was Bush who proposed algebra and genetics to Shannon: "It occurred to me that just as a special algebra had worked well in his hands on the theory of relays, another special algebra might conceivably handle some of the aspects of Mendelian heredity. Accordingly I tossed the idea to him. At the time he did not even know what the words meant, and of course, at the present time has only a fragmentary knowledge of this aspects of genetics."2 Shannon's dissertation has never been of importance for geneticists, but it turns out to be of great importance for the history of information theory. It was the first time Shannon modeled transmission by statistics. The relation between theoretical genetics and mathematization of cryptology is not new. Twenty years before Shannon, it was William F. Friedman who did the first mathematization of cryptology combining statistics and cryptanalysis. Friedman was also geneticist and his "weapons measure of central tendencies and dispersion, of fit and skewness, of probability and sampling and significance - were ideally fashioned to deal with the statistical behavior of letters and words." [4, p. 384] The reproduction of a population in Shannon's genetic work combines genes by "definite probabilities", as every gene has a definite place in the map of the chromosome. The relative positions of genes in a chromosome determine a priori the possibility and probability of a combination that an offspring receives. The transmission of a population is modeled on a time-axis. Later, the founder of cybernetics-Norbert Wienerwill sum up the facts between telegraphy and genetics, both games of discrete transmission systems: "there is no fundamental absolute line between the types of transmission which we use for sending a telegram and the types of transmission which are theoretically possible for a living organsim such as a human being." [8, p. 110]

Of course, this kind of hereditary transmission does not lead directly to information theory, but it is the first time that Shannon sought an algebraic theory for probabilistic transitions during the transmission of genetical structures on a time-axis. Together with a rigorous logic, the mathematical theory of cryptography came to be. When Shannon started war research at the Institute for Advanced Studies, he decided in a letter to Bush to take up the "mathematical genetics work from point of view of algebraic theory." 3 The first general sketch of communication theory in 1939 merged with the statistical approach of algebraic genetics in 1940 and became a mathematical and algebraic theory of cryptology in 1945. Shannon's biography, which started with the master's thesis, "A Symbolic Analysis of Relay and Switching Circuits" in 1938, turns out to be a Markov chain itself: Boolean algebra - algebra of genetics - notion of redundancy and theory of information; electrical engineering - biopolitics - cryptography and theory of communication. The redundancy in Shannon's biography is high, the entropy low.

1 As Shannon states in an interview.[5, p. 1681

2 Bush to E. B. Wilson, 15.12.1938. Bush Collection, Library of Congress, Washington DC.

3 Shannon to Bush, 15.12.1939. Bush Collection, Library of Congress, Washington DC.

REFERENCES

1. Fagen, M. 1978. A History of Engineering and Science in the Bell System. New York: BTL, Inc.

2. Hagemeyer, F. W. 1949. Die Entstehung von Informationskonzepten in der Nachrichtentechnik. PhD, Typoscript. Free University Berlin, GERMANY.

3. Kahn, D. 1967. The Codebreakers. The Story of Secret Writing. New York: Macmillan.

4. Kahn, D. 1984. Cryptology and the origin of spread spectrum. IEEE Spectrum. 21(Sep): 70-80.

5. Price, R. 1985. A Conversation with Claude Shannon. One Man's Approach to Problem Solving. Cryptologia. 9(2): 167-175.

6. Shannon, C. E. 1945. A Mathematical Theory of Cryptography. MM-45110-92, PO. 4. Declassified in 1957 (M. I. T. Archive).

7. Sloane, N. J. A. et al. 1993. Claude E. Shannon. Collected Papers. New York: IEEE Press).

8. Wiener, N. 1950. The Human Use of Human Beings: Cybernetics and Society. Boston: Houghton Mifflin.

Axel Roch

ADDRESS: Esmarchstr. 2, 10407 Berlin GERMANY. Email: axel.roch@rz.hu-berlin.de.

BIOGRAPHICAL SKETCH

Axel Roch received his master's degree from Humboldt University in Berlin. He is currently visiting scholar at MIT, Program in Science, Technology, and Society. He has published a number of works, among them, "Mendel's Message. Genetics and Information Theory," in Versuchskaninchen, Oeder, W. et al. (eds.), 1997, Zurich: MfG; "Machines that catch Machines. On the Firecontrol Systems of Norbert Wiener and Claude Shannon," in Konfigurationen," Tholen, C. et al. (eds.), 1999, Munich: Fink.