Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali

Description

A cryptographic scheme is constructed so as to maintain a desired functionality, even under malicious attempts aimed at making it deviate from its prescribed behavior. The design of cryptographic systems must be based on firm foundations, whereas ad hoc approaches and heuristics are a very dangerous way to go. These foundations were developed mostly in the 1980s, in works that are all co-authored by Shafi Goldwasser and/or Silvio Micali. These works have transformed cryptography from an engineering discipline, lacking sound theoretical foundations, into a scientific field possessing a well-founded theory, which influences practice as well as contributes to other areas of theoretical computer science. This book celebrates these works, which were the basis for bestowing the 2012 A.M. Turing Award upon Shafi Goldwasser and Silvio Micali. A significant portion of this book reproduces some of these works, and another portion consists of scientific perspectives by some of their former students. The highlight of the book is provided by a few chapters that allow the readers to meet Shafi and Silvio in person. These include interviews with them, their biographies and their Turing Award lectures. Contents Preface Acknowledgments Photo and Text Credits PART I. BIOGRAPHIES, INTERVIEWS, AND AWARD LECTURES 1. A Story Behind Every Problem: A Brief Biography of Shafi Goldwasser 2. One Obsession at a Time: A Brief Biography of Silvio Micali 3. An Interview with Shafi Goldwasser 4. An Interview with Silvio Micali 5. The Cryptographic Lens: Shafi Goldwasser’sTuring Lecture 6. Proofs, According to Silvio: Silvio Micali’s Turing Lecture PART II. ORIGINAL PAPERS 7. Probabilistic Encryption 8. The Knowledge Complexity of Interactive Proof Systems 9. How to Generate Cryptographically Strong Sequences of Pseudorandom Bits 10. How to Construct Random Functions 11. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks 12. Proofs that Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems 13. How to Play Any Mental Game: A Completeness Theorem for Protocols with Honest Majority 14. Non-Interactive Zero-Knowledge (NIZK) Proof Systems 15. Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation 16. Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions PART III. PERSPECTIVES 17. On the Foundations of Cryptography 18. On the Impact of Cryptography on Complexity Theory 19. On Some Noncryptographic Works of Goldwasser and Micali 20. Fundamentals of Fully Homomorphic Encryption 21. Interactive Proofs for Lattice Problems 22. Following a Tangent of Proofs 23. A Tutorial on Concurrent Zero-Knowledge 24. Doubly Efficient Interactive Proofs 25. Computational Entropy 26. A Survey of Leakage-Resilient Cryptography Editor and Author Biographies Blank Page