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

- An Overview of the Protocol
- 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

- Oblivious Transfer

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

- Notational Conventions for Protocols
- 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

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

### Categories:

- Home page
- All papers, by:
- .. category
- .. author names
- .. publication date
- .. recently added
- .. recently updated

- Glossary
- About
- Just getting started in MPC?
- Guidelines
- Todo List

Search Papers

Bibliography Categories