Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Efficient Multi-Party Computation over Rings.

Ronald Cramer, Serge Fehr, Yuval Ishai, Eyal Kushilevitz

Published Jan 1, 2003• 11 citations
OpenAlex

Abstract

Abstract. Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite fields. We are motivated by two limitations of these techniques:- Generality. Existing protocols do not apply to computation over

Related papers

A Pragmatic Introduction to Secure Multi-Party Computation

David Evans, Vladimir Kolesnikov, Mike Rosulek

Secure multi-party computation (MPC) has evolved from a theoretical curiosity in the 1980s to a tool for building real systems today. Over the past decade, MPC has been one of the most active research areas in both theoretical and applied cryptography. This article introduces several important MPC protocols, and surveys methods for improving the efficiency of privacy-preserving applications built using MPC. Besides giving a broad overview of the field and the insights of the main constructions, we overview the most currently active areas of MPC research and aim to give readers insights into what problems are practically solvable using MPC today and how different threat models and assumptions impact the practicality of different approaches.

Foundations and Trends® in Privacy and Security•Dec 19, 2018•369 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, 2024•0 citations

Secure multiParty computation protocols

Daniel Casanova Faria Torres

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 fields. 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.

•Mar 13, 2015•0 citations

Generalizing the SPDZ Compiler For Other Protocols

Toshinori Araki, Assi Barak, Jun Furukawa +4 more

Protocols for secure multiparty computation (MPC) enable a set of mutually distrusting parties to compute an arbitrary function of their inputs while preserving basic security properties like privacy and correctness. The study of MPC was initiated in the 1980s where it was shown that any function can be securely computed, thus demonstrating the power of this notion. However, these proofs of feasibility were theoretical in nature and it is only recently that MPC protocols started to become efficient enough for use in practice. Today, we have protocols that can carry out large and complex computations in very reasonable time (and can even be very fast, depending on the computation and the setting). Despite this amazing progress, there is still a major obstacle to the adoption and use of MPC due to the huge expertise needed to design a specific MPC execution. In particular, the function to be computed needs to be represented as an appropriate Boolean or arithmetic circuit, and this requires very specific expertise. In order to overcome this, there has been considerable work on compilation of code to (typically) Boolean circuits. One work in this direction takes a different approach, and this is the SPDZ compiler (not to be confused with the SPDZ protocol) that takes high-level Python code and provides an MPC run-time environment for securely executing that code. The SPDZ compiler can deal with arithmetic and non-arithmetic operations and is extremely powerful. However, until now, the SPDZ compiler could only be used for the specific SPDZ family of protocols, making its general applicability and usefulness very limited. In this paper, we extend the SPDZ compiler so that it can work with general underlying protocols. Our SPDZ extensions were made in mind to enable the use of SPDZ for arbitrary protocols and to make it easy for others to integrate existing and new protocols. We integrated three different types of protocols, an honest-majority protocol for computing arithmetic circuits over a field (for any number of parties), a three-party honest majority protocol for computing arithmetic circuits over the ring of integers Z2n, and the multiparty BMR protocol for computing Boolean circuits. We show that a single high-level SPDZ-Python program can be executed using all of these underlying protocols (as well as the original SPDZ protocol), thereby making SPDZ a true general run-time MPC environment.In order to be able to handle both arithmetic and non-arithmetic operations, the SPDZ compiler relies on conversions from field elements to bits and back. However, these conversions do not apply to ring elements (in particular, they require element division), and we therefore introduce new bit decomposition and recomposition protocols for the ring over integers with replicated secret sharing. These conversions are of independent interest and utilize the structure of Z2n (which is much more amenable to bit decomposition than prime-order fields), and are thus much more efficient than all previous methods. We demonstrate our compiler extensions by running a complex SQL query and a decision tree evaluation over all protocols.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Oct 15, 2018•52 citations

An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings.

Mark Abspoel, Anders Dalskov, Daniel E. Escudero +1 more

Multiparty computation (MPC) over rings such as \(\mathbb {Z}_{2^{32}}\) or \(\mathbb {Z}_{2^{64}}\) has received a great deal of attention recently due to its ease of implementation and attractive performance. Several actively secure protocols over these rings have been implemented, for both the dishonest majority setting and the setting of three parties with one corruption. However, in the honest majority setting, no concretely efficient protocol for arithmetic computation over rings has yet been proposed that allows for an arbitrary number of parties.

•Jan 1, 2019•3 citations

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 Security•Apr 30, 2020•0 citations
Abstract. Secure multi-party computation (MPC) is an active research area, and a wide range of literature can be found nowadays suggesting improvements and generalizations of existing protocols in various directions. However, all current techniques for secure MPC apply to functions that are represented by (boolean or arithmetic) circuits over finite fields. We are motivated by two limitations of these techniques:- Generality. Existing protocols do not apply to computation over
Secure multi-party computation (MPC) has evolved from a theoretical curiosity in the 1980s to a tool for building real systems today. Over the past decade, MPC has been one of the most active research areas in both theoretical and applied cryptography. This article introduces several important MPC protocols, and surveys methods for improving the efficiency of privacy-preserving applications built using MPC. Besides giving a broad overview of the field and the insights of the main constructions, we overview the most currently active areas of MPC research and aim to give readers insights into what problems are practically solvable using MPC today and how different threat models and assumptions impact the practicality of different approaches.
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
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 fields. 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.
Protocols for secure multiparty computation (MPC) enable a set of mutually distrusting parties to compute an arbitrary function of their inputs while preserving basic security properties like privacy and correctness. The study of MPC was initiated in the 1980s where it was shown that any function can be securely computed, thus demonstrating the power of this notion. However, these proofs of feasibility were theoretical in nature and it is only recently that MPC protocols started to become efficient enough for use in practice. Today, we have protocols that can carry out large and complex computations in very reasonable time (and can even be very fast, depending on the computation and the setting). Despite this amazing progress, there is still a major obstacle to the adoption and use of MPC due to the huge expertise needed to design a specific MPC execution. In particular, the function to be computed needs to be represented as an appropriate Boolean or arithmetic circuit, and this requires very specific expertise. In order to overcome this, there has been considerable work on compilation of code to (typically) Boolean circuits. One work in this direction takes a different approach, and this is the SPDZ compiler (not to be confused with the SPDZ protocol) that takes high-level Python code and provides an MPC run-time environment for securely executing that code. The SPDZ compiler can deal with arithmetic and non-arithmetic operations and is extremely powerful. However, until now, the SPDZ compiler could only be used for the specific SPDZ family of protocols, making its general applicability and usefulness very limited. In this paper, we extend the SPDZ compiler so that it can work with general underlying protocols. Our SPDZ extensions were made in mind to enable the use of SPDZ for arbitrary protocols and to make it easy for others to integrate existing and new protocols. We integrated three different types of protocols, an honest-majority protocol for computing arithmetic circuits over a field (for any number of parties), a three-party honest majority protocol for computing arithmetic circuits over the ring of integers Z2n, and the multiparty BMR protocol for computing Boolean circuits. We show that a single high-level SPDZ-Python program can be executed using all of these underlying protocols (as well as the original SPDZ protocol), thereby making SPDZ a true general run-time MPC environment.In order to be able to handle both arithmetic and non-arithmetic operations, the SPDZ compiler relies on conversions from field elements to bits and back. However, these conversions do not apply to ring elements (in particular, they require element division), and we therefore introduce new bit decomposition and recomposition protocols for the ring over integers with replicated secret sharing. These conversions are of independent interest and utilize the structure of Z2n (which is much more amenable to bit decomposition than prime-order fields), and are thus much more efficient than all previous methods. We demonstrate our compiler extensions by running a complex SQL query and a decision tree evaluation over all protocols.
Multiparty computation (MPC) over rings such as Z232\mathbb {Z}_{2^{32}}Z232​ or Z264\mathbb {Z}_{2^{64}}Z264​ has received a great deal of attention recently due to its ease of implementation and attractive performance. Several actively secure protocols over these rings have been implemented, for both the dishonest majority setting and the setting of three parties with one corruption. However, in the honest majority setting, no concretely efficient protocol for arithmetic computation over rings has yet been proposed that allows for an arbitrary number of parties.
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.