Skip to main content
main-content

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Introduction and Definitions

Frontmatter

Chapter 1. Introduction

Abstract
The focus of this book is on constructing efficientsecure protocols for the two-party setting. In this introduction, we begin with a general high-level survey of secure multiparty computation. This places the topic of this book in its larger context. Following this, we describe the basic results and techniques related to efficiency in secure computation. Finally, we conclude with a roadmap to the book.
Carmit Hazay, Yehuda Lindell

Chapter 2. Definitions

Abstract
In this chapter we present a number of definitions of security for secure computation. Specifically, in Sections 2.2 to 2.4 we present definitions of security for semi-honest, malicious and covert adversaries; all these definitions are based on the ideal/real-model paradigm for formulating security. We begin with the classic definitions of security in the presence of semi-honest and malicious adversaries, and then proceed to the more recent notion of security in the presence of covert adversaries.
Carmit Hazay, Yehuda Lindell

General Constructions

Frontmatter

Chapter 3. Semi-honest Adversaries

Abstract
In this chapter, we present Yao’s protocol for secure two-party computation in the presence of semi-honest adversaries. The protocol has a constant number of rounds, and works by having the parties evaluate an “encrypted” or “garbled” circuit such that they learn nothing from the evaluation but the output itself. In particular, all intermediate values in the circuit evaluation (which can reveal more information than is allowed) remain hidden from both parties. We present the protocol for the case of a deterministic, non-reactive, single-output functionality. As we have shown in Section 2.5, this suffices for obtaining the secure computation of any probabilistic, reactive two-party functionality at approximately the same cost.
Carmit Hazay, Yehuda Lindell

Chapter 4. Malicious Adversaries

Abstract
In this chapter, we show how to securely compute any deterministic, singleoutput non-reactive functionality in the presence of malicious adversaries. As we have shown in Section 2.5, this suffices for obtaining secure computation of any two-party probabilistic reactive functionality, with almost the same complexity.
Carmit Hazay, Yehuda Lindell

Chapter 5. Covert Adversaries

Abstract
In this chapter, we present protocols for securely computing any functionality in the model of covert adversaries; see Section 2.4 for motivation and definitions of the model. We begin by presenting a protocol for oblivious transfer that is secure in the covert model. We present this protocol mainly for didactic reasons; it serves as a good warm-up for understanding how to prove security in this model. Nevertheless, we stress that more efficient oblivious transfer protocols are known (both for the covert and malicious settings; see Section 7.4 for an example).
Carmit Hazay, Yehuda Lindell

Specific Constructions

Frontmatter

Chapter 6. Sigma Protocols and Efficient Zero-Knowledge1

Abstract
A zero-knowledge proof is an interactive proof with the additional property that the verifier learns nothing beyond the correctness of the statement being proved. The theory of zero-knowledge proofs is beautiful and rich, and is a cornerstone of the foundations of cryptography. In the context of cryptographic protocols, zero-knowledge proofs can be used to enforce “good behavior” by having parties prove that they indeed followed the protocol correctly. These proofs must reveal nothing about the parties’ private inputs, and as such must be zero knowledge. Zero-knowledge proofs are often considered an expensive (and somewhat naive) way of enforcing honest behavior, and those who view them in this way consider them to be not very useful when constructing efficient protocols.
Carmit Hazay, Yehuda Lindell

Chapter 7. Oblivious Transfer and Applications

Abstract
In this chapter we carry out an in-depth study of the problem of constructing efficient protocols for oblivious transfer (as introduced in Section 3.2.2). Oblivious transfer is one of the most important building blocks in cryptography, and is very useful for constructing secure protocols. We demonstrate this by showing how to achieve secure pseudorandom function evaluation using oblivious transfer.
Carmit Hazay, Yehuda Lindell

Chapter 8. The kth-Ranked Element

Abstract
In this chapter we describe the construction of Aggarwal et al. [1] for securely computing the kth-ranked element of the union of two distributed and sorted data sets in the presence of semi-honest and malicious adversaries. An important special case of this problem is that of securely computing the median. The construction of [1] is based on the iterative protocol of [74] for computing the kth-ranked element with low communication complexity. The secure implementation of this fundamental problem has been looked at by researchers in the last few years, mostly due to its potential applications. One particular setting is where the data sets contain sensitive data, yet the particular kth element is of mutual interest. For instance, two health insurance companies may wish to compute the median life expectancy of their insured smokers, or two companies may wish to compute the median salary of their employees. By running secure protocols for these tasks, sensitive information is not unnecessarily revealed.
Carmit Hazay, Yehuda Lindell

Chapter 9. Search Problems

Abstract
Recently, there has been much interest in the data mining and other communities for secure protocols for a wide variety of tasks. This interest exists not only in academic circles, but also in industry, in part due to the growing conflict between the privacy concerns of citizens and the homeland security needs of governments. In this chapter we focus on search problems involving two parties; a client that is interested in performing a search in a database that is being held by a server. The (informal) security requirements for search problems assert that the server should not learn any useful information regarding the search conducted by the client, while the client should learn the search result but nothing more.
Carmit Hazay, Yehuda Lindell

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise