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

Читать онлайн.
Название Cryptography, Information Theory, and Error-Correction
Автор произведения Aiden A. Bruen
Жанр Зарубежная компьютерная литература
Серия
Издательство Зарубежная компьютерная литература
Год выпуска 0
isbn 9781119582403



Скачать книгу

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 ellipsis. We may construct our cipher in such a way that breaking it is equivalent to ellipsis the solution of some problem known to be laborious.

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

      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 p (and the probability of a tail was 1 minus p) with p not-equals 1 slash 2, the information gained, on learning the outcome of the toss, would be less than one. The exact amount of information gained would be

      Note that when p equals one half and q equals one half, this works out to be 1. However if, for example p equals 2 slash 3, we gain only approximately 0.918 Shannon bits of information on learning the outcome of the coin toss.

      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.

      Cybersecurity

      Big data

      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.