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.

This book honors Professor Oded Goldreich, a pioneering scientist, educator, and mentor. Oded was instrumental in laying down the foundations of cryptography, and he inspired the contributing authors, Benny Applebaum, Boaz Barak, Andrej Bogdanov, Iftach Haitner, Shai Halevi, Yehuda Lindell, Alon Rosen, and Salil Vadhan, themselves leading researchers on the theory of cryptography and computational complexity. The book is appropriate for graduate tutorials and seminars, and for self-study by experienced researchers, assuming prior knowledge of the theory of cryptography.

Autorentext

Yehuda Lindell is a professor in the Dept. of Computer Science of Bar-Ilan University; his main research interests are in the field of cryptography, focusing on secure protocols, and questions of feasibility and efficiency. Benny Applebaum is a professor at the School of Electrical Engineering at Tel-Aviv University; his main interests are the foundations of cryptography and computational complexity. Boaz Barak is the Gordon McKay Professor of Computer Science at Harvard University; his research interests include all areas of theoretical computer science and in particular cryptography and computational complexity. Andrej Bogdanov is an associate professor in the Dept. of Computer Science and Engineering and an associate director of the Institute for Theoretical Computer Science and Communications at The Chinese University of Hong Kong; his research interests are computational complexity and the foundations of cryptography. Iftach Haitner is a faculty member in the School of Computer Science at Tel-Aviv University; his main interests are cryptography and computational complexity. Shai Halevi is a Principal Research Staff Member at the IBM T.J. Watson Research Center, with research interests in cryptography. Alon Rosen is a professor in the School of Computer Science at the Herzliya Interdisciplinary Center (IDC); his main interests are cryptography and computational complexity. Salil Vadhan is the Vicky Joseph Professor of Computer Science and Applied Mathematics at Harvard University; his research areas include computational complexity, cryptography, randomness in computation, and data privacy.

Inhalt

Garbled Circuits as Randomized Encodings of Functions: A Primer.- The Complexity of Public-Key Cryptography.- Pseudorandom Functions: Three Decades Later.- The Many Entropies in One-Way Functions.- Homomorphic Encryption.- How to Simulate It: A Tutorial on the Simulation Proof Technique.- The Complexity of Differential Privacy.