Efficient Secure Two-Party Protocols (eBook)

Techniques and Constructions

Carmit Hazay, Yehuda Lindell (Autoren)

eBook Download: PDF

2010
XIII, 263 Seiten
Springer Berlin (Verlag)
9783642143038 (ISBN)

Infos

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.

Inhalt

Cover 1
Preface 6
Contents 10
Part I Introduction and Definitions 13
Chapter 1 Introduction 15
1.1 Secure Multiparty Computation – Background 15
1.2 The GMW Protocol for Secure Computation 23
1.3 A Roadmap to the Book 25
1.3.1 Part I – Introduction and Defi nitions 25
1.3.2 Part II – General Constructions 27
1.3.3 Part III – Specific Constructions 29
Chapter 2 Definitions 31
2.1 Preliminaries 31
2.2 Security in the Presence of Semi-honest Adversaries 32
2.3 Security in the Presence of Malicious Adversaries 35
2.3.1 The Definition 36
2.3.2 Extension to Reactive Functionalities 37
2.3.3 Malicious Versus Semi-honest Adversaries 38
2.4 Security in the Presence of Covert Adversaries 42
2.4.1 Motivation 42
2.4.2 The Actual Definition 45
2.4.3 Cheating and Aborting 47
2.4.4 Relations Between Security Models 48
2.5 Restricted Versus General Functionalities 50
2.5.1 Deterministic Functionalities 51
2.5.2 Single-Output Functionalities 51
2.5.3 Non-reactive Functionalities 53
2.6 Non-simulation-Based Definitions 54
2.6.1 Privacy Only 54
2.6.2 One-Sided Simulatability 57
2.7 Sequential Composition – Simulation-BasedDefinitions 58
Part II General Constructions 62
Chapter 3 Semi-honest Adversaries 64
3.1 An Overview of the Protocol 64
3.2 Tools 68
3.2.1 "Special" Private-Key Encryption 68
3.2.2 ObliviousTransfer 72
3.3 The Garbled-Circuit Construction 74
3.4 Yao’s Two-Party Protocol 77
3.5 Efficiency of the Protocol 89
Chapter 4 Malicious Adversaries 92
4.1 An Overview of the Protocol 92
4.1.1 High-Level Protocol Description 93
4.1.2 Checks for Correctness and Consistency 95
4.2 The Protocol 100
4.3 Proof of Security 104
4.3.1 Security Against a Malicious P1 104
4.3.2 Security Against a Malicious P2 110
4.4 Efficient Implementation of the Different Primitives 116
4.5 Efficiency of the Protocol 117
4.6 Suggestions for Further Reading 118
Chapter 5 Covert Adversaries 120
5.1 Oblivious Transfer 120
5.1.1 The Basic Protocol 122
5.1.2 Extensions 130
5.2 Secure Two-Party Computation 132
5.2.1 Overview of the Protocol 133
5.2.2 The Protocol for Two-Party Computation 135
5.2.3 Non-halting Detection Accuracy 152
5.3 Efficiency of the Protocol 154
Part III Specific Constructions 155
Chapter 6 Sigma Protocols and Efficient Zero-Knowledge1 157
6.1 An Example 157
6.2 Definitions and Properties 159
6.3 Proofs of Knowledge 163
6.4 Proving Compound Statements 168
6.5 Zero-Knowledge from ?-Protocols 170
6.5.1 The Basic Zero-Knowledge Construction 171
6.5.2 Zero-Knowledge Proofs of Knowledge 174
6.5.3 The ZKPOK Ideal Functionality 177
6.6 Efficient Commitment Schemes from ?-Protocols 183
6.7 Summary 185
Chapter 7 Oblivious Transfer and Applications 186
7.1 Notational Conventions for Protocols 187
7.2 Oblivious Transfer – Privacy Only 187
7.2.1 A Protocol Based on the DDH Assumption 187
7.2.2 A Protocol from Homomorphic Encryption 191
7.3 Oblivious Transfer – One-Sided Simulation 194
7.4 Oblivious Transfer – Full Simulation 197
7.4.1 1-out-of-2 Oblivious Transfer 197
7.4.2 Batch Oblivious Transfer 205
7.5 Another Oblivious Transfer – Full Simulation 210
7.6 Secure Pseudorandom Function Evaluation 211
7.6.1 Pseudorandom Function – Privacy Only 212
7.6.2 Pseudorandom Function – Full Simulation 218
7.6.3 Covert and One-Sided Simulation 220
7.6.4 Batch Pseudorandom Function Evaluation 221
Chapter 8 The kth-Ranked Element 222
8.1 Background 222
8.1.1 A Protocol for Finding the Median 223
8.1.2 Reducing the kth-Ranked Element to the Median 225
8.2 Computing the Median – Semi-honest 227
8.3 Computing the Median – Malicious 230
8.3.1 The Reactive Greater-Than Functionality 230
8.3.2 The Protocol 232
Chapter 9 Search Problems 236
9.1 Background 237
9.2 Secure Database Search 238
9.2.1 Securely Realizing Basic Database Search 240
9.2.2 Securely Realizing Full Database Search 245
9.3 Secure Document Search 247
9.4 Implementing Functionality FCPRP with Smartcards 251
9.4.1 Standard Smartcard Functionality and Security 252
9.4.2 Implementing FCPRP with Smartcards 255
9.5 Secure Text Search (Pattern Matching) 257
9.5.1 Indexed Implementation for Naor-Reingold 258
9.5.2 The Protocol for Secure Text Search 261
References 264
Index 269

Produkt-Details

• Erscheint lt. Verlag: 2.11.2010
• Reihe/Serie: Information Security and Cryptography
• Reihe/Serie: Information Security and Cryptography
• Zusatzinfo: XIII, 263 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Datenbanken
• Themenwelt: Informatik ► Netzwerke ► Sicherheit / Firewall
• Schlagworte: Covert Adversaries • Database • Data Mining • Definitions • Index • Introduction • Malicious Adversaries • Oblivious Transfer and Applications • References • Search Problems • Semi-honest Adversaries • Sigma Protocols and Efficient Zero-Knowledge • The k-th Ranked Element
• ISBN-13: 9783642143038 / 9783642143038