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

In the above, we can think of entropy as “uncertainty” analogous to entropy in physics (which is the key idea in the second law of thermodynamics). An example would be the tossing of a fair coin and learning which turned up – heads or tails. If the coin were biased, so that the probability of a head was (and the probability of a tail was ) with , the information gained, on learning the outcome of the toss, would be less than one. The exact amount of information gained would be

(1.1)

Note that when and , this works out to be 1. However if, for example , we gain only approximately 0.918 Shannon bits of information on learning the outcome of the coin toss.

It can be mathematically proven that the only information function that gives sensible results is the appropriate generalization to a probability distribution of Formula ( 1.1) above. Formula ( 1.1) ties in to the fundamental notion of entropy (or uncertainty). There are many examples of redundancy in the English language, i.e. the use of more letters or words or phrases than are necessary to convey the information content being transmitted. As Shannon points out, the existence of redundancy in the language is what makes crosswords possible.

This redundancy can be reduced in various ways. An example is by writing acronyms such as “U.S.” for “United States.” When information is to be electronically transmitted, we remove redundancy by data‐compression. Shannon's formula for data compression is intimately related to entropy which is in turn related to the average number of yes–no questions needed to pin down a fact. Shannon showed that it is possible to obtain a bound for the maximum compression which is the best possible. The actual technique for compressing to that ultimate degree is embodied in the construction of the so‐called Huffman codes, well known to all computer science undergraduates. Later, other compression techniques followed, leading to modern technologies used in, for example, mp3's (music compression). This part of Shannon's work is also connected to the later work of Kolmogorov on algorithmic complexity and the minimum length binary program needed for a Turing machine to print out a given sequence.

But this was only the beginning. Shannon then went on to prove his fundamental result on communication, based on entropy and the mathematical ideas delineated above. He showed that any given communications channel has a maximum capacity for reliably transmitting information which he calculated. One can approach this maximum by certain coding techniques – random coding and now turbo coding – but one can never quite reach it. To put it succinctly: Capacity is the bound to error‐free coding . Thus, for the last 50 years, the study of error correction has boiled down to attempts to devise techniques of encoding in order to come close to the Shannon capacity. We will have much to say about this bound in Parts II and III of this book.

Shannon's work, theoretical and practical, still dominates the field and the landscape. To quote Cover in [Cov02]:

This ability to create new fields and develop their form and depth surely places Shannon in the top handful of creative minds of the century.

Few can disagree with this assessment. Indeed, in Part III of this book, we describe protocols in cryptography and error‐correction based squarely on C.E. Shannon's work in information theory.

The Data Encryption Standard , or DES , was originally approved in 1977 as a block cipher algorithm that provides good cryptographic protection. Computational power has increased dramatically since 1977. DES is no longer considered to be secure. Since May 2005, it is recommended that DES no longer be used [Cen19].

The Advanced Encryption Standard , or AES , the replacement for DES, is detailed in Section 5.2.

The first two decades of the twenty‐first century have witnessed an explosive growth of global need for secure communications and the secure storage of data. Cybersecurity has become an area of major concern to governments and companies. Universities now offer entire degrees in cybersecurity. We discuss this more in Section 28.5.

In this big data era in which governments and private companies collect more and more information from, and make more information available to individuals in a variety of electronic formats. Along with the usual technological advances in the hardware and software of computers and networks that took place at the end of the twentieth century, there has been an increase in the variety and the uses of technology, including new devices such as smart phones, tablets, smart watches, apps on these devices, a multitude of devices from the Internet of Things (IoT), and cloud computing.

Computers today often have 4, 8, 16, 32, or more GBs of main memory (RAM). Solid‐state drives (SSDs) that are much faster (but more expensive) than hard drives (HDDs) are now prevalent in desktops and laptop computers. The memory hierarchy of a computer is discussed in Section 17.2.

CPUs (processors, or central processing units) on desktops and laptops (and even portable devices such as smart phones) have progressed from mainly one‐core processors to multicore processors with 2, 4, 8, or more cores. With multicore processors, multiple tasks can be done in parallel.

GPUs (graphics processing units), previously reserved for doing calculations to display graphics, can do some types of calculations, such as certain matrix manipulations, extremely quickly as they have many, many cores.

An empirical rule that has held true for a few decades is Moore's Law. In 1965, Intel cofounder Gordon Moore asserted that, “The number of transistors incorporated in a chip will approximately double every 24 months”(see [Int19]). For many years, the computing power of our desktop and laptop computers doubled every 18 months or so. As processor power increases, we must ensure that an adversary, Eve, who should not have the appropriate decryption keys, cannot decrypt our data and messages. This led in part to the replacement of DES with AES (see Section 1.6).

Recently, some have argued that Moore's law is dead. (See [Hea18, Sim16, Tib19], for example.) However, the performance of chips can still increase from changes in chip design. For example, multicore chips are now common‐place. Multiple computations can be done in parallel (at the same time) on different cores in a chip. Other factors, such as artificial intelligence (AI), cloud computing, and quantum computing, mean that we must continue to keep our encryption algorithms up to date. The amount and types of data, some of which are very personal and/or sensitive (e.g. health records, financial records), have never been greater in quantity and sensitivity. The need for encryption using encryption algorithms that are not susceptible to attacks has never been greater.