Foundations of cryptography. Vol. 2. Basic applications.

*(English)*Zbl 1068.94011
Cambridge: Cambridge University Press (ISBN 0-521-83084-2/hbk). xxii, 373-798 p. (2004).

As a continuation of the book of O. Goldreich [Foundations of cryptography – basic tools (Cambridge University Press, Cambridge) (2001; Zbl 1007.94016)], the book under review consists of three chapters to deal with encryption, signatures, and general cryptographic protocols.

In the chapter entitled encryption schemes, an encryption scheme is rigorously defined by means of probabilistic polynomial-time algorithms, including private-key scheme and public-key scheme. A semantically secure encryption scheme and indistinguishable encryptions, for private-key and public-key, in single-message and multiple-message, are defined, and their equivalence is proven. For the existence of semantically secure private-key encryption schemes, two constructions, the state-based encryption scheme using an on-line pseudorandom generator and the block-cipher based on pseudorandom functions, are presented; for public-key, a simple block-cipher scheme using collections of trapdoor permutations, the randomized RSA based on the large hard-core conjecture for RSA, a public-key encryption scheme based on a collection of trap-door permutations having a hard-core, and the Blum-Goldwasser encryption scheme based on the intractability of factoring, are also presented. Similarly, for public-key, definitions of semantically secure and indistinguishable encryptions under key-dependent passive attack, their equivalence, and existence, are given. For an active attack, after formulating the chosen plaintext attack (resp. the chosen ciphertext attack), semantically secure and indistinguishable encryptions under chosen plaintext attacks (resp. a priori or a posteriori chosen ciphertext attacks) are defined, and their equivalence is proven; existence under some assumptions is also proven using the aforementioned constructions or new constructions based on one-way functions or collections of enhanced trapdoor permutations. Additionally, non-malleable encryption schemes are also discussed.

In the chapter entitled digital signatures and message authentication, after defining a signature scheme, a secure private-key signature scheme, i.e., a secure message-authentication scheme, and a secure public-key signature scheme are rigorously defined. Constructions of message-authentication schemes using pseudorandom functions are given, and it is proven that secure message-authentication schemes exist if and only if one-way functions exist. For public-key signature schemes, constructions of signature schemes using one-way permutations, which do not necessarily have a trapdoor, are presented, and it is proven that if one-way permutations exist then secure public-key signature schemes exist.

The chapter entitled general cryptographic protocols deals with secure multi-part computations. After giving a review section, three sections are devoted to two-part protocols; the main result is proven: if collections of enhanced trapdoor permutations exist, then any two-part functionality can be securely computable in the malicious model. The treatment is extended to the multi-part case for proving the main result: if collections of enhanced trapdoor permutations exist, then any \(m\)-part functionality can be securely computable in each of the two malicious models, provided that a public-key infrastructure exists in the network. In addition, an alternative treatment of general secure multi-part protocols for the “private channel model” is presented.

The book is well written. It is aimed at serving both the beginner and the expert. Historical notes, suggestions for further reading, some open problems, and some exercises are provided at the end of each chapter.

In the chapter entitled encryption schemes, an encryption scheme is rigorously defined by means of probabilistic polynomial-time algorithms, including private-key scheme and public-key scheme. A semantically secure encryption scheme and indistinguishable encryptions, for private-key and public-key, in single-message and multiple-message, are defined, and their equivalence is proven. For the existence of semantically secure private-key encryption schemes, two constructions, the state-based encryption scheme using an on-line pseudorandom generator and the block-cipher based on pseudorandom functions, are presented; for public-key, a simple block-cipher scheme using collections of trapdoor permutations, the randomized RSA based on the large hard-core conjecture for RSA, a public-key encryption scheme based on a collection of trap-door permutations having a hard-core, and the Blum-Goldwasser encryption scheme based on the intractability of factoring, are also presented. Similarly, for public-key, definitions of semantically secure and indistinguishable encryptions under key-dependent passive attack, their equivalence, and existence, are given. For an active attack, after formulating the chosen plaintext attack (resp. the chosen ciphertext attack), semantically secure and indistinguishable encryptions under chosen plaintext attacks (resp. a priori or a posteriori chosen ciphertext attacks) are defined, and their equivalence is proven; existence under some assumptions is also proven using the aforementioned constructions or new constructions based on one-way functions or collections of enhanced trapdoor permutations. Additionally, non-malleable encryption schemes are also discussed.

In the chapter entitled digital signatures and message authentication, after defining a signature scheme, a secure private-key signature scheme, i.e., a secure message-authentication scheme, and a secure public-key signature scheme are rigorously defined. Constructions of message-authentication schemes using pseudorandom functions are given, and it is proven that secure message-authentication schemes exist if and only if one-way functions exist. For public-key signature schemes, constructions of signature schemes using one-way permutations, which do not necessarily have a trapdoor, are presented, and it is proven that if one-way permutations exist then secure public-key signature schemes exist.

The chapter entitled general cryptographic protocols deals with secure multi-part computations. After giving a review section, three sections are devoted to two-part protocols; the main result is proven: if collections of enhanced trapdoor permutations exist, then any two-part functionality can be securely computable in the malicious model. The treatment is extended to the multi-part case for proving the main result: if collections of enhanced trapdoor permutations exist, then any \(m\)-part functionality can be securely computable in each of the two malicious models, provided that a public-key infrastructure exists in the network. In addition, an alternative treatment of general secure multi-part protocols for the “private channel model” is presented.

The book is well written. It is aimed at serving both the beginner and the expert. Historical notes, suggestions for further reading, some open problems, and some exercises are provided at the end of each chapter.

Reviewer: Tao Renji (Beijing)