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