Providing Sound Foundations for Cryptography:
On the work of Shafi Goldwasser and Silvio Micali
edited by Oded Goldreich
To appear in ACM's book series
Cryptography is concerned with the construction of schemes
that withstand any abuse: 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 1980's, 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.
The current book celebrates these works,
which were the basis for bestowing the 2012 Turing Award
upon Shafi Goldwasser and Silvio Micali.
[Extract from the book's preface]
TITLE: Providing sound foundations for cryptography
SUBTITLE: On the work of Shafi Goldwasser and Silvio Micali
ACM production of this book included re-typing the original papers
(for Part II), rather than using facsimiles of these papers,
and changing various aspects of the texts of Part III
(e.g., the bibliographic conventions
and the numbering of theorem-like environments).
These production decisions were forced upon the editor,
who strongly objected them both per merits
and due to the likelihood of errors caused by implementing them.
Neither the editor nor the authors assume responsibility
for the errors introduced in this process.
The reader is advised to fetch the original versions
of the surveys appearing in Part III from the authors
(mine are available here).
- Part I: Biographies, Interviews, and Award Lectures
- Shafi Goldwasser: A story behind every problem,
a biography by Michelle Waitzman.
- Silvio Micali: One obsession at a time,
a biography by Michelle Waitzman.
- Interview of Shafi Goldwasser by Alon Rosen.
- Interview of Silvio Micali by Stephen Ibaraki.
- Turing award lecture by Shafi Goldwasser.
- Turing award lecture by Silvio Micali.
- Part II: Original papers
- Probabilistic Encryption
- The Knowledge Complexity of Interactive Proof Systems
- How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits
- How to Construct Random Functions
- A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
- Proofs that Yield Nothing but their Validity or All La
nguages in NP Have Zero-Knowledge Proof Systems
- How to Play any Mental Game:
A Completeness Theorem for Protocols with Honest Majority
- Completeness Theorems for Non-Cryptographic Fault-Tolerant
- Multi-Prover Interactive Proofs: How to Remove Intractability
- Non-Interactive Zero-Knowledge (NIZK) Proof Systems
- Part III: Perspectives
- On the foundations of cryptography (by O.G.)
- On the impact of cryptography on complexity theory (by O.G.)
- On some non-cryptographic works of Goldwasser and Micali (by O.G.)
- Fundamentals of Fully Homomorphic Encryptionm by Zvika Brakerski
- Interactive Proofs for Lattice Problems by Daniele Micciancio
- Following a tangent of proofs by Johan Hastad
- Tutorial on Concurrent Zero Knowledge by Rafael Pass
- Doubly-Efficient Interactive Proofs by Guy Rothblum
- Computational Entropy by Salil Vadhan
- Survey of Leakage-Resilient Cryptography
by Yael Tauman Kalai and Leonid Reyzin
- Brief biographies of the editor and the authors.
The original papers reproduced in Chapters 8-16
were co-authored also by researchers other
than Shafi Goldwasser and Silvio Micali.
The list, in chronological order, includes
Manuel Blum (Chapter 9),
Charles Rackoff (Chapter 8),
myself (Chapters 10 and 12-13),
Ronald Rivest (Chapter 11),
Avi Wigderson (Chapters 12-13 and 15-16),
Paul Feldman (Chapter 14),
Michael Ben-Or (Chapters 15-16),
and Joe Kilian (Chapter 16).
Indeed, it is due to start the acknowledgments
by thanking these researchers.
Needless to say, thanks are also due to the many researcher
on which all these works were built.
Next, I would like to thank the colleagues who have
contributed scientific chapters to this book. The list includes
Zvika Brakerski (Chapter 20),
Daniele Micciancio (Chapter 21),
Johan Hastad (Chapter 22),
Rafael Pass (Chapter 23),
Guy Rothblum (Chapter 24),
Salil Vadhan (Chapter 25),
and Yael Tauman Kalai and Leonid Reyzin (Chapter 26).
Special thanks to Michelle Waitzman who wrote the two biographies
(appearing as Chapters 1-2),
and to Alon Rosen and Stephen Ibaraki for conducting the two interviews
(appearing as Chapters 3 and 4, respectively).
Lastly, I wish to thank Tamer Ozsu, the editor-in-chief of ACM Books,
for monitoring and assisting the writing and production of this volume.
Back to Oded Goldreich's homepage.