zbMATH — the first resource for mathematics

Foundations of cryptography. Vol. 1. Basic tools. (English) Zbl 1007.94016
Cambridge: Cambridge University Press. xx, 372 p. (2001).
This book is the first volume of a three-volume book presenting the basic concepts, techniques and results in cryptography. It contains an introductory chapter to discuss the goals of cryptography and to present the computational models and some elementary background from probability theory, as well as basic tools: one-way functions, pseudorandomness, and zero-knowledge proofs. Chapter 2 of the book deals with one-way functions. Strong and weak one-way functions are defined, and it is proven that the existence of weak one-way functions implies the existence of strong one-way functions. (So far, it is not know that one-way functions exist.) Hard-core predicates are also defined, and it is proven that every one-way function has a hard-core predicate. In chapter 3, pseudorandom generators are defined as computationally indistinguishable from truly random sequences by efficient algorithms, and they are constructed based on various types of one-way functions and one-way permutations. In chapter 4, the author discusses zero-knowledge proof systems. The main result is a method for constructing zero-knowledge proof systems for every language in NP. This method can be implemented using any bit-commitment scheme, which can be implemented using any pseudorandom generator. In addition, advanced aspects of the concept of zero-knowledge and their effects on the applicability of this concept are also discussed.
This book is well-written. It is aimed at presenting firm foundations for cryptography. (The foundations of cryptography, according to the author’s viewpoint, are the paradigms, approaches, and techniques used to conceptualize, define, and provide solutions to natural “security concerns”.) This book is intended to serve as both a textbook and a reference text.

94A60 Cryptography
94-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory
68P25 Data encryption (aspects in computer science)
65C10 Random number generation in numerical analysis
Full Text: DOI