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

Round-Optimal Secure Multiparty Computation from Minimal Assumptions

Akshayaram Srinivasan

Published Jan 1, 2020• 0 citations
OpenAlex

Abstract

Secure Multiparty Computation (MPC) allows a set of parties, each having its own private data, to compute a function of their joint data such that the parties only learn the output of this function and everything else about their data is hidden. MPC is a fundamental cryptographic abstraction that captures many other natural cryptographic primitives as special cases. It also has a wide range of practical applications such as conducting secure electronic auctions, delegating sensitive computation to untrusted cloud service providers, secure computation on genomic data and training machine learning models on private data.A long-standing open problem in this area is to construct MPC protocols that have {\\it optimal} (two-round) round complexity under the {\\it weakest} possible cryptographic hardness assumptions.We {\\it completely resolve} this problem by showing lower bounds and matching upper bounds on the hardness assumptions required for constructing round-optimal MPC. Specifically, we obtain the following results.\\begin{itemize}\\item \\textbf{Black-Box Separation.} We show that there exists no construction of two-round semi-honest MPC protocol for general functions that makes black-box use of a two-round oblivious transfer. As a corollary, a similar separation holds when starting with any 2-party functionality other than oblivious transfer. \\item \\textbf{Non-Black-Box Construction.} We show that the above negative result can be bypassed by making non-black-box use of a two-round oblivious transfer. Specifically, starting from a semi-honest (resp. malicious) secure two-round oblivious transfer protocol, we construct a two-round MPC protocol against semi-honest (resp. malicious) adversaries. \\end{itemize}Since any two-round MPC protocol for general functionalities implies a two-round oblivious transfer as a special case, the above two results show that non-black-box use of oblivious transfer is {\\it necessary and sufficient} to construct round-optimal MPC protocols.

Related papers

Separating Two-Round Secure Computation From Oblivious Transfer

Benny Applebaum, Zvika Brakerski, Sanjam Garg +2 more

We consider the question of minimizing the round complexity of protocols for secure multiparty computation (MPC) with security against an arbitrary number of semi-honest parties. Very recently, Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) constructed such 2-round MPC protocols from minimal assumptions. This was done by showing a round preserving reduction to the task of secure 2-party computation of the oblivious transfer functionality (OT). These constructions made a novel non-black-box use of the underlying OT protocol. The question remained whether this can be done by only making black-box use of 2-round OT. This is of theoretical and potentially also practical value as black-box use of primitives tends to lead to more efficient constructions. Our main result proves that such a black-box construction is impossible, namely that non-black-box use of OT is necessary. As a corollary, a similar separation holds when starting with any 2-party functionality other than OT. As a secondary contribution, we prove several additional results that further clarify the landscape of black-box MPC with minimal interaction. In particular, we complement the separation from 2-party functionalities by presenting a complete 4-party functionality, give evidence for the difficulty of ruling out a complete 3-party functionality and for the difficulty of ruling out black-box constructions of 3-round MPC from 2-round OT, and separate a relaxed "non-compact" variant of 2-party homomorphic secret sharing from 2-round OT.

Leibniz international proceedings in informatics•Jan 1, 2020•9 citations

Round-Efficient Black-Box Construction of Composable Multi-Party Computation.

Susumu Kiyoshima

We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC’04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is $$\max (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ when the round complexity of the underlying oblivious transfer protocol is $$R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}$$ . Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a $$\widetilde{O}(\log ^2n)$$ -round protocol under these assumptions. Previously, only an $$O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ -round protocol was shown, where $$\epsilon >0$$ is an arbitrary constant. We obtain our MPC protocol by constructing a $$\widetilde{O}(\log ^2n)$$ -round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.

•Jan 1, 2014•0 citations

Two-round Multiparty Secure Computation from Minimal Assumptions

Sanjam Garg, Akshayaram Srinivasan

We provide new two-round multiparty secure computation (MPC) protocols in the dishonest majority setting assuming the minimal assumption that two-round oblivious transfer (OT) exists. If the assumed two-round OT protocol is secure against semi-honest adversaries (in the plain model) then so is our two-round MPC protocol. Similarly, if the assumed two-round OT protocol is secure against malicious adversaries (in the common random/reference string model) then so is our two-round MPC protocol. Previously, two-round MPC protocols were only known under relatively stronger computational assumptions.

Journal of the ACM•Oct 7, 2022•14 citations

On adaptive security and round efficiency in secure multi-party computation

Tal Malkin, Seung Geol Choi

Secure multi-party computation (MPC) enables distrustful parties to jointly perform computations while guaranteeing both the privacy of their inputs and the correctness of the computation. This thesis explores two aspects of secure multi-party computation: adaptive security and round efficiency. Adaptive security is concerned with an adversary that adaptively determines who and when to corrupt during the course of the computation. Even though this is a very natural and realistic assumption about the adversary, most of the MPC literature addresses security only against a static adversary — an adversary that chooses (and fixes) which parties to corrupt before the protocol starts executing. A protocol is called round-efficient if it runs in a small number of rounds. Constructing such protocols is important since efficiency of a protocol is greatly influenced by its round complexity. The security in this thesis is formulated in the universal composability (UC) framework introduced by Canetti [Can01]. Protocols secure in the UC framework remain secure even when executed concurrently with other arbitrary protocols running in some larger network, and can be used as subroutines of larger protocols in a modular fashion. This property is important considering that nowadays many protocols are executed concurrently with others in the Internet. With the focus on adaptive security and round efficiency, we obtain the following results: (1) We show that with access to an ideal commitment functionality, there exists a protocol that UC realizes any well-formed multi-party functionality against a malicious, adaptive adversary that may corrupt any number of parties, with black-box access to any protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary. (2) We show that there exists a protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary, with black-box access to a cryptographic primitive called a trapdoor simulatable cryptosystem, which is a natural relaxation of a simulatable cryptosystem introduced by Damgard and Nielsen [3N00]. We also show that the primitive can be constructed based on hardness of factoring. (3) We present a single-message protocol that UC realizes two-party computing with encrypted data (a variant of secure two-party computation), based on the DDH assumption and non- interactive zero-knowledge arguments. The protocol achieves security against a malicious, static adversary. (4) We present two round-efficient protocols that UC realize multi-party computing with encrypted data (a variant of secure multi-party computation), based on the DDH assumption and non-interactive zero-knowledge arguments. The first (resp. second) protocol requires one round (resp. two rounds) with appropriate preprocessing, which is independent of the exact circuit and actual inputs of the specific instance problem to solve — only the bound on the circuit size is known. Although the first protocol is more round-efficient, the preprocessing of the second is sometimes better under some efficiency considerations. Both protocols achieve security against a malicious, static adversary that may corrupt up to all but one parties.

•Jan 1, 2010•0 citations

Towards Optimality in Secure Computation

Saikrishna Badrinarayanan

The need for Cryptography arises out of the following fundamental question: can we perform useful computation while ensuring that an adversary does not learn anything about our private sensitive data? The notion of secure multiparty computation (MPC) \\cite{Yao82,GMW87} is a unifying framework for general secure protocols. MPC allows mutually distrusting parties to jointly evaluate any efficiently computable function on their private inputs in such a manner that each party does not learn anything beyond the output of the function. In this thesis, we study the question of building MPC protocols in various security models from standard cryptographic assumptions while minimizing the number of rounds of interaction amongst parties. In the first part of this thesis, (in a joint work with Vipul Goyal, Abhishek Jain, Yael Kalai, Dakshita Khurana and Amit Sahai, CRYPTO 2018) we construct the first round-optimal (i.e., four round) MPC protocol for general functions based on polynomially hard DDH (or QR or N$^{th}$-Residuosity) in the plain model where parties have access to no trusted setup. We further show how to overcome the four-round barrier for MPC by constructing a three-round protocol for ``list coin-tossing'' -- a slight relaxation of coin-tossing that suffices for most conceivable applications -- based on polynomially hard DDH (or QR or N$^{th}$-Residuosity). This result generalizes to randomized input-less functionalities. Previously, four round MPC protocols required sub-exponential-time hardness assumptions and no multi-party three-round protocols were known for any relaxed security notions with polynomial-time simulation against malicious adversaries. In order to build these protocols, we devise a new {\\em partitioned simulation} technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and non-aborting adversaries. The protagonist of this technique is a new notion of {\\em promise zero knowledge} (ZK) where the ZK property only holds against non-aborting verifiers. We show how to realize promise ZK in three rounds in the simultaneous-message model assuming polynomially hard DDH (or QR or N$^{th}$-Residuosity). We also rely upon a new {\\em leveled rewinding security} technique that can be viewed as a polynomial-time alternative to leveled complexity leveraging for achieving ``non-malleability'' across different primitives. Then, we also we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model (in a joint work with Vipul Goyal, Abhishek Jain, Dakshita Khurana and Amit Sahai, TCC 2017). In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model. We construct a three-round concurrent MPC with SPS security against Byzantine adversaries, assuming sub-exponentially secure DDH and LWE. Prior to our work, the best known round complexity for SPS concurrent MPC was around twenty, although to the best of our knowledge, no previous work even gave an approximation of the constant round complexity that is sufficient for concurrent MPC.In the second part of the thesis, (in a joint work with Abhishek Jain, Rafail Ostrovsky and Ivan Visconti, ASIACRYPT 2018), we study the problem of non-interactive secure computation in the stateless hardware token model where parties have access to physical hardware as part of a trusted setup phase. The notion of non-interactive secure computation (NISC) first introduced in the work of Ishai et al. [EUROCRYPT 2011] studies the following problem: Suppose a receiver $R$ wishes to publish an encryption of her secret input $y$ so that any sender $S$ with input $x$ can then send a message $m$ that reveals $f(x,y)$ to $R$ (for some function $f$). Here, $m$ can be viewed as an encryption of $f(x,y)$ that can be decrypted by $R$. NISC requires security against both malicious senders and receivers, and also requires the receiver's message to be reusable across multiple computations (w.r.t. a fixed input of the receiver). All previous solutions to this problem necessarily rely upon OT (or specific number-theoretic assumptions) even in the common reference string model or the random oracle model or to achieve weaker notions of security such as super-polynomial-time simulation. In this work, we construct a NISC protocol based on the minimal assumption of one way functions, in the stateless hardware token model. Our construction achieves UC security and requires a single token sent by the receiver to the sender.

•Jan 1, 2019•0 citations

Constant-Round Black-Box Construction of Composable Multi-Party Computation Protocol.

Susumu Kiyoshima, Yoshifumi Manabe, Tatsuaki Okamoto

Abstract. We present the first general MPC protocol that satisfies the following: (1) the con-struction is black-box, (2) the protocol is universally composable in the plain model, and (3) the number of rounds is constant. The security of our protocol is proven in angel-based UC security under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries and constant-round semi-honest oblivious transfer protocols that are secure against quasi-polynomial-time adversaries. We obtain the MPC protocol by constructing a constant-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries. To justify the use of such a sub-exponential hardness assumption in obtaining our constant-round CCA-secure commitment scheme, we show that if black-box reductions are used, there does not exist any constant-round CCA-secure commitment scheme under any falsifiable polynomial-time hardness assumptions. 1

•Jan 1, 2013•0 citations
Secure Multiparty Computation (MPC) allows a set of parties, each having its own private data, to compute a function of their joint data such that the parties only learn the output of this function and everything else about their data is hidden. MPC is a fundamental cryptographic abstraction that captures many other natural cryptographic primitives as special cases. It also has a wide range of practical applications such as conducting secure electronic auctions, delegating sensitive computation to untrusted cloud service providers, secure computation on genomic data and training machine learning models on private data.A long-standing open problem in this area is to construct MPC protocols that have {\it optimal} (two-round) round complexity under the {\it weakest} possible cryptographic hardness assumptions.We {\it completely resolve} this problem by showing lower bounds and matching upper bounds on the hardness assumptions required for constructing round-optimal MPC. Specifically, we obtain the following results.\begin{itemize}\item \textbf{Black-Box Separation.} We show that there exists no construction of two-round semi-honest MPC protocol for general functions that makes black-box use of a two-round oblivious transfer. As a corollary, a similar separation holds when starting with any 2-party functionality other than oblivious transfer. \item \textbf{Non-Black-Box Construction.} We show that the above negative result can be bypassed by making non-black-box use of a two-round oblivious transfer. Specifically, starting from a semi-honest (resp. malicious) secure two-round oblivious transfer protocol, we construct a two-round MPC protocol against semi-honest (resp. malicious) adversaries. \end{itemize}Since any two-round MPC protocol for general functionalities implies a two-round oblivious transfer as a special case, the above two results show that non-black-box use of oblivious transfer is {\it necessary and sufficient} to construct round-optimal MPC protocols.
We consider the question of minimizing the round complexity of protocols for secure multiparty computation (MPC) with security against an arbitrary number of semi-honest parties. Very recently, Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) constructed such 2-round MPC protocols from minimal assumptions. This was done by showing a round preserving reduction to the task of secure 2-party computation of the oblivious transfer functionality (OT). These constructions made a novel non-black-box use of the underlying OT protocol. The question remained whether this can be done by only making black-box use of 2-round OT. This is of theoretical and potentially also practical value as black-box use of primitives tends to lead to more efficient constructions. Our main result proves that such a black-box construction is impossible, namely that non-black-box use of OT is necessary. As a corollary, a similar separation holds when starting with any 2-party functionality other than OT. As a secondary contribution, we prove several additional results that further clarify the landscape of black-box MPC with minimal interaction. In particular, we complement the separation from 2-party functionalities by presenting a complete 4-party functionality, give evidence for the difficulty of ruling out a complete 3-party functionality and for the difficulty of ruling out black-box constructions of 3-round MPC from 2-round OT, and separate a relaxed "non-compact" variant of 2-party homomorphic secret sharing from 2-round OT.
We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC’04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is max⁡(O~(log⁡2n),O(ROT))\max (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))max(O(log2n),O(ROT​)) when the round complexity of the underlying oblivious transfer protocol is ROTR_{{{{\mathsf {O}}}{{\mathsf {T}}}}}ROT​ . Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a O~(log⁡2n)\widetilde{O}(\log ^2n)O(log2n) -round protocol under these assumptions. Previously, only an O(max⁡(nϵ,ROT))O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))O(max(nϵ,ROT​)) -round protocol was shown, where ϵ>0\epsilon >0ϵ>0 is an arbitrary constant. We obtain our MPC protocol by constructing a O~(log⁡2n)\widetilde{O}(\log ^2n)O(log2n) -round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.
We provide new two-round multiparty secure computation (MPC) protocols in the dishonest majority setting assuming the minimal assumption that two-round oblivious transfer (OT) exists. If the assumed two-round OT protocol is secure against semi-honest adversaries (in the plain model) then so is our two-round MPC protocol. Similarly, if the assumed two-round OT protocol is secure against malicious adversaries (in the common random/reference string model) then so is our two-round MPC protocol. Previously, two-round MPC protocols were only known under relatively stronger computational assumptions.
Secure multi-party computation (MPC) enables distrustful parties to jointly perform computations while guaranteeing both the privacy of their inputs and the correctness of the computation. This thesis explores two aspects of secure multi-party computation: adaptive security and round efficiency. Adaptive security is concerned with an adversary that adaptively determines who and when to corrupt during the course of the computation. Even though this is a very natural and realistic assumption about the adversary, most of the MPC literature addresses security only against a static adversary — an adversary that chooses (and fixes) which parties to corrupt before the protocol starts executing. A protocol is called round-efficient if it runs in a small number of rounds. Constructing such protocols is important since efficiency of a protocol is greatly influenced by its round complexity. The security in this thesis is formulated in the universal composability (UC) framework introduced by Canetti [Can01]. Protocols secure in the UC framework remain secure even when executed concurrently with other arbitrary protocols running in some larger network, and can be used as subroutines of larger protocols in a modular fashion. This property is important considering that nowadays many protocols are executed concurrently with others in the Internet. With the focus on adaptive security and round efficiency, we obtain the following results: (1) We show that with access to an ideal commitment functionality, there exists a protocol that UC realizes any well-formed multi-party functionality against a malicious, adaptive adversary that may corrupt any number of parties, with black-box access to any protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary. (2) We show that there exists a protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary, with black-box access to a cryptographic primitive called a trapdoor simulatable cryptosystem, which is a natural relaxation of a simulatable cryptosystem introduced by Damgard and Nielsen [3N00]. We also show that the primitive can be constructed based on hardness of factoring. (3) We present a single-message protocol that UC realizes two-party computing with encrypted data (a variant of secure two-party computation), based on the DDH assumption and non- interactive zero-knowledge arguments. The protocol achieves security against a malicious, static adversary. (4) We present two round-efficient protocols that UC realize multi-party computing with encrypted data (a variant of secure multi-party computation), based on the DDH assumption and non-interactive zero-knowledge arguments. The first (resp. second) protocol requires one round (resp. two rounds) with appropriate preprocessing, which is independent of the exact circuit and actual inputs of the specific instance problem to solve — only the bound on the circuit size is known. Although the first protocol is more round-efficient, the preprocessing of the second is sometimes better under some efficiency considerations. Both protocols achieve security against a malicious, static adversary that may corrupt up to all but one parties.
The need for Cryptography arises out of the following fundamental question: can we perform useful computation while ensuring that an adversary does not learn anything about our private sensitive data? The notion of secure multiparty computation (MPC) \\cite{Yao82,GMW87} is a unifying framework for general secure protocols. MPC allows mutually distrusting parties to jointly evaluate any efficiently computable function on their private inputs in such a manner that each party does not learn anything beyond the output of the function. In this thesis, we study the question of building MPC protocols in various security models from standard cryptographic assumptions while minimizing the number of rounds of interaction amongst parties. In the first part of this thesis, (in a joint work with Vipul Goyal, Abhishek Jain, Yael Kalai, Dakshita Khurana and Amit Sahai, CRYPTO 2018) we construct the first round-optimal (i.e., four round) MPC protocol for general functions based on polynomially hard DDH (or QR or Nth^{th}th-Residuosity) in the plain model where parties have access to no trusted setup. We further show how to overcome the four-round barrier for MPC by constructing a three-round protocol for ``list coin-tossing'' -- a slight relaxation of coin-tossing that suffices for most conceivable applications -- based on polynomially hard DDH (or QR or Nth^{th}th-Residuosity). This result generalizes to randomized input-less functionalities. Previously, four round MPC protocols required sub-exponential-time hardness assumptions and no multi-party three-round protocols were known for any relaxed security notions with polynomial-time simulation against malicious adversaries. In order to build these protocols, we devise a new {\\em partitioned simulation} technique for MPC where the simulator uses different strategies for simulating the view of aborting adversaries and non-aborting adversaries. The protagonist of this technique is a new notion of {\\em promise zero knowledge} (ZK) where the ZK property only holds against non-aborting verifiers. We show how to realize promise ZK in three rounds in the simultaneous-message model assuming polynomially hard DDH (or QR or Nth^{th}th-Residuosity). We also rely upon a new {\\em leveled rewinding security} technique that can be viewed as a polynomial-time alternative to leveled complexity leveraging for achieving ``non-malleability'' across different primitives. Then, we also we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model (in a joint work with Vipul Goyal, Abhishek Jain, Dakshita Khurana and Amit Sahai, TCC 2017). In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model. We construct a three-round concurrent MPC with SPS security against Byzantine adversaries, assuming sub-exponentially secure DDH and LWE. Prior to our work, the best known round complexity for SPS concurrent MPC was around twenty, although to the best of our knowledge, no previous work even gave an approximation of the constant round complexity that is sufficient for concurrent MPC.In the second part of the thesis, (in a joint work with Abhishek Jain, Rafail Ostrovsky and Ivan Visconti, ASIACRYPT 2018), we study the problem of non-interactive secure computation in the stateless hardware token model where parties have access to physical hardware as part of a trusted setup phase. The notion of non-interactive secure computation (NISC) first introduced in the work of Ishai et al. [EUROCRYPT 2011] studies the following problem: Suppose a receiver RRR wishes to publish an encryption of her secret input yyy so that any sender SSS with input xxx can then send a message mmm that reveals f(x,y)f(x,y)f(x,y) to RRR (for some function fff). Here, mmm can be viewed as an encryption of f(x,y)f(x,y)f(x,y) that can be decrypted by RRR. NISC requires security against both malicious senders and receivers, and also requires the receiver's message to be reusable across multiple computations (w.r.t. a fixed input of the receiver). All previous solutions to this problem necessarily rely upon OT (or specific number-theoretic assumptions) even in the common reference string model or the random oracle model or to achieve weaker notions of security such as super-polynomial-time simulation. In this work, we construct a NISC protocol based on the minimal assumption of one way functions, in the stateless hardware token model. Our construction achieves UC security and requires a single token sent by the receiver to the sender.
Abstract. We present the first general MPC protocol that satisfies the following: (1) the con-struction is black-box, (2) the protocol is universally composable in the plain model, and (3) the number of rounds is constant. The security of our protocol is proven in angel-based UC security under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries and constant-round semi-honest oblivious transfer protocols that are secure against quasi-polynomial-time adversaries. We obtain the MPC protocol by constructing a constant-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries. To justify the use of such a sub-exponential hardness assumption in obtaining our constant-round CCA-secure commitment scheme, we show that if black-box reductions are used, there does not exist any constant-round CCA-secure commitment scheme under any falsifiable polynomial-time hardness assumptions. 1