Protecting Information: From Classical Error Correction to Quantum Cryptography

Susan Loepp, William K. Wootters052182740X, 9780521827409

For many everyday transmissions, it is essential to protect digital information from noise or eavesdropping. This undergraduate introduction to error correction and cryptography is unique in devoting several chapters to quantum cryptography and quantum computing, thus providing a context in which ideas from mathematics and physics meet. By covering such topics as Shor’s quantum factoring algorithm, this text informs the reader about current thinking in quantum information theory and encourages an appreciation of the connections between mathematics and science. Of particular interest are the potential impacts of quantum physics: (i) a quantum computer, if built, could crack our currently used public-key cryptosystems; and (ii) quantum cryptography promises to provide an alternative to these cryptosystems, basing its security on the laws of nature rather than on computational complexity. No prior knowledge of quantum mechanics is assumed, but students should have a basic knowledge of complex numbers, vectors, and matrices.

---

Table of contents :
Cover……Page 1
Half-title……Page 3
Title……Page 5
Copyright……Page 6
Dedication……Page 7
Contents……Page 9
Preface……Page 13
Acknowledgments……Page 17
1.1.1 Substitution ciphers……Page 19
1.1.2 Vigenère ciphers……Page 21
1.1.3 One-time pad……Page 24
1.2.1 The Enigma cipher……Page 27
Cracking Enigma……Page 32
1.3 A Review of Modular Arithmetic and Zn……Page 36
1.4 The Hill Cipher……Page 39
1.5 Attacks on the Hill Cipher……Page 45
1.6 Feistel Ciphers and DES……Page 46
An r-Round Feistel Cipher with Block Size 64……Page 48
DES……Page 49
1.7 A Word about AES……Page 52
1.8 Diffie–Hellman Public Key Exchange……Page 53
Diffie–Hellman Public Key Exchange……Page 54
1.9 RSA……Page 55
RSA……Page 56
The Euclidean Algorithm……Page 58
1.10 Public Key Exchanges with a Group……Page 61
1.11 Public Key Exchange Using Elliptic Curves……Page 64
2 Quantum Mechanics……Page 74
2.1 Photon Polarization……Page 75
2.1.1 Linear polarization……Page 76
2.1.2 Review of complex numbers……Page 85
2.1.3 Circular and elliptical polarization……Page 89
2.2 General Quantum Variables……Page 95
2.3 Composite Systems……Page 101
The composite system rule……Page 105
2.4 Measuring a Subsystem……Page 111
Rule for measurements on subsystems……Page 112
2.5 Other Incomplete Measurements……Page 114
3 Quantum Cryptography……Page 121
3.1 The Bennett–Brassard Protocol……Page 123
3.2 The No-Cloning Theorem……Page 133
3.3 Quantum Teleportation……Page 137
4 An Introduction to Error-Correcting Codes……Page 146
4.1 A Few Binary Examples……Page 147
4.2 Preliminaries and More Examples……Page 152
4.3 Hamming Distance……Page 158
4.4 Linear Codes……Page 163
4.5 Generator Matrices……Page 166
4.6 Dual Codes……Page 173
4.7 Syndrome Decoding……Page 178
4.8 The Hat Problem……Page 184
The Strategy……Page 186
5 Quantum Cryptography Revisited……Page 191
5.1 Error Correction for Quantum Key Distribution……Page 192
5.2 Introduction to Privacy Amplification……Page 197
5.2.1 Eve knows a fixed number of elements of the bit string……Page 198
5.2.2 Eve knows the parities of certain subsets of the bit string……Page 201
5.2.3 The general case……Page 203
6.1 Definitions and Examples……Page 211
6.2 A Finite Field with Eight Elements……Page 213
6.3 General Theorems……Page 215
6.4 A Generator Matrix for a GRS Code……Page 218
6.5 The Dual of a GRS Code……Page 220
7.1 Introduction……Page 223
7.2 Quantum Gates……Page 226
7.3 The Deutsch Algorithm……Page 235
7.4 A Universal Set of Quantum Gates……Page 239
7.5 Number Theory for Shor’s Algorithm……Page 244
7.6 Finding the Period of f (x)……Page 247
7.7 Estimating the Probability of Success……Page 256
7.8 Efficiency of Factoring……Page 267
7.9 Introduction to Quantum Error Correction……Page 275
7.9.1 An X-correcting code……Page 276
7.9.2 A Z-correcting code……Page 279
7.9.3 The Shor code……Page 280
A.1 Fields……Page 287
A.2 A Glossary of Linear Algebra Definitions and Theorems……Page 289
A.3 Tables for the Alphabet……Page 293
References……Page 295
Index……Page 303