Efficient Secure Two-Party Protocols

by Hazay, Carmit; Lindell, Yehuda

• ISBN13: 9783642143021
• ISBN10: 3642143024
• Format: Hardcover
• Copyright: 2010-10-29
• Publisher: Springer-Nature New York Inc

Summary

The authors present a comprehensive study of efficient protocols and techniques for secure two-party computation. They study both general constructions that can be used to securely compute any functionality, and protocols for specific problems of interest. The aim of the book is to focus on techniques for both constructing protocols and proving them secure. In addition, the authors study the different definitional paradigms used and compare the efficiency of protocols achieved under these different definitions. This book is essential for practitioners and researchers in the field of secure protocols, particularly those with a focus on efficiency, and for researchers in the area of privacy-preserving data mining.

Table of Contents

Introduction and Definitions
Introduction	p. 3
Secure Multiparty Computation - Background	p. 3
The GMW Protocol for Secure Computation	p. 11
A Roadmap to the Book	p. 13
Part I - Introduction and Definitions	p. 13
Part II - General Constructions	p. 15
Part III - Specific Constructions	p. 17
Definitions	p. 19
Preliminaries	p. 19
Security in the Presence of Semi-honest Adversaries	p. 20
Security in the Presence of Malicious Adversaries	p. 23
The Definition	p. 24
Extension to Reactive Functionalities	p. 25
Malicious Versus Semi-honest Adversaries	p. 26
Security in the Presence of Covert Adversaries	p. 30
Motivation	p. 30
The Actual Definition	p. 33
Cheating and Aborting	p. 35
Relations Between Security Models	p. 36
Restricted Versus General Functionalities	p. 38
Deterministic Functionalities	p. 39
Single-Output Functionalities	p. 39
Non-reactive Functionalities	p. 41
Non-simulation-Based Definitions	p. 42
Privacy Only	p. 42
One-Sided Simulatability	p. 45
Sequential Composition - Simulation-Based Definitions	p. 46
General Constructions
Semi-honest Adversaries	p. 53
An Overview of the Protocol	p. 53
Tools	p. 57
"Special" Private-Key Encryption	p. 57
Oblivious Transfer	p. 61
The Garbled-Circuit Construction	p. 63
Yao's Two-Party Protocol	p. 66
Efficiency of the Protocol	p. 78
Malicious Adversaries	p. 81
An Overview of the Protocol	p. 81
High-Level Protocol Description	p. 82
Checks for Correctness and Consistency	p. 84
The Protocol	p. 89
Proof of Security	p. 93
Security Against a Malicious P1	p. 93
Security Against a Malicious P2	p. 99
Efficient Implementation of the Different Primitives	p. 105
Efficiency of the Protocol	p. 106
Suggestions for Further Reading	p. 107
Covert Adversaries	p. 109
Oblivious Transfer	p. 109
The Basic Protocol	p. 111
Extensions	p. 119
Secure Two-Party Computation	p. 121
Overview of the Protocol	p. 122
The Protocol for Two-Party Computation	p. 124
Non-halting Detection Accuracy	p. 141
Efficiency of the Protocol	p. 143
Specific Constructions
Sigma Protocols and Efficient Zero-Knowledge	p. 147
An Example	p. 147
Definitions and Properties	p. 149
Proofs of Knowledge	p. 153
Proving Compound Statements	p. 158
Zero-Knowledge from ¿-Protocols	p. 160
The Basic Zero-Knowledge Construction	p. 161
Zero-Knowledge Proofs of Knowledge	p. 164
The ZKPOK Ideal Functionality	p. 167
Efficient Commitment Schemes from ¿-Protocols	p. 173
Summary	p. 175
Oblivious Transfer and Applications	p. 177
Notational Conventions for Protocols	p. 178
Oblivious Transfer - Privacy Only	p. 178
A Protocol Based on the DDH Assumption	p. 178
A Protocol from Homomorphic Encryption	p. 182
Oblivious Transfer - One-Sided Simulation	p. 185
Oblivious Transfer - Full Simulation	p. 188
1-out-of-2 Oblivious Transfer	p. 188
Batch Oblivious Transfer	p. 196
Another Oblivious Transfer - Full Simulation	p. 201
Secure Pseudorandom Function Evaluation	p. 202
Pseudorandom Function - Privacy Only	p. 203
Pseudorandom Function - Full Simulation	p. 209
Covert and One-Sided Simulation	p. 211
Batch Pseudorandom Function Evaluation	p. 212
The kth-Ranked Element	p. 213
Background	p. 213
A Protocol for Finding the Median	p. 214
Reducing the kth-Ranked Element to the Median	p. 216
Computing the Median - Semi-honest	p. 218
Computing the Median - Malicious	p. 221
The Reactive Greater-Than Functionality	p. 221
The Protocol	p. 223
Search Problems	p. 227
Background	p. 228
Secure Database Search	p. 229
Securely Realizing Basic Database Search	p. 231
Securely Realizing Pull Database Search	p. 236
Covert and One-Sided Simulation	p. 237
Secure Document Search	p. 238
Implementing Functionality FCPRP with Smartcards	p. 242
Standard Smartcard Functionality and Security	p. 243
Implementing FCPRP with Smartcards	p. 246
Secure Text Search (Pattern Matching)	p. 248
Indexed Implementation for Naor-Reingold	p. 249
The Protocol for Secure Text Search	p. 252
References	p. 255
Index	p. 261
Table of Contents provided by Ingram. All Rights Reserved.