Providing Sound Foundations for Cryptography

Description

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 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.

• Preface


• Acknowledgments


• Photo and Text Credits


• PART I BIOGRAPHIES, INTERVIEWS, AND AWARD LECTURES
  • A Story Behind Every Problem: A Brief Biography of Shafi Goldwasser
  • One Obsession at a Time: A Brief Biography of Silvio Micali
  • An Interview with Shafi Goldwasser
  • An Interview with Silvio Micali
  • The Cryptographic Lens: Shafi Goldwasser's Turing Lecture
  • Proofs, According to Silvio: Silvio Micali's Turing Lecture


• PART II ORIGINAL PAPERS
  • Probabilistic Encryption
  • The Knowledge Complexity of Interactive Proof Systems
  • How to Generate Cryptographically Strong Sequences of Pseudorandom 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 Languages in NP Have Zero-Knowledge Proof Systems
  • How to Play Any Mental Game: A Completeness Theorem for Protocols with Honest Majority
  • Non-Interactive Zero-Knowledge (NIZK) Proof Systems
  • Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation
  • Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions


• PART III PERSPECTIVES
  • On the Foundations of Cryptography
  • On the Impact of Cryptography on Complexity Theory
  • On Some Noncryptographic Works of Goldwasser and Micali
  • Fundamentals of Fully Homomorphic Encryption
  • Interactive Proofs for Lattice Problems
  • Following a Tangent of Proofs
  • A Tutorial on Concurrent Zero-Knowledge
  • Doubly Efficient Interactive Proofs
  • Computational Entropy
  • A Survey of Leakage-Resilient Cryptography


• Editor and Author Biographies

Sujets

• Computers
• Informatique
• Cryptography
• Security
• Encryption

Informations

• Publié par: Association for Computing Machinery and Morgan & Claypool Publishers
• Date de parution: 13 septembre 2019
• Nombre de lectures: 0
• EAN13: 9781450372688
• Langue: English

Extrait

Providing Sound Foundations for Cryptography

ACM Books

Ebitor in Chief M. Tamer Özsu,University of Waterloo

ACM Books is a new series of high-quality ooks for the computer science community, pulisheb y ACM in collaoration with Morgan & Claypool Pulishers. ACM Books pulications are wibely bistriuteb in oth print anb bigital formats through ooksellers anb to liraries (anb lirary consortia) anb inbivibual ACM memers via the ACM Digital Lirary platform.

Provibing Sounb Founbations for Cryptography: On the work of Shafi Golbwasser anb Silvio Micali Obeb Golbreich,Weizmann Institute of Science 2019

Concurrency: The Works of Leslie Lamport Dahlia Malkhi,VMware ResearchanbCalibra 2019

The Essentials of Mobern Software Engineering: Free the Practices from the Methob Prisons! Ivar Jacoson,Ivar Jacobson International Harolb “Bub” Lawson,Lawson Konsult AB (deceased) Pan-Wei Ng,DBS Singapore Paul E. McMahon,PEM Systems Michael Goebicke,Universität Duisburg–Essen 2019

Data Cleaning Iha F. Ilyas,University of Waterloo Xu Chu,Georgia Institute of Technology 2019

Conversational UX Design: A Practitioner’s Guibe to the Natural Conversation Framework Roert J. Moore,IBM Research–Almaden Raphael Arar,IBM Research–Almaden 2019

Heterogeneous Computing: Harbware anb Software Perspectives Mohameb Zahran,New York University 2019

Harbness of Approximation Between P anb NP Aviab Ruinstein,Stanford University 2019

The Hanbook of Multimobal-Multisensor Interfaces, Volume 3: Language Processing, Software, Commercialization, anb Emerging Directions Ebitors: Sharon Oviatt,Monash University Björn Schuller,Imperial College London and University of Augsburg Philip R. Cohen,Monash University Daniel Sonntag,German Research Center for Artificial Intelligence (DFKI) Gerasimos Potamianos,University of Thessaly

Antonio Krüger,Saarland University and German Research Center for Artificial Intelligence(DFKI) 2019

Making Dataases Work: The Pragmatic Wisbom of Michael Stoneraker Ebitor: Michael L. Brobie,Massachusetts Institute of Technology 2018

The Hanbook of Multimobal-Multisensor Interfaces, Volume 2: Signal Processing, Architectures, anb Detection of Emotion anb Cognition Ebitors: Sharon Oviatt,Monash University Björn Schuller,University of Augsburg and Imperial College London Philip R. Cohen,Monash University Daniel Sonntag,German Research Center for Artificial Intelligence (DFKI) Gerasimos Potamianos,University of Thessaly Antonio Krüger,Saarland University and German Research Center for Artificial Intelligence(DFKI) 2018

Declarative Logic Programming: Theory, Systems, anb Applications Ebitors: Michael Kifer,Stony Brook University Yanhong Annie Liu,Stony Brook University 2018

The Sparse Fourier Transform: Theory anb Practice Haitham Hassanieh,University of Illinois at Urbana-Champaign 2018

The Continuing Arms Race: Cobe-Reuse Attacks anb Defenses Ebitors: Per Larsen,Immunant, Inc. Ahmab-Reza Sabeghi,Technische Universität Darmstadt 2018

Frontiers of Multimebia Research Ebitor: Shih-Fu Chang,Columbia University 2018

Shareb-Memory Parallelism Can Be Simple, Fast, anb Scalale Julian Shun,University of California, Berkeley 2017

Computational Prebiction of Protein Complexes from Protein Interaction Networks Sriganesh Srihari,The University of Queensland Institute for Molecular Bioscience Chern Han Yong,Duke-National University of Singapore Medical School Limsoon Wong,National University of Singapore 2017

The Hanbook of Multimobal-Multisensor Interfaces, Volume 1: Founbations, User Mobeling, anb Common Mobality Cominations Ebitors: Sharon Oviatt,Incaa Designs Björn Schuller,University of Passau and Imperial College London Philip R. Cohen,Voicebox Technologies Daniel Sonntag,German Research Center for Artificial Intelligence (DFKI) Gerasimos Potamianos,University of Thessaly Antonio Krüger,Saarland University and German Research Center for Artificial Intelligence (DFKI) 2017

Communities of Computing: Computer Science anb Society in the ACM Thomas J. Misa, Ebitor,University of Minnesota 2017

Text Data Management anb Analysis: A Practical Introbuction to Information Retrieval anb Text Mining ChengXiang Zhai,University of Illinois at Urbana–Champaign Sean Massung,University of Illinois at Urbana–Champaign 2016

An Architecture for Fast anb General Data Processing on Large Clusters Matei Zaharia,Stanford University 2016

Reactive Internet Programming: State Chart XML in Action Franck Barier,University of Pau, France 2016

Verifieb Functional Programming in Agba Aaron Stump,The University of Iowa 2016

The VR Book: Human-Centereb Design for Virtual Reality Jason Jeralb,NextGen Interactions 2016

Aba’s Legacy: Cultures of Computing from the Victorian to the Digital Age Roin Hammerman,Stevens Institute of Technology Anbrew L. Russell,Stevens Institute of Technology 2016

Ebmunb Berkeley anb the Social Responsiility of Computer Professionals Bernabette Longo,New Jersey Institute of Technology 2015

Canbibate Multilinear Maps Sanjam Garg,University of California, Berkeley 2015

Smarter Than Their Machines: Oral Histories of Pioneers in Interactive Computing John Cullinane,Northeastern University; Mossavar-Rahmani Center for Business and Government, John F. Kennedy School of Government, Harvard University 2015

A Framework for Scientific Discovery through Vibeo Games Seth Cooper,University of Washington 2014

Trust Extension as a Mechanism for Secure Cobe Execution on Commobity Computers Bryan Jeffrey Parno,Microsoft Research 2014

Emracing Interference in Wireless Systems Shyamnath Gollakota,University of Washington 2014

Providing Sound Foundations for Cryptography

On the work of Shafi Goldwasser and Silvio Micali

Ôded Goldreich, ediTor Weizmann Institute of Science

ACM Books #30

Copyright © 2019 by Association for Computing Machinery

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews—without the prior permission of the publisher.

Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks. In all instances in which the Association for Computing Machinery is aware of a claim, the product names appear in initial capital or all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding trademarks and registration.

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

Oded Goldreich, editor

books.acm.org http://books.acm.org

ISBN: 978-1-4503-7266-4 ISBN: 978-1-4503-7267-1 ISBN: 978-1-4503-7268-8 ISBN: 978-1-4503-7269-5

hardcover paperback EPUB eBook

Series ISSN: 2374-6769 print

DOIs:

10.1145/3335741 Book

2374-6777 electronic

10.1145/3335741.3335742 Preface

10.1145/3335741.3335743 Chapter 1

10.1145/3335741.3335744 Chapter 2

10.1145/3335741.3335745 Chapter 3

10.1145/3335741.3335746 Chapter 4

10.1145/3335741.3335747 Chapter 5

10.1145/3335741.3335748 Chapter 6

10.1145/3335741.3335749 Chapter 7

10.1145/3335741.3335750 Chapter 8

10.1145/3335741.3335751 Chapter 9

10.1145/3335741.3335752 Chapter 10

10.1145/3335741.3335753 Chapter 11

10.1145/3335741.3335754 Chapter 12

10.1145/3335741.3335755 Chapter 13

10.1145/3335741.3335756 Chapter 14

10.1145/3335741.3335757 Chapter 15

10.1145/3335741.3335758 Chapter 16

10.1145/3335741.3335759 Chapter 17

10.1145/3335741.3335760 Chapter 18

10.1145/3335741.3335761 Chapter 19

10.1145/3335741.3335762 Chapter 20

10.1145/3335741.3335763 Chapter 21

10.1145/3335741.3335764 Chapter 22

10.1145/3335741.3335765 Chapter 23

10.1145/3335741.3335766 Chapter 24

10.1145/3335741.3335767 Chapter 25

10.1145/3335741.3335768 Chapter 26

10.1145/3335741.3335769 Biographies

A publication in the ACM Books series, #30 Editor in Chief: M. Tamer Özsu,University of Waterloo

This book was typeset in Arnhem Pro 10/14 and Flama using ZzT X. E

First Edition

10 9 8 7 6 5 4 3 2 1

Contents

PART I

Chapter 1

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 6

PART II

Preface

Acknowledgments

Photo and Text Credits

BIOGRAPHIES, INTERVIEWS, AND AWARD LECTURES

A Story Behind Every Problem: A Brief Biog raphy of Shafi Goldwasser 1.1 Beaches and Books: An International Childhood 1.2 The Mind-Blowing World of Computer Science 1.3 Blue Skies and Green Hills 1.4 Theory and the Cryptography Revolution 1.5 A Mecca for Cryptography 1.6 The Traveling Professor 1.7 New Perspectives

One Obsession at a Time: A Brief Biography of Silvio Micali 2.1 A Childhood Among the Ruins 2.2 Rome: The World as a Museum 2.3 Preparing for a Nobel Prize . . . Or Not 2.4 California, Here I Come! 2.5 The “Perfect Storm” of Cryptography 2.6 I Have a Ph.D., Now What? 2.7 Professor Micali of MIT 2.8 Kudos and Companies 2.9 The Road Ahead

An Interview with Shafi Goldwasser

An Interview with Silvio Micali

The Cryptographic Lens: Shafi Goldwasser’s Turing Lecture 5.1 Historical and Social Perspective 5.2 A List of Wonders 5.3 Two Axioms 5.4 Impact on Theory of Computation at Large 5.5 Following One Thread 5.6 The Future 5.7 Concluding Remarks

Proofs, According to Silvio: Silvio Micali ’s Turing Lecture 6.1 Thanks 6.2 Science 6.3 Advice

ORIGINAL PAPERS