Modern cryptology more and more employs mathematically rigorous concepts and methods from complexity theory. Conversely, current research topics in complexity theory often are motivated by questions and problems from cryptology. This book takes account of this situation and therefore its subject is what may be dubbed "cryptocomplexity,'' some sort of symbiosis of these two areas. 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.

First book focusing on the interrelation of Cryptology and Complexity Theory Includes supplementary material: sn.pub/extras

Autorentext

Prof. Dr. Jörg Rothe und seine Doktorandin Dorothea Baumeister arbeiten an der Heinrich-Heine-Universität Düsseldorf im Gebiet Computational Social Choice. Claudia Lindner hat im Gebiet Cake-cutting geforscht und promoviert an der University of Manchester. Prof. Dr. Irene Rothe arbeitet als Informatikerin an der Hochschule Bonn-Rhein-Sieg in Sankt Augustin.

Inhalt
to Cryptocomplexity.- Foundations of Computer Science and Mathematics.- Foundations of Complexity Theory.- Foundations of Cryptology.- Hierarchies Based on NP.- Randomized Algorithms and Complexity Classes.- RSA Cryptosystem, Primality, and Factoring.- Other Public-Key Cryptosystems and Protocols.