Complexity and cryptography : an introduction

Title:

Personal Author:

Talbot, John

Publication Information:

UK : Cambridge University Press, 2006

Physical Description:

xii, 292 p. : ill. ; 24 cm.

ISBN:

9780521852319

Subject Term:

Cryptography

Computational complexity

Added Author:

Welsh, D. J. A

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010229202	Z103 T35 2006	Open Access Book	Book	Searching... Unknown

Cryptography plays a crucial role in many aspects of today's world, from internet banking and ecommerce to email and web-based business processes. Understanding the principles on which it is based is an important topic that requires a knowledge of both computational complexity and a range of topics in pure mathematics. This book provides that knowledge, combining an informal style with rigorous proofs of the key results to give an accessible introduction. It comes with plenty of examples and exercises (many with hints and solutions), and is based on a highly successful course developed and taught over many years to undergraduate and graduate students in mathematics and computer science.

Author Notes

Dominic Welsh is Professor of Mathematics and Fellow of Merton College, Oxford.

Reviews 1

Choice Review

Talbot (University College London) and Welsh (Merton College, Oxford) emphasize modern cryptology in the light of complexity theory, which is presented first in a rigorous manner, including discussions of many open problems. Not intending to create a comprehensive work, the authors treat classical cryptology very briefly, leave out much cryptanalysis, and skip elliptic curve cryptography and quantum cryptography. Having said this, a great deal is presented and the unique approach makes this work valuable. At times, it is more oriented toward theory than practice. The popular cryptosystems DES and AES are discussed briefly, without details necessary for implementation. The book is based on a course taught to seniors and graduate students, but without an instructor's help, most undergraduates would likely experience difficulty. The mathematics is at a fairly high level and most proofs are included. This is a fine resource for campuses offering cryptology, but it does not serve as the gentlest introduction for students without previous knowledge of the subject. For them, the easier (and much less thorough!) Cryptology by Albrecht Beutelspacher (1994) or Cryptological Mathematics by Robert E. Lewand (CH, Dec'01, 39-2242) is recommended. Those more interested in implementation than theory should seek Bruce Schneier's books. ^BSumming Up: Recommended. Upper-division undergraduates through professionals. C. Bauer York College of Pennsylvania

Preface	p. ix
Notation	p. xi
1 Basics of cryptography	p. 1
1.1 Cryptographic models	p. 2
1.2 A basic scenario: cryptosystems	p. 3
1.3 Classical cryptography	p. 7
1.4 Modern cryptography	p. 8
2 Complexity theory	p. 10
2.1 What is complexity theory?	p. 10
2.2 Deterministic Turing machines	p. 16
2.3 Decision problems and languages	p. 22
2.4 Complexity of functions	p. 30
2.5 Space complexity	p. 33
3 Non-deterministic computation	p. 39
3.1 Non-deterministic polynomial time - NP	p. 39
3.2 Polynomial time reductions	p. 43
3.3 NP-completeness	p. 45
3.4 Turing reductions and NP-hardness	p. 54
3.5 Complements of languages in NP	p. 56
3.6 Containments between complexity classes	p. 60
3.7 NP revisited - non-deterministic Turing machines	p. 62
4 Probabilistic computation	p. 67
4.1 Can tossing coins help?	p. 67
4.2 Probabilistic Turing machines and RP	p. 71
4.3 Primality testing	p. 74
4.4 Zero-error probabilistic polynomial time	p. 80
4.5 Bounded-error probabilistic polynomial time	p. 81
4.6 Non-uniform polynomial time	p. 83
4.7 Circuits	p. 86
4.8 Probabilistic circuits	p. 92
4.9 The circuit complexity of most functions	p. 93
4.10 Hardness results	p. 94
5 Symmetric cryptosystems	p. 99
5.1 Introduction	p. 99
5.2 The one time pad: Vernam's cryptosystem	p. 101
5.3 Perfect secrecy	p. 102
5.4 Linear shift-register sequences	p. 106
5.5 Linear complexity	p. 111
5.6 Non-linear combination generators	p. 113
5.7 Block ciphers and DES	p. 115
5.8 Rijndael and the AES	p. 118
5.9 The Pohlig-Hellman cryptosystem	p. 119
6 One way functions	p. 125
6.1 In search of a definition	p. 125
6.2 Strong one-way functions	p. 129
6.3 One way functions and complexity theory	p. 132
6.4 Weak one-way functions	p. 135
7 Public key cryptography	p. 141
7.1 Non-secret encryption	p. 141
7.2 The Cocks-Ellis non-secret cryptosystem	p. 142
7.3 The RSA cryptosystem	p. 145
7.4 The Elgamal public key cryptosystem	p. 147
7.5 Public key cryptosystems as trapdoor functions	p. 150
7.6 Insecurities in RSA	p. 153
7.7 Finding the RSA private key and factoring	p. 155
7.8 Rabin's public key cryptosystem	p. 158
7.9 Public key systems based on NP-hard problems	p. 161
7.10 Problems with trapdoor systems	p. 164
8 Digital signatures	p. 170
8.1 Introduction	p. 170
8.2 Public key-based signature schemes	p. 171
8.3 Attacks and security of signature schemes	p. 172
8.4 Signatures with privacy	p. 176
8.5 The importance of hashing	p. 178
8.6 The birthday attack	p. 180
9 Key establishment protocols	p. 187
9.1 The basic problems	p. 187
9.2 Key distribution with secure channels	p. 188
9.3 Diffie-Hellman key establishment	p. 190
9.4 Authenticated key distribution	p. 193
9.5 Secret sharing	p. 196
9.6 Shamir's secret sharing scheme	p. 197
10 Secure encryption	p. 203
10.1 Introduction	p. 203
10.2 Pseudorandom generators	p. 204
10.3 Hard and easy bits of one-way functions	p. 207
10.4 Pseudorandom generators from hard-core predicates	p. 211
10.5 Probabilistic encryption	p. 216
10.6 Efficient probabilistic encryption	p. 221
11 Identification schemes	p. 229
11.1 Introduction	p. 229
11.2 Interactive proofs	p. 231
11.3 Zero knowledge	p. 235
11.4 Perfect zero-knowledge proofs	p. 236
11.5 Computational zero knowledge	p. 240
11.6 The Fiat-Shamir identification scheme	p. 246
Appendix 1 Basic mathematical background	p. 250
A1.1 Order notation	p. 250
A1.2 Inequalities	p. 250
Appendix 2 Graph theory definitions	p. 252
Appendix 3 Algebra and number theory	p. 253
A3.1 Polynomials	p. 253
A3.2 Groups	p. 253
A3.3 Number theory	p. 254
Appendix 4 Probability theory	p. 257
Appendix 5 Hints to selected exercises and problems	p. 261
Appendix 6 Answers to selected exercises and problems	p. 268
Bibliography	p. 278
Index	p. 287

Available:*

On Order

Summary

Summary

Author Notes

Reviews 1

Choice Review

Table of Contents