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

of modern developments (Figure 1.1).

1.2 Brief Biography of Claude E. Shannon

Claude Shannon has been described as the “father of the information age.” His discoveries are everywhere. Waldrop [Wal01] gives an excellent example from the days, not so long ago, where most people listened to music on CDs, before streaming services became so popular.

      Pick up a favorite CD. Now drop it on the floor. Smear it with your fingerprints. Then slide it into the slot on the player‐and listen as the music comes out just as crystal clear as the day you first opened the plastic case. Before moving on with the rest of your day, give a moment of thought to the man whose revolutionary ideas made this miracle possible: Claude Elwood Shannon.

      Computers give us the power to process information. But Shannon gave us the capacity to understand and analyze information. Shannon demonstrated the unity of text, pictures, film, radio‐waves, and other types of electronic communication, and showed how to use these media to revolutionize technology and our way of thinking.

1.3 Career

Shannon was born in Petoskey, Michigan in 1916. His father was a business man who later became a judge, and his mother was a high schoolteacher. As a youngster he was interested in, and became adept at, handling all kinds of contraptions such as model airplanes and boats as well as learning the workings of the telegraph system. At the age of 20, he graduated with degrees in Mathematics and Electrical Engineering from the University of Michigan.

      In the summer of 1936, Claude joined the MIT Electric Engineering department as a research assistant to work on an analog computer (as opposed to our modern digital computers) under the supervision of Vannevar Bush. Bush's analog computer, called a differential analyzer, was the most advanced calculator of the era and was used mainly for solving differential equations. A relay circuit associated with the analyzer used hundreds of relays and was a source of serious study by Shannon, then, and later.

      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.

1.4 Personal – Professional

      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.”

      

1.5 Scientific Legacy

      Circuits

      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.

      Cryptography

      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