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

Format:

Book

Author/Creator:

Goldreich, Oded, editor.

Series:

ACM books - Collection 2 ; #30.

ACM books, 2374-6777 ; #30

Language:

English

Subjects (All):

Hardware & Software (Computer Science).

Genre:

Electronic books.

Physical Description:

1 online resource (xxxv, 800 pages) LuaTEX

Edition:

First Edition

Place of Publication:

[New York, NY, USA] : Association for Computing Machinery; [2019].

System Details:

Mode of access: World Wide Web

System requirements: Adobe Acrobat Reader

Contents:

PART I BIOGRAPHIES, INTERVIEWS, AND AWARD LECTURES

1 A Story Behind Every Problem: A Brief Biography 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

2 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

3 An Interview with Shafi Goldwasser

4 An Interview with Silvio Micali

5 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

6 Proofs, According to Silvio: Silvio Micali's Turing Lecture

6.1 Thanks

6.2 Science

6.3 Advice

PART II ORIGINAL PAPERS

7 Probabilistic Encryption 1 Introduction

2 The Security of a Public Key Cryptosystem

2.1 What is a Public Key Cryptosystem?

2.2 The RSA Scheme and the Rabin Scheme

2.3 Objections to Cryptosystems based on Trapdoor Functions

2.4 Discussion of Objection 1

2.5 Discussion of Objection 2

2.6 Attempts to Send a Single Bit Securely in Public Key Cryptosystems based on TrapDoor Functions

3 Deciding Quadratic Residuosity Is Hard on the Average

3.1 Background and Notation

3.2 A Difficult Problem in Number Theory

3.4 A Number Theoretic Result

4 How to Send Messages in a Public Key Cryptosystem in a Provably Secure Way

4.1 The Security of Partial Information

4.2 An Adversary Cannot Decode

5 Mental Poker

5.1 Background For Coin Flipping

5.2 Useful Results

5.3 The Protocol

5.3.1 The Algorithm

5.3.2 Proof Of Correctness

5.3.3 Implementation Details

6 Remarks and Further Improvements

8 The Knowledge Complexity of Interactive Proof Systems 1 Introduction

2 Interactive Proof Systems

2.1 Interactive Turing Machines and Interactive Pairs of Turing Machines

2.2 Interactive Proof-Systems

2.3 Interactive Complexity Classes

3 Knowledge Complexity

3.1 Degrees of Distinguishability for Probability Distributions

3.2 The Knowledge Computable from a Communication

3.3 The Knowledge Complexity of a Language

4 Languages in KC(0)

4.1 The Quadratic Residuosity Problem

4.2 A "0" Knowledge Interactive Proof System for L

5 A Parenthetical Section

6 Applications to Cryptographic Protocols

6.1 A Modification of the Oblivious Transfer That Is Provably Equivalent to Factoring

7 Open Problems

9 How to Generate Cryptographically Strong Sequences of Pseudorandom Bits

1 Introduction

1.1 Randomness and Complexity Theory

1.2 Our Generator

1.3 Related Results and Applications

2 The Generator Model

3 The Discrete Logarithm Problem

3.1 Actual knowledge about the DLP

3.2 The DLP and the Principal Square Root Problem

4 A Concrete Implementation of the General Model

4.1 First Implementation

4.2 Second Implementation

10 How to Construct Random Functions 1 Introduction

1.1 Poly-Random Collections

1.2 Comparison with One-way Functions

1.3 Comparison with CSPRB Generators

1.4 Conventions

2 CSPRB Generators

2.1 The Notion of a CSPRB Generator

2.2 Polynomial-Time Statistical Tests for Strings

2.3 Implementations of CSPRB Generators

2.4 CSPRB Generators with Direct Access

3 Constructing Poly-Random Collections

3.1 Polynomial Time Statistical Tests for Functions

3.2 The Construction of F

3.3 The Poly-Randomness of F

3.4 Generalized Poly-Random Collections

3.5 A Universal StatisticalTest

4 Prediction Problems and Poly-Random Collections

5 Applications

5.1 Storageless Distribution of Secret Identification Numbers

5.2 Message Authentication and Time-Stamping

5.3 An Identify Friend or Foe System

5.4 Dynamic Hashing

5.5 Speeding-up CSPRB Generation

6 Concluding Remarks

11 Digita1 Signature Scheme Secure Against Adaptive Chosen-Message Attacks

I Introduction

II Fundamental Notions

II.A What Is a Digital Signature Scheme?

II.A.1 Trap-Door Signatures

II.B Kinds of Attacks

II.C What Does It Mean to "Break" a Signature Scheme?

III The Paradoxical Problem of Proving Signature Schemes Secure

III.A The Paradox

III.B Breaking the Paradox

IV Previous Signature Schemes

V Description of the Scheme

V.A How to Generate Keys

V.B How to Sign

V.C How to Verify a Signature

V.D Efficiency of the Proposed Signature Scheme

VI Proof of Security

VI.A An Implementation of Our Scheme as Intractable as Factoring

VII Conclusions and Open Problems

VIII References

12 Proofs that Yield Nothing but Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems

1.1 What Is an Interactive Proof

1.2 What Is a Zero-Knowledge Proof

1.3 Previous Results Concerning Interactive Proof Systems

1.4 Organization of the Paper

2 Proofs of Graph Isomorphism and Graph Non-Isomorphism

2.1 An Interactive Proof of Graph Non-Isomorphism

2.2 A Zero-Knowledge Proof for Graph Isomorphism

2.3 Zero-Knowledge Proof of Graph Non-Isomorphism

3 All Languages in NP Have Zero-Knowledge Proof Systems

3.1 A Zero-Knowledge Proof for Graph 3-Colourability

3.2 Zero-Knowledge Proofs for all NP

3.3 Everything Efficiently Provable Can Be Proven in Zero-Knowledge

3.4 Related Results

4 A Methodology of Cryptographic Protocol Design

13 How to Play Any Mental Game: A Completeness Theorem for Protocols with Honest Majority

2 Preliminary Definitions

2.1 Notation and Conventions for Probabilistic Algorithms

2.2 Game Networks and Distributed Algorithms

2.3 Adversaries

2.4 Indistinguishability of Random Variables

3 Tm-games With Passive Adversaries

4 Hints on How to Play Tm-games With Passive Adversaries

4.1 A New and General Oblivious Transfer Protocol

4.2 Strengthening Yao's Combined Oblivious Transfer

4.3 The Tm-game Solver for Passive Adversaries

5 Malicious Adversaries

6 General Games

6.1 Games

6.2 Playable Games

6.3 A General Result

6.4 A Completeness Theorem for Fault-Tolerant Computation

7 Recent Developments

8 Acknowledgements

9 References

14 Non-Interactive Zero-Knowledge (NIZK) Proof Systems

1.1 Our Model Versus the Old One

1.2 The Robustness of Our Result

1.3 Applications of our Result

1.4 What's Coming

2 Preliminaries

2.1 Notations and Conventions

2.2 Number Theory

2.3 A Complexity Assumption

3 Single-Theorem Non-Interactive Zero-Knowledge Proofs

3.1 The Proof-System (P,V)

3.2 A Rough Idea of why (P,V) is a Single-Theorem Non-Interactive ZKPS

4 Non-Interactive ZKPS

4.1 The Proof System (P,V)

4.2 The Zero-Knowledgeness of (P,V)

4.2.1 The Simulation of Stage 1

5 A No-Longer Long-Standing Open Problem

6 Improvements

7 References

15 Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation

Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation (Extended Abstract)

16 Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions

1.1 New Model

1.2 Results

1.2.1 Perfect Zero Knowledge Multi-Prover Interactive Proofs

1.3 Language Recognition Power of New Model

1.4 Open Problem

2 Definitions

3 Statement of Our Results

3 Key Ideas

4 Proof of Theorem 1: How to Commit Bits

5 Proof of Theorem 4: IPk = IP2 for all k > 2

6 Proof of Theorem 5: Completeness

7 Proof of Theorem 2: Outline

A Structure of the Transformed Protocol

A.1 The Commital Phase

A.2 The Oblivious Transfer Phase

Introduction to Oblivious Transfer

A Variant of Oblivious Transfer in the 2-Prover Model

Branching Programs

The Oblivious Transfer Protocol

Properties of the Oblivious Transfer Protocol

Ideal versus Nonideal Oblivious Transfer Bits

Formalizing Proof Systems with Oblivious Transfer Channels

Modeling Ideal and Nonideal Sources in Our Formalism

Modeling an Ideal Oblivious Transfer Mechanism

A Practical Equivalence Between Tn, k and T ideal

Transfer Mechanisms That Are Intermediate Between The Ideal and Nonideal Models

Analysis of Cheating Probabilities for Different Transfer Mechanisms

Restricted Versions of Oblivious Transfer Mechanisms

Analysis of Cheating with Respect to Restricted Transfer Mechanisms

A.3 Implementing Zero-Knowledge with Circuits

A Normal Form for Two-Prover IPS's

A.3.1 Strong Encryption Using 2-Universal Hash Functions

A.3.2 Use of Oblivious Circuit Evaluation

A.3.3 Outline of the Zero-Knowledge Protocol

Is This Protocol a Proof System?

Is This Protocol Zero-Knowledge?

PART III PERSPECTIVES

17 On the Foundations of Cryptography 17.1 Introduction and Preliminaries

17.1.1 Introduction

17.1.2 Preliminaries

Part I Basic Tools

17.3 Computational Difficulty and One-Way Functions

17.3.1 One-Way Functions

17.3.2 Hard-Core Predicates

17.4 Pseudorandomness

17.4.1 Computational Indistinguishability

17.4.2 Pseudorandom Generators

17.4.3 Pseudorandom Functions

17.5 Zero-Knowledge

17.5.1 The Simulation Paradigm

17.5.2 The Actual Definition

17.5.3 Zero-Knowledge Proofs for All NP-Assertions and Their Applications

17.5.4 Variants and Issues

17.5.4.1 Computational Soundness

17.5.4.2 Definitional Variations

17.5.4.3 Related Notions: POK, NIZK, and WI

17.5.4.4 Two Basic Problems: Composition and Black-Box Simulation

Part II Basic Applications

17.7 Encryption Schemes

17.7.1 Definitions

17.7.2 Constructions

17.7.3 Beyond Eavesdropping Security

17.8 Signature and Message Authentication Schemes

17.8.1 Definitions

17.8.2 Constructions

17.8.3 Public-Key Infrastructure

17.9 General Cryptographic Protocols

17.9.1 The Definitional Approach and Some Models

17.9.1.1 Some Parameters Used in Defining Security Models

17.9.1.2 Example: Multi-Party Protocols with Honest Majority

17.9.1.3 Another Example: Two-Party Protocols Allowing Abort

17.9.2 Some Known Results

17.9.3 Construction Paradigms

17.9.3.1 Passively Secure Computation with Shares

17.9.3.2 Compilation of Passively Secure Protocols into Actively Secure Ones

17.9.4 Concurrent Execution of Protocols

17.9.5 Concluding Remarks

References

18 On the Impact of Cryptography on Complexity Theory

18.1 The Story

18.1.1 Pseudorandomness

18.1.2 Probabilistic Proof Systems

18.1.3 Finer Study of Reductions

18.3 Probabilistic Proof Systems: A Bird's-Eye View

18.3.1 Interactive Proof Systems

18.3.2 Zero-Knowledge Proof Systems

18.3.3 Probabilistically Checkable Proof Systems

18.3.4 Doubly Efficient Interactive Proof Systems

Acknowledgments

References

19 On Some Noncryptographic Works of Goldwasser and Micali 19.1 An -time Algorithm for Finding Maximum Matching in General Graphs

19.2 Certifying Almost All Primes Using Elliptic Curves

19.3 Private Coins versus Public Coins in Interactive Proof Systems

19.4 An Optimal Randomized Protocol for Synchronous Byzantine Agreement

19.5 PCPs and the Hardness of Approximating Cliques

19.6 Computationally Sound Proofs

19.7 Property Testing and its Connection to Learning and Approximation

19.8 Pseudo-Deterministic Algorithms

20 Fundamentals of Fully Homomorphic Encryption

20.1 Homomorphic Encryption: Good, Bad, or Ugly?

20.2 Definition and Basic Properties

20.3 Bootstrapping and Circular Security

20.4 Constructing FHE

20.4.1 Learning with Errors: A Primer

20.4.2 A Homomorphic Encryption Scheme Based on LWE

20.4.3 Efficiency and Implementations

20.5 Beyond Vanilla FHE

21 Interactive Proofs for Lattice Problems

21.1 Introduction

21.2 Background

21.2.1 Worst-Case Lattice Problems

21.2.2 Average-Case Lattice Problems and Smoothing Parameter

21.3 The GG Proof Systems

21.4 Zero-Knowledge with Efficient Provers

21.5 Other Lattice Problems

21.6 LWE and the GapSVP to BDD Reduction

21.7 Conclusion

22 Following a Tangent of Proofs

22.1 Introduction and Notation

22.2 The Beginning, IP, ZK, and AM

22.3 Multi-Prover Interactive Proofs

22.4 The True Power of Interaction

22.5 Inapproximability Enters the Picture

22.6 PCP-Theorem and Label-Cover

22.7 The Long Code and the Standard Written Proof

22.8 Two Inner Tests

22.8.1 The Test Underlying Max-3Lin-2 Hardness

22.8.2 A Promise Problem Version of SAT

22.9 Conclusions

23 Tutorial on Concurrent Zero-Knowledge

23.1 Introduction

23.2 Preliminaries

23.2.1 Black-Box Concurrent Zero-Knowledge

23.2.2 Other Primitives

23.2.3 Known Protocols

23.3 Black-Box Concurrent Zero-Knowledge Arguments of Knowledge

23.3.1 The Protocol

23.3.2 The Simulator Algorithm

23.3.3 A Formal Description of Sim

23.4 Acknowledgements

24 Doubly Efficient Interactive Proofs

24.1 Introduction

24.1.1 DEIPs for Bounded-Depth Computations

24.1.2 Constant-Round DEIPs for Bounded-Space Computations

24.1.3 Applications and Further Related Work

24.1.4 Open Questions

24.2 Preliminaries

24.2.1 Interactive Proofs

24.2.2 Polynomials and Low-Degree Extensions

24.2.3 The Sum-Check Protocol

24.3 DEIPs for Bounded-Depth Computations

24.3.1 Setup and Notation

24.3.2 The "Bare-Bones" Protocol

24.3.3 Analysis of the Bare-Bones Protocol

24.4 Constant-Round DEIPs for Bounded-Space Computation

24.4.1 A Warm-Up: Batching the Verification of UP Statements

24.4.2 Batching Unambiguous Interactive Proofs

24.4.2.1 Unambiguous and Probabilistically Checkable Interactive Proofs

24.4.2.2 Batching Using Unambiguous PCIPs

25 Computational Entropy

25.1 Introduction

25.2 Basic Information-Theoretic Notions

25.3 Basic Computational Notions

25.4 Pseudoentropy

25.5 One-Way Permutations to Pseudorandom Generators

25.6 One-Way Functions to Pseudorandom Generators

25.7 One-Way Functions to Statistically Hiding Commitments

26 A Survey of Leakage- Resilient Cryptograph

26.1 Introduction

26.1.1 Early Works

26.1.2 Formalisms of Leakage-Resilient Cryptography

26.1.3 Roadmap

26.2 Memory Leakage

26.2.1 The Models for Memory Leakage

26.2.2 Bounded Memory Leakage

26.2.3 Auxiliary Input Memory Leakage

26.2.4 Bounded Retrieval Model

26.2.5 Continual Memory Leakage

26.2.6 Interactive Protocols

26.3 Leakage from Storage

26.4 Leakage from Computation

26.4.1 The Only Computation Leaks (OCL) Model

26.4.2 Specific Schemes

26.4.2.1 Pseudorandom Generators of Micali and Reyzin [2004]

26.4.2.2 The Power of Only-Computation-Leaks: The Stream Cipher of Dziembowski and Pietrzak [2008]

26.4.2.3 More Leakage-Resilient Stream Ciphers

26.4.2.4 Leakage-Resilient Key Evolution

26.4.2.5 Leakage-Resilient Block Ciphers, Encryption, and Authentication

26.4.2.6 Leakage-Resilient Public-Key Objects

26.4.3 General Compilers

26.4.3.1 The Compiler of Ishai et al. [2003]

26.4.3.2 Improved Compilers for Wire Probing Leakage

26.4.3.3 Compilers for Leakage of Limited Complexity

26.4.3.4 Compilers for OCL leakage

26.4.3.5 Compilers for Noisy and Noisy OCL Leakage

26.4.4 Heuristic Security Evaluation of Leakage-Resilient Constructions

26.5 Acknowledgements

Editor and Author Biographies

Other Format:

Print version:

ISBN:

3335741

9781450372695

9781450372688

Access Restriction:

Restricted for use by site license.