The Foundations of Cryptography - Volume 2

Oded Goldreich


Cryptography is concerned with the construction of schemes that should maintain a desired functionality, even under malicious attempts aimed at making them deviate from it. The design of cryptographic systems has to be based on firm foundations; whereas ad-hoc approaches and heuristics are a very dangerous way to go. This work is aimed at presenting firm foundations for cryptography. The foundations of cryptography are the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural ``security concerns''. The emphasis of the work is on the clarification of fundamental concepts and on demonstrating the feasibility of solving several central cryptographic problems. The current book is the second volume of this work, and it focuses on the main applications of Cryptography: encryption schemes, signature schemes and secure protocols. The first volume focused on the main tools of Modern Cryptography: computational difficulty (one-way functions), pseudorandomness and zero-knowledge proofs.

ISBN 0-521-83084-2
Published in US in May 2004.
See purchase information.
Publisher: Cambridge University Press
(see the publisher's page for this volume).

This volume is part of the two-volume work Foundations of Cryptography (see Volume 1).
For a brief introduction to the Foundations of Cryptography, see surveys. Preliminary drafts are also available here.
For further suggestions regarding teaching, see notes.

This page includes the volume's preface, Teaching Tips, Table of Contents, answers to frequently asked questions, and List of Corrections.


See preface to the entire work Foundations of Cryptography. We highlight the following points:

Preface to the current volume

The current volume is the second part (or volume) of the two-volume work Foundations of Cryptography. The first part (i.e., Volume 1) consists of an introductory chapter [Chapter 1], followed by chapters on computational difficulty (one-way functions), pseudorandomness and zero-knowledge proofs [Chapters 2-4, respectively]. The current volume consists of three chapters, which treat encryption schemes [Chapter 5], signature schemes [Chapter 6], and general cryptographic protocols [Chapter 7], respectively. Also included is an appendix that provides corrections and additions to Volume 1. The high-level structure of the current volume is as follows:

Historical notes, suggestions for further reading, some open problems and some exercises are provided at the end of each chapter. The exercises are mostly designed to help and test the basic understanding of the main text, not to test or inspire creativity. The open problems are fairly well-known, still we recommend to check their current status (e.g., in this website).

Using this work

The work is aimed to serve both as a textbook and a reference text. That is, it is aimed at serving both the beginner and the expert. In order to achieve this aim, the presentation of the basic material is very detailed so to allow a typical CS-undergraduate to follow it. An advanced student (and certainly an expert) will find the pace (in these parts) way too slow. However, an attempt was made to allow the latter reader to easily skip details obvious to him/her. In particular, proofs are typically presented in a modular way. We start with a high-level sketch of the main ideas, and only later pass to the technical details. Passage from high-level descriptions to lower level details is typically marked by phrases such as details follow. More advanced material is typically presented at a faster pace and with less details. Thus, we hope that the attempt to satisfy a wide range of readers will not harm any of them.


(See also Teaching Notes.)

The material presented in this work is, on one hand, way beyond what one may want to cover in a course, and on the other hand falls very short of what one may want to know about Cryptography in general. To assist these conflicting needs we make a distinction between basic and advanced material, and provide suggestions for further reading (in the last section of each chapter). In particular, sections, subsections, and subsubsections marked by an asterisk (*) are intended for advanced reading.

This work are supposed to provide all material for a course on Foundations of Cryptography. For a one-semester course, the teacher will definitely need to skip all advanced material (marked by an asterisk) and maybe even some basic material: see suggestion below. This should allow, depending on the class, to cover the basic material at a reasonable level (i.e., cover all material marked as ``main'' and some of the ``optional''). This work can also serve as textbook for a two-semester course. Either way, the current volume only covers the second half of the material mentioned above. The first half is covered in Volume 1.

Following is our suggestion for a one-semester course on Foundations of Cryptography. Depending on the class, each lecture consists of 50-90 minutes. Lectures 1-15 are covered by Volume 1, whereas Lectures 16-28 are covered by the current (second) volume.

A comment regarding the current volume

Writing the first volume was fun. In comparison to the current volume, the definitions, constructions and proofs in the first volume are relatively simple and easy to write. Furthermore, in most cases, the presentation could safely follow existing texts. Consequently, the writing effort was confined to re-organizing the material, revising existing texts, and augmenting them by additional explanations and motivations.

Things were quite different with respect to the current volume. Even the simplest notions defined in the current volume are more complex than most notions treated in the first volume (e.g., contrast secure encryption with one-way functions or secure protocols with zero-knowledge proofs). Consequently, the definitions are more complex, and many of the constructions and proofs are more complex. Furthermore, in most cases, the presentation could not follow existing texts. Indeed, most effort had to be (and was) devoted to the actual design of constructions and proofs, which were only inspired by existing texts.

It seems that the fact that writing this volume required so much effort implies that this volume may be very valuable: Even experts may be happy to be spared the hardship of trying to understand this material based on the original research manuscripts.

Table of Contents


Chapter 5: Encryption Schemes

Chapter 6: Digital Signatures and Message Authentication Chapter 7: General Cryptographic Protocols Appendix C: Corrections and Additions to Volume 1 Bibliography (approximately 200 entries)

Index (approximately 200 entries)

Frequently Asked Questions

Is there a solution manual of this book? Unfortunately, the answer is negative, but we believe that the guidelines for the exercises provide sufficient clues.

When will this volume 2 appear? It has already appeared (in Spring 2004).

See also answers to other Frequently Asked Questions.

List of Corrections

Material available on-line (see Copyright notice below):

Permission is granted for (non-commercial) use of the following drafts:

Also available (older related material, superseeded by the above):

Copyright (C symbol) 2003 by Oded Goldreich. Permission to make digital or hard copies of part or all of the material posted here is currently granted without fee provided that copies are made only for personal or classroom use, are not distributed for profit or commercial advantage, and that new copies bear this notice and the full citation on the first page. Abstracting with credit is permitted. This work will be published in 2004 by Cambridge University Press, and the relevant copyrights have been transferred to it. Once published, permission to make digital or hard copies of part or all of the material posted here will be granted without fee provided that copies are made only for personal use and are not distributed in any way.

Back to the top or to Oded Goldreich's homepage.