Complexity theory and cryptology. An introduction to cryptocomplexity. (Q2484164)

Though genesis and development of computational complexity differs from the genesis and development of cryptology, at one point of time these two areas eventually touched each other. As turned out both areas can gain significantly from interaction with the other one and in return provide motivation and ideas for further research. The book reflects this close relationship and provides introduction to both cryptology and complexity theory with special emphasis on their mutual pervasion. The book is structured in a way that makes it possible to use it for introductory courses in cryptology viewed from a complexity-theoretic perspective, in complexity theory with emphasis to potential applications in cryptology, or for joint introduction for both these areas. It must be noted, however, that the book is focused on theory, and avoids dealing with practical aspects of security engineering. Chapter 1 provides brief introduction into the main themes of the book as well as an overview of the subsequent chapters. The second chapter provides an introduction to those parts of mathematics and computer science that are relevant to complexity theory and cryptology. Particularly, foundations of algorithmics, theory of formal languages, recursive function theory, logic, algebra, number theory, graph theory, and probability theory are given here. Also a section on exercises and problems is included as well as bibliographic remarks and references for further study. Chapter 3 presents foundations of computational complexity theory. Here firstly basic tasks and notions are described followed by sections introducing in more detail complexity measures and classes as well as some basic theorems (speed-up, space hierarchy, time hierarchy). A separate section is given for the inclusion relationships among complexity classes between logarithmic and polynomial space. Special attention is then paid to complexity-bounded reducibilities among problems as well as to hardness and completeness notions, including proofs of NP-completeness for a number of problems. In the last section the class NP is investigated more closely and some further basic notions and results, like self-reducibility, Berman-Hartmanis isomorphism conjecture, one-way functions and UP class, are given. Foundations of cryptology are given in the fourth chapter. Here the first section introduces the formal definition of a cryptosystem followed by explanation of other basic notions, like different types of attacks, Kerckhoffs`s principle and authentication problems. Then some classical cryptosystems are presented together with examples of their cryptanalysis. Various modes of using block ciphers are also discussed in this section. Finally, a special section introduces the notion of perfect secrecy and provides relevant results of Shannon`s theory. Chapter 5 switches attention back to the complexity theory by introducing some important complexity hierarchies build upon NP. Boolean hierarchy over NP as well as polynomial hierachy and a close connection between them are covered there as well as various polynomial-time Turing reducibilities and alternating Turing machines. The theme ends with a section introducing the low and the high hierarchy within NP. Chapter 6 is the last one dealing with the computational complexity theory. Here randomized algorithms and corresponding probabilistic complexity classes, as well as Arthur-Merlin games and counting classes are introduced and discussed. Various concepts related to randomization are then used to prove certain lowness properties of the graph isomorphism problem, including lowness for probabilistic classes. In the last two chapters the reader is turned again towards cryptology topics. Chapter 7 firstly introduces the famous RSA public key cryptosystem and digital signature scheme based on it. As the primality problem and the factoring problem play key roles in use and security of the RSA (but also many other cryptosystems), various primality testing algorithms as well as some factoring methods are presented in separate sections. The RSA theme ends with a section discussing possible attacks and countermeasures. Chapter 8 gives a survey of important public key cryptosystems and cryptographic protocols. It begins with the description and discussion of the Diffie-Hellman secret-key agreement protocol and discrete logarithm problem, followed by the ElGamal public key cryptosystem and digital signature scheme, and Rabin`s public key cryptosystem. Then zero-knowledge protocols are introduced and zero-knowledge protocol for graph isomorphism and Fiat-Shamir identification scheme are presented to illustrate the idea. To further illustrate the basic design principles of public key cryptography a section on the Merkle-Hellman (``knapsack-based'') cryptosystem is given. Finally, the chapter introduces protocols for secret-key agreement and digital signatures that are based on associative, strongly noninvertible one-way functions. All chapters have a set of exercises and problems as well as a summary describing the historical development of the notions and results presented and providing bibliographic remarks and references for further study. A comprehensive bibliography makes the book a valuable source for researchers, teachers, and even practitioners working in complexity theory and cryptology. A useful book.