Secure multiParty computation protocols

Daniel Casanova Faria Torres

Published Mar 13, 2015• 0 citations

Abstract

Secure Multiparty Computation (abrv. MPC) is a group of techniques that enable multiple entities to compute some function on their private inputs. Moreformally,itenablesasetofplayers{P1,...,Pn},eachofthemholding private inputs xi, where i is the index of the player, to evaluate a function f(x1,...,xn) = (y1,...,yn) so that every player Pi learns yi. Multiparty Computation has many application scenarios such as private auctioning, computation outsourcing, or private information retrieval. These and other applications make MPC a very appealing object of study, since it may be a solution to problems in different ﬁelds. The objective of this thesis is twofold. First, we aim to provide a comprehensive guide to the current state of multiparty computation protocols. Wedosobyinspectingthetwocategorieswheremostgeneralfunctionality secure function evaluation protocols are inserted - boolean or arithmetic circuit evaluation. Moreover, we show how to implement MPC protocols with current constructions, and what problems are inherently connected to the chosen representations. Second, we document some of the design choices behind a partial implementation of a concrete secure arithmetic circuit evaluation protocol - the SPDZ protocol by Damgård et al. [10]. We explain the protocol in general terms, and then go into the details of some subprotocols, namely those that were implemented.

Related papers

Secure Multiparty Computation Goes Live

Peter Bogetoft, Dan Lund Christensen, Ivan Damgård +9 more

Abstract. In this note, we report on the first large-scale and practical application of multiparty computation, which took place in January 2008. We also report on the novel cryptographic protocols that were used. 1 Introduction and History In multiparty computation (MPC), we consider a number of players P1,..., Pn, who initially each hold inputs x1,..., xn, and we then want to securely compute some function f on these inputs, where f(x1,..., xn) = (y1,..., yn), such that Pi learns yi but no other information. This should hold, even if players exhibit some amount of adversarial behavior. The goal can be accomplished by an interactive

Jan 1, 20083 citations

Secure Computation in Heterogeneous Environments: How to Bring Multiparty Computation Closer to Practice?

Raykova, Mariana Petrova

Many services that people use daily require computation that depends on the private data of multiple parties. While the utility of the final result of such interactions outweighs the privacy concerns related to output release, the inputs for such computations are much more sensitive and need to be protected. Secure multiparty computation (MPC) considers the question of constructing computation protocols that reveal nothing more about their inputs than what is inherently leaked by the output. There have been strong theoretical results that demonstrate that every functionality can be computed securely. However, these protocols remain unused in practical solutions since they introduce efficiency overhead prohibitive for most applications. Generic multiparty computation techniques address homogeneous setups with respect to the resources available to the participants and the adversarial model. On the other hand, realistic scenarios present a wide diversity of heterogeneous environments where different participants have different available resources and different incentives to misbehave and collude. In this thesis we introduce techniques for multiparty computation that focus on heterogeneous settings. We present solutions tailored to address different types of asymmetric constraints and improve the efficiency of existing approaches in these scenarios. We tackle the question from three main directions: New Computational Models for MPC - We explore different computational models that enable us to overcome inherent inefficiencies of generic MPC solutions using circuit representation for the evaluated functionality. First, we show how we can use random access machines to construct MPC protocols that add only polylogarithmic overhead to the running time of the insecure version of the underlying functionality. This allows to achieve MPC constructions with computational complexity sublinear in the size for their inputs, which is very important for computations that use large databases. We also consider multivariate polynomials which yield more succinct representations for the functionalities they implement than circuits, and at the same time a large collection of problems are naturally and efficiently expressed as multivariate polynomials. We construct an MPC protocol for multivariate polynomials, which improves the communication complexity of corresponding circuit solutions, and provides currently the most efficient solution for multiparty set intersection in the fully malicious case. Outsourcing Computation - The goal in this setting is to utilize the resources of a single powerful service provider for the work that computationally weak clients need to perform on their data. We present a new paradigm for constructing verifiable computation (VC) schemes, which enables a computationally limited client to verify efficiently the result of a large computation. Our construction is based on attribute-based encryption and avoids expensive primitives such as fully homomorphic encryption andprobabilistically checkable proofs underlying existing VC schemes. Additionally our solution enjoys two new useful properties: public delegation and verification. We further introduce the model of server-aided computation where we utilize the computational power of an outsourcing party to assist the execution and improve the efficiency of MPC protocols. For this purpose we define a new adversarial model of non-collusion, which provides room for more efficient constructions that rely almost completely only on symmetric key operations, and at the same time captures realistic settings for adversarial behavior. In this model we propose protocols for generic secure computation that offload the work of most of the parties to the computation server. We also construct a specialized server-aided two party set intersection protocol that achieves better efficiencies for the two participants than existing solutions. Outsourcing in many cases concerns only data storage and while outsourcing the data of a single party is useful, providing a way for data sharing among different clients of the service is the more interesting and useful setup. However, this scenario brings new challenges for access control since the access control rules and data accesses become private data for the clients with respect to the service provide. We propose an approach that offers trade-offs between the privacy provided for the clients and the communication overhead incurred for each data access. Efficient Private Search in Practice - We consider the question of private search from a different perspective compared to traditional settings for MPC. We start with strict efficiency requirements motivated by speeds of available hardware and what is considered acceptable overhead from practical point of view. Then we adopt relaxed definitions of privacy, which still provide meaningful security guarantees while allowing us to meet the efficiency requirements. In this setting we design a security architecture and implement a system for data sharing based on encrypted search, which achieves only 30% overhead compared to non-secure solutions on realistic workloads.

Jan 1, 20124 citations

Implementation of a Secure Multiparty Computation Protocol

Tahsin C. M. Dönmez

Secure multiparty computation (SMC) allows a set of parties to jointly compute a function on private inputs such that, they learn only the output of the function, and the correctness of the output is guaranteed even when a subset of the parties is controlled by an adversary. SMC allows data to be kept in an uncompromisable form and still be useful, and it also gives new meaning to data ownership, allowing data to be shared in a useful way while retaining its privacy. Thus, applications of SMC hold promise for addressing some of the security issues information-driven societies struggle with. In this thesis, we implement two SMC protocols. Our primary objective is to gain a solid understanding of the basic concepts related to SMC. We present a brief survey of the field, with focus on SMC based on secret sharing. In addition to the protocol im- plementations, we implement circuit randomization, a common technique for efficiency improvement. The implemented protocols are run on a simulator to securely evaluate some simple arithmetic functions, and the round complexities of the implemented protocols are compared. Finally, we attempt to extend the implementation to support more general computations.

Dec 20, 20170 citations

Is multiparty computation any good in practice?

Claudio Orlandi

The aim of this paper is to present some of the recent progress in efficient secure multiparty computation (MPC). In MPC we have a set of parties owning a set of private inputs. The par ties want to compute a function of their inputs, but they do not trust each other, therefore they need a cryptographic protocol to perform the computation in a way that 1) the output is correct and 2) cheating parties will not be able to learn any information about the honest parties inputs. Even though this problem has been formulated and essentially solved almost 30 years ago, practical solutions that can be relevant for real-world applications have been discovered only in the last few years. We will present some of these advances, trying to explain to a non-specialized audience the significance of the several existing security notions.

IEEE International Conference on Acoustics Speech and Signal ProcessingMay 1, 201151 citations

Efficient threshold multiparty computation schemes

Schuyler Rosefield

Multiparty Computation (hereafter MPC) is a technique for allowing a set ofparticipants to run a secure computation with the assurance that the output is (1) correct, and (2) that a malicious party did not learn anything about the inputs of the honest parties besides what it can glean from the output. Impor- tantly much of cryptography is based on the assumption that an honest party has a private and secret input, and if the adversary learns this input the security of the scheme is broken. Then naturally the techniques of MPC can be applied to create threshold protocols for these cryptographic schemes to ensure that the secret inputs are not leaked and moreover that no group of parties smaller than the threshold know the input at all. While we have known how to generically evaluate MPC for any function since the 80s the question of efficiency still drives progress to this day. This thesis looks at two approaches for making secure com- putation more practical to deploy: developing specialized protocols for appli- cations such as distributed key generation and signing with RSA and ECDSA; and improving the state of the art of maliciously secure generic boolean-circuit MPC. We first look at work that produced a distributed key generation protocol for RSA that utilizes a novel candidate sampling mechanism to reduce waste in primality testing. The second work builds a threshold scheme for symmetric cryptographic primitives such as AES and SHA where there is limited algebraic structure to exploit by efficiently converting a generic n-of-n MPC protocol into a threshold t-of-n MPC protocol. Future directions in this thesis are in combin- ing techniques from the prior works to create a blind signature scheme for the Elliptic Curve Digital Signature Algorithm (ECDSA) that requires both alge- braic operations over elliptic curves and additionally symmetric evaluations of the SHA2 hash function.--Author's abstract

Jan 1, 20240 citations

MPC Protocols with Passive Security

Ronald Cramer, Ivan Damgård, Jesper Buus Nielsen

Introduction In Chapter 1 we gave an introduction to the multiparty computation problem and explained what it intuitively means for a protocol to compute a given function securely, namely, we want a protocol that is correct and private. However, we only considered three players, we only argued that a single player does not learn more than he or she is supposed to, and finally, we assumed that all players would follow the protocol. In this chapter we will consider a more general solution to multiparty computation, where we remove the first two restrictions: we will consider any number n ≥ 3 of players, and we will be able to show that as long as at most t < n /2 of the players go together after the protocol is executed and pool all their information, they will learn nothing more than their own inputs and the outputs they were supposed to receive, even if their computing power is unbounded. We will still assume, however, that all players follow the protocol. This is known as semihonest or passive security . To argue security in this chapter, we will use a somewhat weak but very simple definition that only makes sense for semihonest security. We then extend this in Chapter 4 to a fully general model of what protocols are and what security means. Throughout this chapter we will assume that each pair of players can communicate using a perfectly secure channel, so if two players exchange data, a third player has no information at all about what is sent. Such channels might be available because of physical circumstances, or we can implement them relative to a computational assumption using cryptography. For more details on this, see Chapter 7. We end the chapter by showing that the bound t < n /2 is optimal: if t ≥ n /2, then some functions cannot be computed securely in the model mentioned, that is, obtaining perfect security by using only secure point-to-point communication as the communication resource. Secret Sharing Our main tool to build the protocol will be secret-sharing schemes. The theory of secret-sharing schemes is a large and interesting field in its own right with many applications to multiparty computation (MPC), and we look at this in more detail in Chapter 11, where a formal definition of the notion as well as a general treatment of the theory of secret sharing can be found.

Cambridge University Press eBooksJun 30, 20150 citations