IEEE International Conference on Acoustics Speech and Signal Processing

Is multiparty computation any good in practice?

Claudio Orlandi

Published May 1, 2011• 51 citations

Abstract

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.

DOI: 10.1109/icassp.2011.5947691

Related papers

Secure Multi-Party Computation: A and Future Directions

Dr. Emily J. Carter, Dr. Michael Brown

Secure Multi-Party Computation (MPC) is a cryptographic framework that enables multiple parties to jointly compute a function over their inputs while keeping those inputs private. MPC has found applications in privacy-preserving data analytics, secure voting, private machine learning, and secure financial transactions. This article provides a comprehensive survey of recent advances in MPC protocols, including fully homomorphic encryption, garbled circuits, and oblivious transfer. It also explores the challenges in efficiency, scalability, and real-world deployment of MPC and discusses future research directions to enhance its practicality and security.

American Journal Of Cryptography And Network SecurityApr 30, 20200 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

Publicly Auditable Secure Multi-Party Computation

Carsten Baum, Ivan Damgård, Claudio Orlandi

In the last few years the efficiency of secure multi-party computation (MPC) increased in several orders of magnitudes. However, this alone might not be enough if we want MPC protocols to be used in practice. A crucial property that is needed in many applications is that everyone can check that a given (secure) computation was performed correctly – even in the extreme case where all the parties involved in the computation are corrupted, and even if the party who wants to verify the result was not participating. This is especially relevant in the clients-servers setting, where many clients provide input to a secure computation performed by a few servers. An obvious example of this is electronic voting, but also in many types of auctions one may want independent verification of the result. Traditionally, this is achieved by using non-interactive zero-knowledge proofs during the computation.A recent trend in MPC protocols is to have a more expensive preprocessing phase followed by a very efficient online phase, e.g., the recent so-called SPDZ protocol by Damgård et al. Applications such as voting and some auctions are perfect use-case for these protocols, as the parties usually know well in advance when the computation will take place, and using those protocols allows us to use only cheap information-theoretic primitives in the actual computation. Unfortunately no protocol of the SPDZ type supports an audit phase.In this paper, we show how to achieve efficient MPC with a public audit. We formalize the concept of publicly auditable secure computation and provide an enhanced version of the SPDZ protocol where, even if all the servers are corrupted, anyone with access to the transcript of the protocol can check that the output is indeed correct. Most importantly, we do so without significantly compromising the performance of SPDZ i.e. our online phase has complexity approximately twice that of SPDZ.

Lecture notes in computer scienceJan 1, 2014115 citations

MPC in de echte wereld: praktische aspecten van meerpartijrekenen

Botelho da Gama, Mariana

In 1982, Yao presented a protocol that allowed two parties to compute over their private inputs while revealing nothing but the final output. This first theoretical construction originated a fruitful line of research exploring the possibilities of the cryptographic technique known as multi-party computation, or MPC. Today, we have MPC schemes with practical efficiency that can be used for a wide range of applications and use cases, from securing cryptographic keys to training Machine Learning models on private data. Despite the advancements from the past few decades, we have only started to bridge the gap between theory and practice, and several obstacles stand in the way of the widespread adoption of MPC. First, the performance overhead depends heavily on the computation we want to perform. Not all computations are well-suited to be distributed with MPC, and algorithms must usually be refactored before they can be executed securely. Furthermore, the practical efficiency of most modern protocols quickly deteriorates as the number of parties increases and comes at the expense of the security guarantees provided. On the other hand, almost all academic works assume a static set of MPC parties, all pairwise connected by dedicated channels in a network without delays or failures. Yet, these assumptions are hardly achievable in current real-world networks. In this thesis, we study three practical aspects of multi-party computation: (i) we discuss how to improve performance by designing algorithms tailor-made for execution with MPC. To this end, we present and evaluate secure auction mechanisms for the financial setting and for the peer-to-peer electricity market. (ii) We analyse the information leakage from the MPC computation outputs. In particular, we focus on the case of individual and private correlated outputs, for which we propose a new privacy notion. Lastly, (iii) we consider the problem of building efficient large-scale MPC. We explore the possibilities and limitations associated with standard (fully connected) networks and present a new protocol with a star-like network topology and resilience against delayed parties.

Feb 10, 20250 citations

Techniques for scalable secure computation systems

Kreuter

Secure Multiparty Computation protocols allow a set of mutually distrustful parties to compute a function on their respective inputs while guaranteeing both the privacy of the inputs and the correctness of the outputs. Despite thirty years of research and many potential real-world applications, MPC deployment remains limited by efficiency and scalability bottlenecks. This thesis presents novel protocol designs and engineering techniques to address those performance and scalability issues.

Jan 1, 20181 citation

On secret sharing-based classical and quantum multi-party computation

J.G. Hölting

Secure multi-party computation (MPC) is a cryptographic primitive that lets a num- ber N of mutually distrustful parties compute a function f (x1, . . . , xN ) on their private inputs xi such that at the end of the MPC protocol, each honest party obtains the func- tion’s correct output and no adversary controlling a certain subset of parties learns any- thing about the honest parties’ inputs beyond what can be inferred from the function’s output value. In 2002, [Smi01] and [CGS02] introduced the notion of multi-party quan- tum computation (MPQC) in which arbitrary quantum circuits can be evaluated in a distributed manner, secure against a quantum adversary. Few protocols for MPQC are known. We present a fundamental study of the building blocks of MPC and MPQC in the information-theoretic setting with a focus on protocols built on top of (quantum) se- cret sharing schemes. In particular, we point out structural similarities and differences and compile an extensive list of theoretical feasibility results for the maximum number of corrupted parties within classical and quantum secret sharing and MPC protocols.

Jan 1, 20200 citations