Efficient Secure Two-Party Protocols

by ;
  • ISBN13:


  • ISBN10:


  • Format: Hardcover
  • Copyright: 2010-10-29
  • Publisher: Springer-Verlag New York Inc
  • Purchase Benefits
  • Free Shipping On Orders Over $35!
    Your order must be $35 or more to qualify for free economy shipping. Bulk sales, PO's, Marketplace items, eBooks and apparel do not qualify for this offer.
  • Get Rewarded for Ordering Your Textbooks! Enroll Now
List Price: $139.99 Save up to $4.20
  • Buy New
    Add to Cart Free Shipping


Supplemental Materials

What is included with this book?

  • The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.


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
Introductionp. 3
Secure Multiparty Computation - Backgroundp. 3
The GMW Protocol for Secure Computationp. 11
A Roadmap to the Bookp. 13
Part I - Introduction and Definitionsp. 13
Part II - General Constructionsp. 15
Part III - Specific Constructionsp. 17
Definitionsp. 19
Preliminariesp. 19
Security in the Presence of Semi-honest Adversariesp. 20
Security in the Presence of Malicious Adversariesp. 23
The Definitionp. 24
Extension to Reactive Functionalitiesp. 25
Malicious Versus Semi-honest Adversariesp. 26
Security in the Presence of Covert Adversariesp. 30
Motivationp. 30
The Actual Definitionp. 33
Cheating and Abortingp. 35
Relations Between Security Modelsp. 36
Restricted Versus General Functionalitiesp. 38
Deterministic Functionalitiesp. 39
Single-Output Functionalitiesp. 39
Non-reactive Functionalitiesp. 41
Non-simulation-Based Definitionsp. 42
Privacy Onlyp. 42
One-Sided Simulatabilityp. 45
Sequential Composition - Simulation-Based Definitionsp. 46
General Constructions
Semi-honest Adversariesp. 53
An Overview of the Protocolp. 53
Toolsp. 57
"Special" Private-Key Encryptionp. 57
Oblivious Transferp. 61
The Garbled-Circuit Constructionp. 63
Yao's Two-Party Protocolp. 66
Efficiency of the Protocolp. 78
Malicious Adversariesp. 81
An Overview of the Protocolp. 81
High-Level Protocol Descriptionp. 82
Checks for Correctness and Consistencyp. 84
The Protocolp. 89
Proof of Securityp. 93
Security Against a Malicious P1p. 93
Security Against a Malicious P2p. 99
Efficient Implementation of the Different Primitivesp. 105
Efficiency of the Protocolp. 106
Suggestions for Further Readingp. 107
Covert Adversariesp. 109
Oblivious Transferp. 109
The Basic Protocolp. 111
Extensionsp. 119
Secure Two-Party Computationp. 121
Overview of the Protocolp. 122
The Protocol for Two-Party Computationp. 124
Non-halting Detection Accuracyp. 141
Efficiency of the Protocolp. 143
Specific Constructions
Sigma Protocols and Efficient Zero-Knowledgep. 147
An Examplep. 147
Definitions and Propertiesp. 149
Proofs of Knowledgep. 153
Proving Compound Statementsp. 158
Zero-Knowledge from -Protocolsp. 160
The Basic Zero-Knowledge Constructionp. 161
Zero-Knowledge Proofs of Knowledgep. 164
The ZKPOK Ideal Functionalityp. 167
Efficient Commitment Schemes from -Protocolsp. 173
Summaryp. 175
Oblivious Transfer and Applicationsp. 177
Notational Conventions for Protocolsp. 178
Oblivious Transfer - Privacy Onlyp. 178
A Protocol Based on the DDH Assumptionp. 178
A Protocol from Homomorphic Encryptionp. 182
Oblivious Transfer - One-Sided Simulationp. 185
Oblivious Transfer - Full Simulationp. 188
1-out-of-2 Oblivious Transferp. 188
Batch Oblivious Transferp. 196
Another Oblivious Transfer - Full Simulationp. 201
Secure Pseudorandom Function Evaluationp. 202
Pseudorandom Function - Privacy Onlyp. 203
Pseudorandom Function - Full Simulationp. 209
Covert and One-Sided Simulationp. 211
Batch Pseudorandom Function Evaluationp. 212
The kth-Ranked Elementp. 213
Backgroundp. 213
A Protocol for Finding the Medianp. 214
Reducing the kth-Ranked Element to the Medianp. 216
Computing the Median - Semi-honestp. 218
Computing the Median - Maliciousp. 221
The Reactive Greater-Than Functionalityp. 221
The Protocolp. 223
Search Problemsp. 227
Backgroundp. 228
Secure Database Searchp. 229
Securely Realizing Basic Database Searchp. 231
Securely Realizing Pull Database Searchp. 236
Covert and One-Sided Simulationp. 237
Secure Document Searchp. 238
Implementing Functionality FCPRP with Smartcardsp. 242
Standard Smartcard Functionality and Securityp. 243
Implementing FCPRP with Smartcardsp. 246
Secure Text Search (Pattern Matching)p. 248
Indexed Implementation for Naor-Reingoldp. 249
The Protocol for Secure Text Searchp. 252
Referencesp. 255
Indexp. 261
Table of Contents provided by Ingram. All Rights Reserved.

Rewards Program

Write a Review