Aiden A. Bruen - Cryptography, Information Theory, and Error-Correction

During the summer of 1937, Shannon obtained an internship at Bell Laboratories and returned to MIT to work on a Master's thesis. In September 1938, he moved to the Mathematics Department of MIT and wrote a thesis in genetics with the title An Algebra for Theoretical Genetics graduating in 1940 with his PhD degree in Mathematics and the S.M. degree in Electrical Engineering.

Dr. Shannon spent the academic year of 1940–1941 at the Princeton Institute where he worked with Herman Weyl, the famous group‐theorist and geometer. Subsequently, he spent a productive 15 years at the Bell Laboratories in New Jersey returning to MIT in 1956, first as a visiting professor and then, in 1958, as Donner Professor of Science. This was a joint appointment between mathematics and electrical engineering. Here he did not teach ordinary courses but gave frequent seminars. According to Horgan and Claude [Hor90], he once gave an entire seminar course, with new results at each lecture!

He retired from MIT in 1978 but continued to work on many different problems including portfolio theory for the stock market, computer chess, juggling, and artificial intelligence. He died in 2001, at the age of 84 a few years after the onset of Alzheimer's Disease.

Dr. Shannon's Master's thesis [Sha40] and related publication in Transactions, American Institute of Electrical Engineers [Sha38] won him the Alfred Noble Prize along with fame and renown. The thesis has often been described as the greatest Master's thesis of all time; many feel that this may in fact understate the case.

At MIT, he was idolized by both the students and faculty. Golomb et al. [GBC +02], reports that Shannon was “somewhat inner‐directed and shy, but very easy to talk to after the initial connection had been made.”

In his spare time, Shannon built several items including Thrifty Roman numerical Backward‐looking Computer (THROBAC) which was actually a calculator that performed all the arithmetic operations in the Roman numerical system. He also built Theseus, a mechanical mouse in 1950. Controlled by a relay circuit, the mouse moved around a maze until it found the exit. Then, having been through the maze, the mouse, placed anywhere it had been before, would go directly to the exit. Placed in an unvisited locale, the mouse would search for a known position then proceed to the exit, adding the new knowledge to its memory.

Shannon was the first to develop computerized chess machines and kept several in his house. He built a “mind‐reading” machine that played the old game of penny‐watching. As juggling was one of his obsessions, he built several juggling machines and worked hard on mathematical models of juggling. He was famous for riding his unicycle along the corridors at Bell Laboratories juggling all the while. On the more practical side, Shannon was also interested in portfolio management and the stock market which he connected to information theory, treating it as a noisy channel.

Over the course of his career, Dr. Shannon received umpteen awards, honors, prizes, honorary degrees, and invitations. In the end, it all became too much, and he “dropped out.” To quote Waldrop [Wal01] “he turned down almost all the endless invitations to lecture or to give newspaper interviews. He didn't want to be a celebrity. He likewise quit responding to much of his mail. Correspondence from major figures in science and government ended up forgotten and unanswered in a file folder he labeled ‘Letters I've procrastinated too long on.’.” Dr. Shannon did attend one other Shannon lecture in Brighton, England, in 1985 (delivered by Golomb), where the shy genius created quite a stir. As Robert McEleice recalls (see [Hor90]): “It was as if Newton had showed up at a physics conference.”

Shannon's Master's Thesis (see above and [Sha48]) was the first work to make him famous. He became intrigued by the switching circuits controlling the differential analyzer while working for Vannevar Bush. He was the first to notice that the work of a mathematics professor named George Boole in Cork, Ireland, done a century earlier, yielded the necessary mathematical framework for analyzing such circuits.

“On” and “Off” could be represented by “1” and “0.” The Boolean logical operations of AND, OR correspond exactly to a circuit with two switches in series, or in parallel, respectively. He demonstrated that any logical statement, no matter how complex, could be implemented physically as a network of such switches. He also showed how the crucial Boolean decision operation could be implemented in a digital system marking the main qualitative difference between a calculator and the powerful digital computers to follow.

Shannon published just one paper in cryptography, namely “Communication theory of secrecy systems,” [Sha49b]. Its contents had appeared in a war‐time classified Bell Laboratories document which was then declassified. The beginning sentence is very revealing. It reads as follows:

The problems of cryptography and secrecy systems furnish an interesting application of communication theory.

Indeed, this is precisely the point of view which inspired the authors of this book! We believe it is unrealistic to separate the study of cryptography from the study of communication theory embodying error‐correction and information theory.

To illustrate this, Shannon points out that just as in error‐correction, where the receiver tries to decode the message over a noisy channel so also, in cryptography, a receiver (this time, Eve, the eavesdropper) tries to decode the message over a noisy channel, the noise being the scrambling by the key which obfuscates the plain text to the cipher text.

In this paper, Shannon discusses at length his two famous principles of confusion and diffusion described in detail in Chapter 4. The Vernam cipher offers perfect security. We discuss perfect security in detail in Part II of the book where it is shown that, under appropriate conditions, perfect security corresponds precisely to a Latin square. Shannon's paper makes it quite clear that he was aware of this phenomenon though he did not explicitly state it.

In the paper, Shannon clearly differentiates between computational and unconditional security. Whether or not he “missed” public key cryptography is far from clear. However, in [Mas02] Massey points out that Hellman of Diffie–Hellman fame, has credited the following words from Shannon's paper as the inspiration for their discovery:

The problem of good cipher design is essentially one of finding difficult problems . We may construct our cipher in such a way that breaking it is equivalent to the solution of some problem known to be laborious.

Of course, the jury is still out, as Massey [Mas02] points out, on whether one‐way functions, the foundations of public key cryptography, really exist. We refer to Chapters 3and 4on this point.

Shannon theory: information compression and communication.

Shannon's revolutionary paper [Sha49b] on information theory electrified the scientific world and has dominated the area of communication theory for over 50 years. No other work of the twentieth century has had greater impact on science and engineering.

First of all, Shannon unified what had been a diverse set of communications – voice, data, telegraphy, and television. He quantified and explained exactly what information means. The unit of information is the Shannon bit. As Golomb et al. [GBC +02] so elegantly puts it, this is the “amount of information gained (or entropy removed) upon learning the answer to a question whose two possible answers were equally likely, a priori.”