Efficient Secure Two-Party Protocols: Techniques and Constructions (Information Security and Cryptography)

✍ Scribed by Carmit Hazay, Yehuda Lindell

• Publisher: Springer
• Year: 2010
• Tongue: English
• Leaves: 271
• Category: Library

✦ Synopsis

In the setting of multiparty computation, sets of two or more parties with p- vate inputs wish to jointly compute some (predetermined) function of their inputs. The computation should be such that the outputs received by the parties are correctly distributed, and furthermore, that the privacy of each party’s input is preserved as much as possible, even in the presence of - versarial behavior. This encompasses any distributed computing task and includes computations as simple as coin-tossing and broadcast, and as c- plex as electronic voting, electronic auctions, electronic cash schemes and anonymous transactions. The feasibility (and infeasibility) of multiparty c- putation has been extensively studied, resulting in a rather comprehensive understanding of what can and cannot be securely computed, and under what assumptions. The theory of cryptography in general, and secure multiparty computation in particular, is rich and elegant. Indeed, the mere fact that it is possible to actually achieve the aforementioned task is both surprising and intriguing.

✦ Table of Contents

Cover
Preface
Contents
Part I Introduction and Definitions
Chapter 1 Introduction
1.1 Secure Multiparty Computation – Background
1.2 The GMW Protocol for Secure Computation
1.3 A Roadmap to the Book
1.3.1 Part I – Introduction and Defi nitions
1.3.2 Part II – General Constructions
1.3.3 Part III – Specific Constructions
Chapter 2 Definitions
2.1 Preliminaries
2.2 Security in the Presence of Semi-honest Adversaries
2.3 Security in the Presence of Malicious Adversaries
2.3.1 The Definition
2.3.2 Extension to Reactive Functionalities
2.3.3 Malicious Versus Semi-honest Adversaries
2.4 Security in the Presence of Covert Adversaries
2.4.1 Motivation
2.4.2 The Actual Definition
2.4.3 Cheating and Aborting
2.4.4 Relations Between Security Models
2.5 Restricted Versus General Functionalities
2.5.1 Deterministic Functionalities
2.5.2 Single-Output Functionalities
2.5.3 Non-reactive Functionalities
2.6 Non-simulation-Based Definitions
2.6.1 Privacy Only
2.6.2 One-Sided Simulatability
2.7 Sequential Composition – Simulation-BasedDefinitions
Part II General Constructions
Chapter 3 Semi-honest Adversaries
3.1 An Overview of the Protocol
3.2 Tools
3.2.1 "
Special" Private-Key Encryption
3.2.2 Oblivious
Transfer
3.3 The Garbled-Circuit Construction
3.4 Yao’s Two-Party Protocol
3.5 Efficiency of the Protocol
Chapter 4 Malicious Adversaries
4.1 An Overview of the Protocol
4.1.1 High-Level Protocol Description
4.1.2 Checks for Correctness and Consistency
4.2 The Protocol
4.3 Proof of Security
4.3.1 Security Against a Malicious P1
4.3.2 Security Against a Malicious P2
4.4 Efficient Implementation of the Different Primitives
4.5 Efficiency of the Protocol
4.6 Suggestions for Further Reading
Chapter 5 Covert Adversaries
5.1 Oblivious Transfer
5.1.1 The Basic Protocol
5.1.2 Extensions
5.2 Secure Two-Party Computation
5.2.1 Overview of the Protocol
5.2.2 The Protocol for Two-Party Computation
5.2.3 Non-halting Detection Accuracy
5.3 Efficiency of the Protocol
Part III Specific Constructions
Chapter 6 Sigma Protocols and Efficient Zero-Knowledge1
6.1 An Example
6.2 Definitions and Properties
6.3 Proofs of Knowledge
6.4 Proving Compound Statements
6.5 Zero-Knowledge from Σ-Protocols
6.5.1 The Basic Zero-Knowledge Construction
6.5.2 Zero-
Knowledge Proofs of Knowledge
6.5.3 The ZKPOK Ideal Functionality
6.6 Efficient Commitment Schemes from Σ-Protocols
6.7 Summary
Chapter 7 Oblivious Transfer and Applications
7.1 Notational Conventions for Protocols
7.2 Oblivious Transfer – Privacy Only
7.2.1 A Protocol Based on the DDH Assumption
7.2.2 A Protocol from Homomorphic Encryption
7.3 Oblivious Transfer – One-Sided Simulation
7.4 Oblivious Transfer – Full Simulation
7.4.1 1-out-of-2 Oblivious Transfer
7.4.2 Batch Oblivious Transfer
7.5 Another Oblivious Transfer – Full Simulation
7.6 Secure Pseudorandom Function Evaluation
7.6.1 Pseudorandom Function – Privacy Only
7.6.2 Pseudorandom Function – Full Simulation
7.6.3 Covert
and One-Sided Simulation
7.6.4 Batch Pseudorandom Function Evaluation
Chapter 8 The kth-Ranked Element
8.1 Background
8.1.1 A Protocol for Finding the Median
8.1.2 Reducing the kth-Ranked Element to the Median
8.2 Computing the Median – Semi-honest
8.3 Computing the Median – Malicious
8.3.1 The Reactive Greater-Than Functionality
8.3.2 The Protocol
Chapter 9 Search Problems
9.1 Background
9.2 Secure Database Search
9.2.1 Securely Realizing Basic Database Search
9.2.2 Securely Realizing Full Database Search
9.3 Secure Document Search
9.4 Implementing Functionality FCPRP with Smartcards
9.4.1 Standard Smartcard Functionality and Security
9.4.2 Implementing FCPRP with Smartcards
9.5 Secure Text Search (Pattern Matching)
9.5.1 Indexed Implementation for Naor-Reingold
9.5.2 The Protocol for Secure Text Search
References
Index