I am again in weird state, this time recommending a book that is dedicated to my 60th birthday. But no matter how weird this may be to do so, I really admire the determination reflected in such a project (of composing a book of tutorials with different authors, let alone with a firm deadline).

I believe that the following extracts from the book, edited and prefaced by Yehuda Lindell, provide a better description than I can provide (let alone at the current moment).

The seven tutorials appear as chapteers of the book. Two of the chapters were already posted on ECCC (see TR17-065 and TR17-067) and I am told that the other chapters will also be posted there soon.

**Updates**: See also
TR17-084,
TR17-112,
TR17-113,

This is a graduate textbook of advanced tutorials on the theory of cryptography and computational complexity. In particular, the chapters explain aspects of garbled circuits, public-key cryptography, pseudorandom functions, one-way functions, homomorphic encryption, the simulation proof technique, and the complexity of differential privacy. Most chapters progress methodically through motivations, foundations, definitions, major results, issues surrounding feasibility, surveys of recent developments, and suggestions for further study.

The book is appropriate for graduate tutorials and seminars, and for self-study by experienced researchers, assuming prior knowledge of the theory of cryptography.

*Garbled Circuits as Randomized Encodings of Functions: a Primer*
by Benny Applebaum.
Yao's garbled circuit construction is a central cryptographic tool
with numerous applications. This chapter reviews garbled circuits
from a foundational point of view under the framework of randomized encod-
ing of functions, including positive and negative results and a sample of
basic applications.

*The Complexity of Public-Key Cryptography*
by Boaz Barak.
This chapter surveys what is known (and the many things that are not known)
about the computational assumptions that can enable public-key cryptography,
and the qualitative dierences between these assumptions
and those that are known to enable private-key cryptography.

*Pseudorandom Functions: Three Decades Later*
by Andrej Bogdanov and Alon Rosen.
Pseudorandom functions are an extremely influential abstraction,
with applications ranging from message authentication to barriers in
proving computational complexity lower bounds. This chapter surveys various
incarnations of pseudorandom functions, giving self-contained proofs of key
results from the literature.

*The Many Entropies in One-Way Functions*
by Iftach Haitner and Salil Vadhan.
This chapter introduces two recent computational notions of entropy,
shows that they can be easily found in any one-way function, and uses them
to present simpler and more effecient constructions of pseudorandom generators
and statistically hiding commitments from one-way functions.

*Homomorphic Encryption*
by Shai Halevi.
Fully homomorphic encryption is a relatively new discovery
and has gained much attention.
This chapter provides a tutorial on the topic, from definitions
and properties, to constructions and applications.

*How to Simulate It: A Tutorial on the Simulation Proof Technique*
by Yehuda Lindell.
The simulation paradigm is central to cryptographic def-
initions and proofs. This chapter consists of a systematic tutorial on how
simulation-based proofs work, from semantic security through zero knowledge
and finally secure computation.

*The Complexity of Differential Privacy*
by Salil Vadhan.
Differential privacy is a theoretical framework for
ensuring the privacy of individual-level data
when performing statistical analysis of privacy-sensitive datasets.
The goal of this chapter is to convey the deep connections
between differential privacy and a variety of other topics
in computational complexity, cryptography,
and theoretical computer science at large.

See the book's webpage.

Back to list of Oded's choices.