Efficient Secure Two-Party Protocols

Efficient Secure Two-Party Protocols

Carmit Hazay, Yehuda Lindell
Monograph, Springer Information Security and Cryptography Series 2010 [bibtex]

Table of Contents:

Part I: Introduction and Definitions

  • Introduction
    • The GMW Protocol for Secure Computation
    • A Roadmap to the Book
  • Definitions
    • Preliminaries
    • Security in the Presence of Semi-honest Adversaries
    • Security in the Presence of Malicious Adversaries
      • The Definition
      • Extension to Reactive Functionalities
      • Malicious Versus Semi-honest Adversaries
    • Security in the Presence of Covert Adversaries
      • Motivation
      • The Actual Definition
      • Cheating and Aborting
      • Relations Between Security Models
    • Restricted Versus General Functionalities
      • Deterministic Functionalities
      • Single-Output Functionalities
      • Non-reactive Functionalities
    • Non-simulation-Based Definitions
      • Privacy Only
      • One-Sided Simulatability
    • Sequential Composition -- Simulation-Based Definitions

Part II: General Constructions

  • Semi-honest Adversaries
    • An Overview of the Protocol
    • Tools
      • "Special" Private-Key Encryption
      • Oblivious Transfer
    • The Garbled-Circuit Construction
    • Efficiency of the Protocol
  • Malicious Adversaries
    • An Overview of the Protocol
      • High-Level Protocol Description
      • Checks for Correctness and Consistency
    • The Protocol
    • Proof of Security
      • Security Against a Malicious ⚠ {$P_1$}
      • Security Against a Malicious ⚠ {$P_2$}
    • Efficient Implementation of the Different Primitives
    • Efficiency of the Protocol
    • Suggestions for Further Reading
  • Covert Adversaries
    • Oblivious Transfer
      • The Basic Protocol
      • Extensions
    • Secure Two-Party Computation
      • Overview of the Protocol
      • The Protocol for Two-Party Computation
      • Non-halting Detection Accuracy
    • Efficiency of the Protocol

Part III: Specific Constructions

  • Sigma Protocols and Efficient Zero-Knowledge
    • An Example
    • Definitions and Properties
    • Proofs of Knowledge
    • Proving Compound Statements
    • Zero-Knowledge from ⚠ {$\Sigma$}-Protocols
      • The Basic Zero-Knowledge Construction
      • Zero-Knowledge Proofs of Knowledge
      • The ZKPOK Ideal Functionality
    • Efficient Commitment Schemes from ⚠ {$\Sigma$}-Protocols
    • Summary
  • Oblivious Transfer and Applications
    • Notational Conventions for Protocols
      • A Protocol Based on the DDH Assumption
      • A Protocol from Homomorphic Encryption
    • Oblivious Transfer -- One-sided Simulation
    • Oblivious Transfer -- Full Simulation
      • 1-out-of-2 Oblivious Transfer
      • Batch Oblivious Transfer
    • Another Oblivious Transfer -- Full Simulation
    • Secure Pseudorandom Function Evaluation
      • Pseudorandom Function -- Privacy Only
      • Pseudorandom Function -- Full Simulation
      • Covert and One-Sided Simulation
      • Batch Pseudorandom Function Evaluation
  • The kth-Ranked Element
    • Background
      • A Protocol for Finding the Median
      • Reducing the kth-Ranked Element to the Median
    • Computing the Median -- Semi-honest
    • Computing the Median -- Malicious
      • The Reactive Greater-Than Functionality
      • The Protocol
  • Search Problems
    • Background
    • Secure Database Search
      • Securely Realizing Basic Database Search
      • Securely Realizing Full Database Search
      • Covert and One-Sided Simulation
    • Secure Document Search
    • Implementing Functionality ⚠ {$\mathcal F_{CPRP}$} with Smartcards
      • Standard Smartcard Functionality and Security
      • Implementing ⚠ {$\mathcal F_{CPRP}$} with Smartcards
    • Secure Text Search (Pattern Matching)
      • Indexed Implementation for Naor-Reingold
      • The Protocol for Secure Text Search

More information, taken from Preface:

Prerequisite knowledge. We assume that the reader is familiar with the basics of theoretical cryptography. Thus, for example, we assume that readers know what commitment schemes and zero-knowledge proofs are, and that they are comfortable with notions like pseudorandomness and computational indistinguishability. In contrast, all the relevant definitions of secure two-party computation are presented here from scratch. Thus, this book can also be used as a first introduction to secure computation.

Other

Comments & Errata from authors

review by Jonathan Katz

Categories:

Reference