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

Library of Congress Cataloging‐in‐Publication Data is applied for

ISBN 978‐1‐119‐58242‐7 (hardback)

Cover Design: Wiley

Cover Image: © matejmo/iStock/Getty Images

Dedicated to the memory of my late parents, Edward A. Bruen and Brid Bean de Brún and to the memory of my late sister Antoinette.

Dedicated also to my siblings Phil and Bernard, to my beloved wife Katri, and to our children Trevor, Robin, and Merike. (Aiden A. Bruen)

Also dedicated to my parents, Alberto Forcinito and Olga Swystun de Forcinito, my beloved wife Claudia, and our children Dante, Lucas, and Diego. (Mario A. Forcinito)

Also dedicated to my parents, Archie and Muriel McQuillan, my siblings Dan, Mary, and Ian, my beloved wife Joy, and our children Anna and Christopher. (James M. McQuillan)

It is a privilege to welcome back our readers, past, present, and future to this second edition. We are delighted to introduce a third author, Dr. James McQuillan from Western Illinois University. We now have as co‐authors a mathematician, a computer scientist, and an engineer which, we feel, provides a good balance.

This new edition, like the first edition, is intended for a broad audience and our goals have not changed. Over the last 15 years, the three areas in the title have become more unified. For example, cryptographer Amight exchange a key with Busing public key cryptography. But in doing so, both would want to use error correction ensuring accuracy of transmission. Now that they have the common secret key they might use a symmetric‐key protocol such as DES or AES to exchange messages or even a one‐time pad. They need to know about security, and how it is measured, which brings in probability and entropy. This example is but the tip of the iceberg.

This book arose out of courses in cryptography and information theory at the University of Calgary. It is used as a text or a reference at universities in North America and Europe and of course can be used for self‐study. Parts of the material have also been presented at various industrial gatherings. Material related to some of the topics in the book has been patented and used in the energy sector.

The second edition has well over 350 worked examples and problems with solutions.

As with the first edition, we have made a considerable effort to ensure that the chapters are as accessible as possible. We wanted this new edition to also have both depth and breadth, to read with ease, and to explain the content clearly. We feel that the updates, the incorporation of new applications of basic principles, and the new examples and worked problems added to this edition greatly enhance and complete the book. We hope that it will be an excellent source for academics (including undergraduate and graduate students!) and practitioners that want to understand the mathematical principles and their real‐world consequences.

In a 2005 review of the first edition for the Mathematical Association of America , Dr. William Satzer states that the book is “lively and engaging, written with palpable enthusiasm.” He mentions the “… clearly communicated sense of interconnections among the [three] parts [of the book].” In a review for Mathematical Reviews (MR2131191), Dr. Andrea Sgarro from the University of Trieste, Italy, noted that the first edition “… is meant for a wide audience … and it can be used at various levels, both as a reference text and as a text for undergraduate and graduate courses; worked examples and problems are provided.”

Each chapter covers a lot of ground so a course might only cover part of it. For a basic course in cryptography, one could start with Chapter 2having taken a quick look at Chapter 1. Chapter 2introduces basic ideas on keys and security. Some of the material relates to weaknesses due to letter frequencies and requires some sophisticated mathematics described more fully in Beutelspacher, [Beu94]. Chapter 3covers public key cryptography algorithms such as RSA and key‐exchanges such as Diffie–Hellman, Elliptic curve cryptography and quantum cryptography are discussed in Chapter 6. Symmetric cryptography involving DES, AES, shift registers and perfect secrecy is discussed in Chapters 2, 4, 5, 15, 16and 21. Various attacks are covered in Chapter 7Part II of the book is devoted to information theory and Part III mainly deals with error-correction. However, along the way all these topics, i.e., cryptography, information theory and error-correction merge. The unity is beautifully illustrated in Chapters 24, 25 and 26.

Recent algorithms related to some in industry are discussed in Chapter 24. For applications to Bitcoin, there is Chapter 26. There are lots of options in the book for an undergraduate or graduate course for a term or a year in all three topics.

On the more applied side, the book can be used for courses in Cybersecurity Foundations, IT Systems, Data Security, and Cryptanalysis which might include topics such as HTTP, SSL/TLS, brute‐force, and birthday attacks.

We refer also to the preface of the first edition. Many new developments have taken place in this dynamic area since the first edition in 2005 and we have tried to cover them and to provide good references in this new edition. Chapters in the first edition have been updated. We have six new chaptersdealing with Compression and Applications ( Chapter 17), New Identities for the Shannon Function and an Application ( Chapter 25), Blockchain and Bitcoin ( Chapter 26), IoT, the Internet of Things ( Chapter 27), In the Cloud ( Chapter 28), and Review Problems and Solutions ( Chapter 29). We touch only on a few of the changes and additions that have been made in various chapters, as follows:

Chapter 4: homomorphic encryption is introduced, the discussion on quantum encryption is enlarged and post‐quantum cryptography is discussed.

Chapter 6extends the usual algorithm for ECC and demonstrates corresponding new geometrical results.

Chapter 7contains details of many new attacks.

Chapter 9has a new extended discussion on entropy in weighing problems.

Chapter 11has an improved treatment of source coding.

Chapter 12now contains a full proof of the Fundamental Theorem of Information Theory.

Chapter 13features a more user‐friendly approach to continuous signals and the Information Capacity Theorem for Band‐Limited channels.

The exposition for Chapter 15has been polished and simplified.

Chapter 16includes background and full details of the Berlekamp–Massey algorithm.

Chapter 17has details of the WKdm algorithms.

Chapter 18outlines the proof by one of the authors on a long‐standing conjecture regarding the next‐to‐minimum weights of Reed–Muller codes.

Chapter 21features a fresh approach to cyclic linear codes and culminates with a new user‐friendly proof of a powerful result on the periodicity of shift registers in Peterson and Weldon, [PW72].

The study of MDS codes leads to a very interesting and basic “inverse” problem in linear algebra over any field. It could be discussed in a first year linear algebra class. See Chapter 23for the details.

Chapter 24introduces a new hash function and improvements to the main algorithm in the chapter.

Chapter 25brings readers of this book to the very forefront of research by exhibiting infinitely many new identities for the Shannon function.