New Books

Foundations of Cryptography -- Basic Tools

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. This is done in a way independent of the particularities of some popular number theoretic examples. Thus, the most relevant background is basic knowledge of algorithms (including randomized ones), computability and elementary probability theory.

The current book is the first volume of this work, and it focuses on the main tools of Modern Cryptography: computational difficulty (one-way functions), pseudorandomness and zero-knowledge proofs. The next volume will focus on the main applications of Cryptography: encryption schemes, signature schemes and secure protocols. Fragments of the second volume are available online from http://www.wisdom.weizmann.ac.il/~oded/foc-vol2.html Together, the available material can serve as a textbook for a course on the Foundations of Cryptography. Teaching suggestions are provided in the current volume and are also available from http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html

The high-level structure of the current volume is as follows:

• Chapter 1: Introduction
  Main Topics covered by the work (Sec. 1.1)
  Background on Probability and Computation (Sec. 1.2 and 1.3)
  Motivation to the Rigorous Treatment (Sec. 1.4)
• Chapter 2: Computational Difficulty (One-Way Functions)
  Motivation and Definitions (Sec. 2.1 and 2.2)
  One-Way functions: Weak implies Strong (Sec. 2.3)
  Variants (Sec. 2.4) and advanced material (Sec. 2.6)
  Hard-Core Predicates (Sec. 2.5)
• Chapter 3: Pseudorandom Generators
  Motivation and Definitions (Sec. 3.1-3.3)
  Constructions based on One-Way Permutations (Sec. 3.4)
  Pseudorandom Functions (Sec. 3.6)
  Advanced material (Sec. 3.5 and 3.7)
• Chapter 4: Zero-Knowledge Proofs
  Motivation and Definitions (Sec. 4.1-4.3)
  Zero-Knowledge Proofs for NP (Sec. 4.4)
  Advanced material (Sec. 4.5-4.11)
• Appendix A: Brief Background on Computational Number Theory
• Appendix B: Brief Outline of Volume 2
• Bibliography and Index

Publisher's page for this volume: http://www.cup.org/Titles/79/0521791723.htm .

Please send your new book announcements to the newsletter editor at