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 adhoc 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 (oneway functions),
pseudorandomness and zeroknowledge proofs.
ISBN 0521830842
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 twovolume 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.
Preface
See preface to the entire work
Foundations of Cryptography.
We highlight the following points:

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.

It makes little sense to make assumptions regarding
the specific strategy that the adversary may use.
The only assumptions that can be justified refer
to the computational abilities of the adversary.

The design of cryptographic systems has to be based on firm foundations;
whereas adhoc 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.
 We will present some of these paradigms, approaches and techniques
as well as some of the fundamental results obtained using them.
 Our emphasis 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.
 The most relevant background for this work is provided by basic
knowledge of algorithms (including randomized ones),
computability and elementary probability theory.
Background on (computational) number theory,
which is required for specific implementations of certain
constructs, is not really required here.

Most of modern cryptography relies on the ability to generate
instances of hard problems. Such ability is captured in the
definition of oneway function
(see Volume 1).
Preface to the current volume
The current volume is the second part (or volume) of the twovolume work
Foundations
of Cryptography. The first part (i.e.,
Volume 1)
consists of an introductory chapter [Chapter 1],
followed by chapters on computational difficulty (oneway functions),
pseudorandomness and zeroknowledge proofs [Chapters 24, 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 highlevel structure of the current volume is as follows:
 Chapter 5: Encryption Schemes
The Basic Setting and Definitions of Security (Sec. 5.1 and 5.2)
Constructions of Secure Encryption Schemes (Sec. 5.3)
Advanced material (Sec. 5.4 and 5.5.15.5.3)
 Chapter 6: Digital Signature and Message Authentication
Definitional Issues (Sec. 6.1)
Lengthrestricted signature scheme (Sec. 6.2)
Basic Constructions (Sec. 6.3 and 6.4)
Advanced material (Sec. 6.5 and 6.6.16.6.3)
 Chapter 7: General Cryptographic Protocols
A detailed overview (Sec. 7.1)
Advanced material (all the rest):
The twoparty case (Sec. 7.27.4)
The multiparty case (Sec. 7.5 and 7.6)
 Appendix C: Corrections and Additions to Volume 1
 Bibliography and Index
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 wellknown,
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 CSundergraduate 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 highlevel sketch of the main ideas,
and only later pass to the technical details.
Passage from highlevel 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.
Teaching
(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 onesemester 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 twosemester 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 onesemester course on Foundations of Cryptography.
Depending on the class, each lecture consists of 5090 minutes.
Lectures 115 are covered by Volume 1,
whereas Lectures 1628 are covered by the current (second) volume.
 Lecture 1: Introduction, Background, etc (depending on class)
 Lecture 25: Computational Difficulty (OneWay Functions)
Main: Definition (Sec. 2.2), HardCore Predicates (Sec. 2.5)
Optional: Weak implies Strong (Sec. 2.3), and Sec. 2.4.22.4.4
 Lecture 610: Pseudorandom Generators
Main: Definitional issues and a construction (Sec. 3.23.4)
Optional: Pseudorandom Functions (Sec. 3.6)
 Lecture 1115: ZeroKnowledge Proofs
Main: Some definitions and a construction (Sec. 4.2.1, 4.3.1, 4.4.14.4.3)
Optional: Sec. 4.2.2, 4.3.2, 4.3.34.3.4, 4.4.4
 Lecture 1620: Encryption Schemes
Main: Definitions and constructions (Sec. 5.1, 5.2.15.2.4, 5.3.25.3.4)
Optional: Beyond passive notions of security (overview, Sec. 5.4.1)
 Lecture 2124: Signature Schemes
Definitions and constructions (Sec. 6.1, 6.2.16.2.2, 6.3.1.1, 6.4.16.4.2)
 Lecture 2528: General Cryptographic Protocols
The definitional approach and a general construction (overview, Sec. 7.1).
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 reorganizing
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 oneway functions
or secure protocols with zeroknowledge 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
Preface
Chapter 5: Encryption Schemes

5.1 The Basic Setting
5.1.1 PrivateKey versus PublicKey Schemes
5.1.2 The Syntax of Encryption Schemes

5.2 Definitions of Security
5.2.1 Semantic Security
5.2.2 Indistinguishability of Encryptions
5.2.3 Equivalence of the Security Definitions
5.2.4 Multiple Messages
5.2.5* A uniformcomplexity treatment

5.3 Constructions of Secure Encryption Schemes
5.3.1* StreamCiphers
5.3.2 Preliminaries: BlockCiphers
5.3.3 Privatekey encryption schemes
5.3.4 Publickey encryption schemes

5.4* Beyond eavesdropping security
5.4.1 Overview
5.4.2 Keydependent passive attacks
5.4.3 Chosen plaintext attack
5.4.4 Chosen ciphertext attack
5.4.5 Nonmalleable encryption schemes

5.5 Miscellaneous
5.5.1 On Using Encryption Schemes
5.5.2 On Information Theoretic Security
5.5.3 On Some Popular Schemes
5.5.4 Historical Notes
5.5.5 Suggestion for Further Reading
5.5.6 Open Problems
5.5.7 Exercises
Chapter 6: Digital Signatures and Message Authentication

6.1 The Setting and Definitional Issues
6.1.1 The two types of schemes: a brief overview
6.1.2 Introduction to the unified treatment
6.1.3 Basic mechanism
6.1.4 Attacks and security
6.1.5* Variants

6.2 Lengthrestricted signature scheme
6.2.1 Definition
6.2.2 The power of lengthrestricted signature schemes
6.2.3* Constructing collisionfree hashing functions

6.3 Constructions of Message Authentication Schemes
6.3.1 Applying a pseudorandom function to the document
6.3.2* More on HashandHide and statebased MACs

6.4 Constructions of Signature Schemes
6.4.1 Onetime signature schemes
6.4.2 From onetime signature schemes to general ones
6.4.3* Universal OneWay Hash Functions and using them

6.5* Some Additional Properties
6.5.1 Unique signatures
6.5.2 Supersecure signature schemes
6.5.3 Offline/online signing
6.5.4 Incremental signatures
6.5.5 Failstop signatures

6.6 Miscellaneous
6.6.1 On Using Signature Schemes
6.6.2 On Information Theoretic Security
6.6.3 On Some Popular Schemes
6.6.4 Historical Notes
6.6.5 Suggestion for Further Reading
6.6.6 Open Problems
6.6.7 Exercises
Chapter 7: General Cryptographic Protocols

7.1 Overview
7.1.1 The Definitional Approach and Some Models
7.1.2 Some Known Results
7.1.3 Construction Paradigms

7.2* The TwoParty Case: Definitions
7.2.1 The syntactic framework
7.2.2 The semihonest model
7.2.3 The malicious model

7.3* Privately Computing (2Party) Functionalities
7.3.1 Privacy reductions and a composition theorem
7.3.2 The 1outofk OT protocol  definition and construction
7.3.3 Privately computing a multiplicationgate
7.3.4 The circuit evaluation protocol

7.4* Forcing (2party) SemiHonest Behavior
7.4.1 The protocol compiler  motivation and overview
7.4.2 Security reductions and a composition theorem
7.4.3 The compiler  functionalities in use
7.4.4 The compiler itself

7.5* Extension to the MultiParty Case
7.5.1 Definitions
7.5.2 Security in the SemiHonest Model
7.5.3 The Malicious Models  Overview and Preliminaries
7.5.4 The first compiler  Forcing SemiHonest Behavior
7.5.5 The second compiler  Effectively Preventing Abort

7.6* Perfect Security in the Private Channel Model
7.6.1 Definitions
7.6.2 Security in the SemiHonest Model
7.6.3 Security in the Malicious Model

7.7 Miscellaneous
7.7.1* Three deferred issues
7.7.2* Concurrent Executions
7.7.3 Concluding Remarks
7.7.4 Historical Notes
7.7.5 Suggestion for Further Reading
7.7.6 Open Problems
7.7.7 Exercises
Appendix C: Corrections and Additions to Volume 1

C.1 Enhanced Trapdoor Permutations

C.2 On Variants of Pseudorandom Functions

C.3 On Strong Witness Indistinguishability
C.3.1 On parallel composition
C.3.2 On Theorem 4.6.8 and an afterthought
C.3.3 Consequences

C.4 On NonInteractive ZeroKnowledge
C.4.1 On NIZKs with efficient prover strategies
C.4.2 On Unbounded NIZKs
C.4.3 On Adaptive NIZKs

C.5 Some developments regarding zeroknowledge
C.5.1 Composing zeroknowledge protocols
C.5.2 Using the adversary's program in the proof of security

C.6 Additional Corrections and Comments

C.7 Additional Mottoes
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
 On page 436, Item 1, the descryption fits the privatekey case.
In the publickey case, $A_1$ should be given input $(e,z)$,
rather than $(1^n,z)$. The same holds for Item 1 on page 443.
[Rupeng Yang]
 On page 443, Item 1: See page 436, Item 1.
 On page 475: All mentions of the authenticated keyexchange
should be unauthenticated keyexchange, and vice verse. [Haiyang Xue]
 On page 481, Footnote 58, the Decisional Diffie Hellman problem
is wrongly stated. One should require instead that $P=2P'+1$,
with $P'$ being a prime, and that $g$ is a generator
of the set of quadratic residues mod $P$.
[Luca Trevisan; for further details, see
Luca's email.]
 Addendum to the guideline of Exer 5.2 (on page 482):
To show that the two distributions are statistically far apart,
consider the event $S$ such that $(r,s)\in S$ if and only if
there exists an $n$bit string $K$ such that $D_K(s)=r$.
 On top of page 622,
the simulator constructed to demonstrate the point
should only output the view $s$, rather than the view
coupled with the output $(s,F(s))$. [Carmit Hazay]
 On constructing 1outofk OT (Const. 7.3.5 and Prop 7.3.6).
The current description is fine if $k=2$,
which actually suffices via additional reductions.
For $k>2$ one should either modify Construction 7.3.5
or make stringer assumptions about the trapdoor permutation used.
The simplest modification is to let the sender select $k$
indices of permutations (rather than a single one), and have
the parties use the $i$th index for $x_i$ and $y_i$. [Ron Rothblum]
 On top of page 698, item 1 (in the discussion of
the (first) malicious model)
refers to a convention made in Sec. 7.2.3
(which can be found in Footnote 17 on page 628).
As pointed out by Yuval Ishai, in the multiparty context,
it seems that the special abortsymbol convention
(including a modified functionality) has to be used.
In retrospect, we prefer this convention also in the twoparty case.
 Regarding the issue of fairness (cf. Sec. 7.2.3 and 7.7.1.1):
See an important revisiting of this issue in
Complete
Fairness in Secure TwoParty Computation
by D. Gordon, C. Hazay, J. Katz, and Y. Lindell (STOC'08, pp. 413422).
 Errata regarding the paragraph following Thm 7.5.14 (on p. 708)
and the 2nd paragraph on the 1st item on page 709:
This assertion is correct only if each output bit in the circuit
is a nonlinear function of each of the input bits,
which means that a multiplication gate appears on each inputoutput path.
This can be enforced by augmenting the circuit with gates that multiply
each input bit by itself
(or multiply each bit output by itself before outputting it).
[Peter Scholl]
 Regarding Section 7.6:
See a full proof of the BGW Protocol
for perfectlysecure multiparty computation,
provided by Gilad Asharov and Yehuda Lindell, 2011.
 Regarding NIZK and enhanced trapdoor permutations
(see Appendices C.1 and C.4.1): Jonathan Katz has pointed out that
although the notion of enhanced trapdoor permutations (Def. C.1.1)
suffices for constructing Oblivious Transfer (see Sec. 7.3.2),
it does not seem to suffice for constructing a NIZK
(as outlined in Remark 4.10.6 and patched in Apdx C.4.1).
A seemingly stronger notion that does suffice (for constructing a NIZK)
may be called a doubly enhanced trapdoor permutation
and is defined as an enhanced trapdoor permutation for which
given an $n$bit long description of a permutation it is feasible
to generate a random pair $(x,r)$ such that $x$ is the preimage
under the permutation of the domain element generated by
the domainsampling algorithm on coins $r$.
For further details, see
note [Nov. 2008 (rev'ed Oct. 2009)].
More about enhanced trapdoor permutations:
See Ron Rothblum's
Taxonomy
of Enhanced Trapdoor Permutations, 2010.
Actually, it may be best to start with a later paper by Ron any myself,
titled Enhancements of Trapdoor Permutations.
Material available online (see Copyright notice below):
Permission is granted for (noncommercial)
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.