Book contents
- Frontmatter
- Contents
- Preface
- Notation
- 1 Basics of cryptography
- 2 Complexity theory
- 3 Non-deterministic computation
- 4 Probabilistic computation
- 5 Symmetric cryptosystems
- 6 One way functions
- 7 Public key cryptography
- 8 Digital signatures
- 9 Key establishment protocols
- 10 Secure encryption
- 11 Identification schemes
- Appendix 1 Basic mathematical background
- Appendix 2 Graph theory definitions
- Appendix 3 Algebra and number theory
- Appendix 4 Probability theory
- Appendix 5 Hints to selected exercises and problems
- Appendix 6 Answers to selected exercises and problems
- Bibliography
- Index
Preface
Published online by Cambridge University Press: 06 July 2010
- Frontmatter
- Contents
- Preface
- Notation
- 1 Basics of cryptography
- 2 Complexity theory
- 3 Non-deterministic computation
- 4 Probabilistic computation
- 5 Symmetric cryptosystems
- 6 One way functions
- 7 Public key cryptography
- 8 Digital signatures
- 9 Key establishment protocols
- 10 Secure encryption
- 11 Identification schemes
- Appendix 1 Basic mathematical background
- Appendix 2 Graph theory definitions
- Appendix 3 Algebra and number theory
- Appendix 4 Probability theory
- Appendix 5 Hints to selected exercises and problems
- Appendix 6 Answers to selected exercises and problems
- Bibliography
- Index
Summary
This book originated in a well-established yet constantly evolving course on Complexity and Cryptography which we have both given to final year Mathematics undergraduates at Oxford for many years. It has also formed part of an M.Sc. course on Mathematics and the Foundations of Computer Science, and has been the basis for a more recent course on Randomness and Complexity for the same groups of students.
One of the main motivations for setting up the course was to give mathematicians, who traditionally meet little in the way of algorithms, a taste for the beauty and importance of the subject. Early on in the book the reader will have gained sufficient background to understand what is now regarded as one of the top ten major open questions of this century, namely the P = NP question. At the same time the student is exposed to the mathematics underlying the security of cryptosystems which are now an integral part of the modern ‘email age’.
Although this book provides an introduction to many of the key topics in complexity theory and cryptography, we have not attempted to write a comprehensive text. Obvious omissions include cryptanalysis, elliptic curve cryptography, quantum cryptography and quantum computing. These omissions have allowed us to keep the mathematical prerequisites to a minimum.
- Type
- Chapter
- Information
- Complexity and CryptographyAn Introduction, pp. ix - xPublisher: Cambridge University PressPrint publication year: 2006