Tutorials on the Foundations of Cryptography

edited by Yehuda Lindell

Oded's comments

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,

From the book's back-cover and preface

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.