Complexity Theory and Cryptology: An Introduction to Cryptocomplexity

Front Cover
Springer Science & Business Media, Jul 22, 2005 - Computers - 478 pages

Modern cryptology increasingly employs mathematically rigorous concepts and methods from complexity theory. Conversely, current research topics in complexity theory are often motivated by questions and problems from cryptology. This book takes account of this situation, and therefore its subject is what may be dubbed "cryptocomplexity'', a kind of symbiosis of these two areas.

This book is written for undergraduate and graduate students of computer science, mathematics, and engineering, and can be used for courses on complexity theory and cryptology, preferably by stressing their interrelation. Moreover, it may serve as a valuable source for researchers, teachers, and practitioners working in these fields. Starting from scratch, it works its way to the frontiers of current research in these fields and provides a detailed overview of their history and their current research topics and challenges.

 

Contents

Contents
1
Foundations of Computer Science and Mathematics
9
Foundations of Complexity Theory
53
Foundations of Cryptology 127
126
Hierarchies Based on NP
171
Randomized Algorithms and Complexity Classes
261
RSA Cryptosystem Primality and Factoring
311
Other PublicKey Cryptosystems and Protocols 361
360
List of Figures
413
Index
444
Copyright

Other editions - View all

Common terms and phrases