Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2010 | Book

Introduction Read chapter Read first chapter

Efficient Secure Two-Party Protocols

Techniques and Constructions

Authors: Carmit Hazay, Yehuda Lindell

Publisher: Springer Berlin Heidelberg

Book Series : Information Security and Cryptography

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

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.

Table of Contents

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
Metadata
Title
Efficient Secure Two-Party Protocols
Authors
Carmit Hazay
Yehuda Lindell
Copyright Year
2010
Publisher
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-14303-8
Print ISBN
978-3-642-14302-1
DOI
https://doi.org/10.1007/978-3-642-14303-8

Premium Partner

    Image Credits