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

Network and Distributed System Security Symposium

hbACSS: How to Robustly Share Many Secrets

Thomas Yurek, Licheng Luo, Jaiden Fairoze, Aniket Kate, Andrew K. Miller

Published Jan 1, 2022• 35 citations
Publisher

Abstract

Despite significant recent progress toward making multi-party computation (MPC) practical, no existing MPC library offers complete robustness-meaning guaranteed output delivery, including in the offline phase-in a network that even has intermittent delays.Importantly, several theoretical MPC constructions already ensure robustness in this setting.We observe that the key reason for this gap between theory and practice is the absence of efficient verifiable/complete secret sharing (VSS/CSS) constructions; existing CSS protocols either require a) challenging broadcast channels in practice or b) introducing computation and communication overhead that is at least quadratic in the number of players.This work presents hbACSS, a suite of optimal-resilience asynchronous complete secret sharing protocols that are (quasi)linear in both computation and communication overhead.Towards developing hbACSS, we develop hbPolyCommit, an efficient polynomial commitment scheme that is (quasi)linear (in the polynomial degree) in terms of computation and communication overhead without requiring a trusted setup.We implement our hbACSS protocols, extensively analyze their practicality, and observe that our protocols scale well with an increasing number of parties.In particular, we use hbACSS to generate MPC input masks: a useful primitive which had previously only been calculated nonrobustly in practice.Recent work shows how to make the online phase of practical asynchronous MPC robust [47].However, the preprocessing phase, which must be run by the servers prior to receiving input, is much harder to make robust in practice.To explain the problem we will focus on generating random input masks, which allow clients to easily contribute secret inputs to an MPC program.The goal is to produce a random secret sharing r t which satisfies the following: if no more than t of the N MPC server nodes are corrupted, r is uniformly random, unknown, and any t + 1 parties can reconstruct the same r.The standard way to generate such values is for all the servers to contribute shares they sample individually, which are then all combined to extract fully random values, even if some corrupt parties chose their inputs in a correlated way [11].This approach hinges on a protocol that can be used to verify that the individually chosen shares are chosen correctly.Verifiable Secret Sharing (VSS) [30], [40], [22] is a natural choice for this task.In particular, Asynchronous Complete Secret Sharing (ACSS) [54] provides all the robustness guarantees needed for the MPC application, since it guarantees not only that the secret inputs can be reconstructed if necessary, but also that each of the servers can receive its original share of the secret.However, existing ACSS protocols introduce a computation and communication overhead that is quadratic in the number of parties and cannot scale well beyond a small number of nodes.This motivates the design of an efficient, scalable ACSS protocol without compromising the optimal replication factor of 3t + 1 or the asynchronous communication setting.In targeting this threat model, we prefix the protocols designed in this paper with "hb" as a reference to the honey badger, a creature known for its resilience in harsh adversarial settings.A. Challenges and overview of our solution a) Good performance under worst case conditions: The asynchronous network setting is fundamentally challenging: unlike in synchrony, a protocol which waits to hear from all parties will stall indefinitely.Instead, we must proceed after hearing from only N -t of the parties, where t is a bound on the number of parties that can fail.Since crashed nodes are indistinguishable from slow nodes, it could be that t parties for which we waited are corrupted, and thus only N -2t correct parties received valid shares.To cope with asynchrony, the most closely related protocol, VSS-R [9], falls back to an inefficient backup mode with communication overhead that is quadratic in the number of servers, even after a brief period of desynchronization.Alternately, Patra et al. give AVSS protocols with linear communication overhead [53], but require weakening resilience (t < N/4).We remark, however, that many t < N/3, AVSS/AVCSS protocols (including ours) could improve their amortized bandwidth by a factor of O(N ) through the use of Packed Secret Sharing.Consequently, we focus on the t < N/3 setting, knowing that improvements here can also lead to improvements in more relaxed settings.b) Aggressive batching for large secrets: Motivated by our application of MPC preprocessing, we seek general efficiency but assume the amount of data that needs to be shared is large.We focus on the case where each single dealer needs to deal a large batch of secrets, such as for precomputation purposes.In doing so, we can amortize away

DOI
10.14722/ndss.2022.23120

Related papers

Communication Efficient Perfectly Secure VSS and MPC in Asynchronous Networks with Optimal Resilience.

Arpita Patra, Ashish Choudhary, Chitra Rangan

Abstract. Verifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols are carried out among n parties, where t out of n parties can be under the influence of a Byzantine (active) adversary, having unbounded computing power. It is well known that protocols for perfectly secure VSS and perfectly secure MPC exist in an asynchronous network iff n ≥ 4t+1. Hence, we call any perfectly secure VSS (MPC) protocol designed over an asynchronous network with n = 4t + 1 as optimally resilient VSS (MPC) protocol. A secret is d-shared among the parties if there exists a random degreed polynomial whose constant term is the secret and each honest party possesses a distinct point on the degree-d polynomial. Typically VSS is used as a primary tool to generate t-sharing of secret(s). In this paper, we present an optimally resilient, perfectly secure Asynchronous VSS (AVSS)

•Jan 1, 2010•0 citations

On the Power of Hybrid Networks in Multi-Party Computation

Arpita Patra, Divya Ravi

Perfectly-secure verifiable secret sharing (VSS) and multi-party computation (MPC) protocols in asynchronous network tolerate only at most one-fourth of corruption, while their counterparts in synchronous network sustain against at most one-third corruption. Moreover property-wise, synchronous protocols provide much stronger guarantees than the asynchronous counterparts. Taking note of the fact that asynchronous network is more realistic on one hand and on the other, synchrony of a network has positive impact on several aspects of distributed protocols including properties and fault-tolerance, we explore the power of hybrid networks that combines best of both the worlds by supporting a few synchronous rounds at the onset of a protocol execution, before turning to asynchronous mode. In hybrid networks, we investigate various feasibility questions pertaining to protocols giving guarantees attainable in synchronous and asynchronous networks. For the asynchronous protocols in hybrid networks, we hope to leverage the initial synchronous rounds to bridge the gap in the fault-tolerance with the synchronous protocols under minimal synchrony assumption. We ask the following fundamental question of both theoretical and practical importance: What is the minimum number of initial synchronous rounds necessary and sufficient in a hybrid network to construct asynchronous perfectly-secure VSS and MPC protocols with the fault-tolerance of synchronous protocols? On the positive note, we show that the answer is one for VSS which is clearly optimal. Notably no broadcast oracle is invoked in the synchronous round of our proposed VSS protocol. On the negative side, we prove that one synchronous round is not enough for MPC, putting MPC on a higher pedestal than VSS in terms of difficulty. For synchronous protocols in hybrid networks, we hope to save on the synchronous rounds leveraging conveniently the available asynchronous phase. We settle the question for VSS in the negative showing that three rounds that are known to be necessary (and sufficient) for VSS in synchronous networks, are also required in hybrid networks. VSS being a special case of MPC, the lower bound holds true for MPC. We match the lower bound with a three-round protocol. Notably, synchronous MPC with cryptographic security is known to be achievable in hybrid networks with one synchronous round.

IEEE Transactions on Information Theory•Apr 17, 2018•15 citations

Efficient Statistical Asynchronous Verifiable Secret Sharing and Multiparty Computation with Optimal Resilience.

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among n parties in the presence of a computationally unbounded active adversary, who can corrupt up to t parties. We assume that every two parties in the network are directly connected by a pairwise secure channel. In this paper, we present a new statistical AVSS protocol with optimal 5 resilience; i.e. with n = 3t + 1. Our protocol privately communicates

•Jan 1, 2009•6 citations

Secure Multi-Player Protocols: Fundamentals, Generality, and Efficiency

Serge Fehr

While classically cryptography is concerned with the problem of private communication among two entities, say players, in modern cryptography multi-player protocols play an important role.And among these, it is probably fair to say that secret sharing, and its stronger version verifiable secret sharing (VSS), as well as multi-party computation (MPC) belong to the most appealing and/or useful ones.The former two are basic tools to achieve better robustness of cryptographic schemes against malfunction or misuse by "decentralizing" the security from one single to a whole group of individuals (captured by the term threshold cryptography).The latter allows-at least in principle-to execute any collaboration among a group of players in a secure way that guarantees the correctness of the outcome but simultaneously respects the privacy of the participants.In this work, we study three aspects of secret sharing, VSS and MPC, which we denote by fundamentals, generality, and efficiency.By fundamentals we mean the quest for understanding why a protocol works and is secure in abstract (and hopefully simple) mathematical terms.By generality we mean generality with respect to the underlying mathematical structure, in other words, minimizing the mathematical axioms required to do some task.And efficiency of course deals with the improvement of protocols with respect to some meaningful complexity measure.We briefly summarize our main results.(1) We give a complete characterization of blackbox secret sharing in terms of simple algebraic conditions on the integer sharing coefficients, and we propose a black-box secret sharing scheme with minimal expansion factor.Note that, in contrast to the classical field-based secret sharing schemes, a black-box secret sharing scheme allows to share a secret sampled from an arbitrary Abelian group and requires only black-box access to the group operations and to random group elements.Such a scheme may be very useful in the construction of threshold cryptosystems based on groups with secret order (like RSA).(2) We show that without loss of efficiency, MPC can be based on arbitrary finite rings.This is in sharp contrast to the literature where essentially all MPC protocols require a much stronger mathematical structure, namely a field.Apart from its theoretical value, this can lead to efficiency improvements since it allows a greater freedom in the (mathematical) representation of the task that needs to be securely executed.(3) We propose a unified treatment of perfectly secure linear VSS and distributed commitments (a weaker version of the former), and we show that the security of such a scheme can be reduced to a linear algebra condition.The security of all known schemes follows as corollaries whose proofs are pure linear algebra arguments, in contrast v to some hybrid arguments used in the literature.(4) We construct a new unconditionally secure VSS scheme with minimized reconstruction complexity in the setting of a dishonest minority.This improves on the reconstruction complexity of the previously best known scheme without affecting the (asymptotic) complexity of the sharing phase.In the context of MPC with pre-processing, our scheme allows to improve the computation phase of earlier protocols without increasing the complexity of the pre-processing.(5) Finally, we consider commitment multiplication proofs, which allow to prove a multiplicative relation among three commitments, and which play a crucial role in computationally secure MPC.We study a non-interactive solution which works in a distributed-verifier setting and essentially consists of a few executions of Pedersen's VSS.We simplify and improve the protocol, and we point out a (previously overlooked) property which helps to construct non-interactive proofs of partial knowledge in this setting.This allows for instance to prove the knowledge of ℓ out of m given secrets, without revealing which ones.We also construct a noninteractive distributed-verifier proof of circuit satisfiability, which-in principle-allows to prove anything that can be proven without giving away the proof.

•Jan 1, 2003•2 citations

Broadcast (and Round) Efficient Verifiable Secret Sharing ∗

Juan A. Garay, Clint Givens, Rafail Ostrovsky +1 more

Verifiable secret sharing (VSS) is a fundamental cryptographic primitive, lying at the core of secure multi-party computation (MPC) and, as the distributed analogue of a commitment functionality, used in numerous applications. In this paper we focus on unconditionally secure VSS protocols with honest majority. In this setting it is typically assumed that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Because broadcast cannot be simulated on a point-to-point network when a third or more of the parties are corrupt, it is impossible to construct VSS (and more generally, MPC) protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of VSS, primarily in terms of round complexity. In this work we consider a refinement of the round complexity of VSS, by adding a measure we term broadcast complexity. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked as well. We construct a (linear) VSS protocol which uses the broadcast channel only twice in the sharing phase, while running in an overall constant number of rounds. 1

•Jan 1, 2013•0 citations

Round and Communication Efficient Unconditionally-secure MPC with t < n/3 in Partially Synchronous Network.

Ashish Choudhury, Arpita Patra, Divya Ravi

In this work, we study unconditionally-secure multi-party computation (MPC) tolerating \(t < n/3\) corruptions, where n is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with \(t<n/3\) requires a communication of \(\varOmega (n^5)\) field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires \(\mathcal {O}(n^2)\) communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.

•Jan 1, 2017•0 citations
Despite significant recent progress toward making multi-party computation (MPC) practical, no existing MPC library offers complete robustness-meaning guaranteed output delivery, including in the offline phase-in a network that even has intermittent delays.Importantly, several theoretical MPC constructions already ensure robustness in this setting.We observe that the key reason for this gap between theory and practice is the absence of efficient verifiable/complete secret sharing (VSS/CSS) constructions; existing CSS protocols either require a) challenging broadcast channels in practice or b) introducing computation and communication overhead that is at least quadratic in the number of players.This work presents hbACSS, a suite of optimal-resilience asynchronous complete secret sharing protocols that are (quasi)linear in both computation and communication overhead.Towards developing hbACSS, we develop hbPolyCommit, an efficient polynomial commitment scheme that is (quasi)linear (in the polynomial degree) in terms of computation and communication overhead without requiring a trusted setup.We implement our hbACSS protocols, extensively analyze their practicality, and observe that our protocols scale well with an increasing number of parties.In particular, we use hbACSS to generate MPC input masks: a useful primitive which had previously only been calculated nonrobustly in practice.Recent work shows how to make the online phase of practical asynchronous MPC robust [47].However, the preprocessing phase, which must be run by the servers prior to receiving input, is much harder to make robust in practice.To explain the problem we will focus on generating random input masks, which allow clients to easily contribute secret inputs to an MPC program.The goal is to produce a random secret sharing r t which satisfies the following: if no more than t of the N MPC server nodes are corrupted, r is uniformly random, unknown, and any t + 1 parties can reconstruct the same r.The standard way to generate such values is for all the servers to contribute shares they sample individually, which are then all combined to extract fully random values, even if some corrupt parties chose their inputs in a correlated way [11].This approach hinges on a protocol that can be used to verify that the individually chosen shares are chosen correctly.Verifiable Secret Sharing (VSS) [30], [40], [22] is a natural choice for this task.In particular, Asynchronous Complete Secret Sharing (ACSS) [54] provides all the robustness guarantees needed for the MPC application, since it guarantees not only that the secret inputs can be reconstructed if necessary, but also that each of the servers can receive its original share of the secret.However, existing ACSS protocols introduce a computation and communication overhead that is quadratic in the number of parties and cannot scale well beyond a small number of nodes.This motivates the design of an efficient, scalable ACSS protocol without compromising the optimal replication factor of 3t + 1 or the asynchronous communication setting.In targeting this threat model, we prefix the protocols designed in this paper with "hb" as a reference to the honey badger, a creature known for its resilience in harsh adversarial settings.A. Challenges and overview of our solution a) Good performance under worst case conditions: The asynchronous network setting is fundamentally challenging: unlike in synchrony, a protocol which waits to hear from all parties will stall indefinitely.Instead, we must proceed after hearing from only N -t of the parties, where t is a bound on the number of parties that can fail.Since crashed nodes are indistinguishable from slow nodes, it could be that t parties for which we waited are corrupted, and thus only N -2t correct parties received valid shares.To cope with asynchrony, the most closely related protocol, VSS-R [9], falls back to an inefficient backup mode with communication overhead that is quadratic in the number of servers, even after a brief period of desynchronization.Alternately, Patra et al. give AVSS protocols with linear communication overhead [53], but require weakening resilience (t < N/4).We remark, however, that many t < N/3, AVSS/AVCSS protocols (including ours) could improve their amortized bandwidth by a factor of O(N ) through the use of Packed Secret Sharing.Consequently, we focus on the t < N/3 setting, knowing that improvements here can also lead to improvements in more relaxed settings.b) Aggressive batching for large secrets: Motivated by our application of MPC preprocessing, we seek general efficiency but assume the amount of data that needs to be shared is large.We focus on the case where each single dealer needs to deal a large batch of secrets, such as for precomputation purposes.In doing so, we can amortize away
Abstract. Verifiable Secret Sharing (VSS) is a fundamental primitive used in many distributed cryptographic tasks, such as Multiparty Computation (MPC) and Byzantine Agreement (BA). It is a two phase (sharing, reconstruction) protocol. The VSS and MPC protocols are carried out among n parties, where t out of n parties can be under the influence of a Byzantine (active) adversary, having unbounded computing power. It is well known that protocols for perfectly secure VSS and perfectly secure MPC exist in an asynchronous network iff n ≥ 4t+1. Hence, we call any perfectly secure VSS (MPC) protocol designed over an asynchronous network with n = 4t + 1 as optimally resilient VSS (MPC) protocol. A secret is d-shared among the parties if there exists a random degreed polynomial whose constant term is the secret and each honest party possesses a distinct point on the degree-d polynomial. Typically VSS is used as a primary tool to generate t-sharing of secret(s). In this paper, we present an optimally resilient, perfectly secure Asynchronous VSS (AVSS)
Perfectly-secure verifiable secret sharing (VSS) and multi-party computation (MPC) protocols in asynchronous network tolerate only at most one-fourth of corruption, while their counterparts in synchronous network sustain against at most one-third corruption. Moreover property-wise, synchronous protocols provide much stronger guarantees than the asynchronous counterparts. Taking note of the fact that asynchronous network is more realistic on one hand and on the other, synchrony of a network has positive impact on several aspects of distributed protocols including properties and fault-tolerance, we explore the power of hybrid networks that combines best of both the worlds by supporting a few synchronous rounds at the onset of a protocol execution, before turning to asynchronous mode. In hybrid networks, we investigate various feasibility questions pertaining to protocols giving guarantees attainable in synchronous and asynchronous networks. For the asynchronous protocols in hybrid networks, we hope to leverage the initial synchronous rounds to bridge the gap in the fault-tolerance with the synchronous protocols under minimal synchrony assumption. We ask the following fundamental question of both theoretical and practical importance: What is the minimum number of initial synchronous rounds necessary and sufficient in a hybrid network to construct asynchronous perfectly-secure VSS and MPC protocols with the fault-tolerance of synchronous protocols? On the positive note, we show that the answer is one for VSS which is clearly optimal. Notably no broadcast oracle is invoked in the synchronous round of our proposed VSS protocol. On the negative side, we prove that one synchronous round is not enough for MPC, putting MPC on a higher pedestal than VSS in terms of difficulty. For synchronous protocols in hybrid networks, we hope to save on the synchronous rounds leveraging conveniently the available asynchronous phase. We settle the question for VSS in the negative showing that three rounds that are known to be necessary (and sufficient) for VSS in synchronous networks, are also required in hybrid networks. VSS being a special case of MPC, the lower bound holds true for MPC. We match the lower bound with a three-round protocol. Notably, synchronous MPC with cryptographic security is known to be achievable in hybrid networks with one synchronous round.
Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among n parties in the presence of a computationally unbounded active adversary, who can corrupt up to t parties. We assume that every two parties in the network are directly connected by a pairwise secure channel. In this paper, we present a new statistical AVSS protocol with optimal 5 resilience; i.e. with n = 3t + 1. Our protocol privately communicates
While classically cryptography is concerned with the problem of private communication among two entities, say players, in modern cryptography multi-player protocols play an important role.And among these, it is probably fair to say that secret sharing, and its stronger version verifiable secret sharing (VSS), as well as multi-party computation (MPC) belong to the most appealing and/or useful ones.The former two are basic tools to achieve better robustness of cryptographic schemes against malfunction or misuse by "decentralizing" the security from one single to a whole group of individuals (captured by the term threshold cryptography).The latter allows-at least in principle-to execute any collaboration among a group of players in a secure way that guarantees the correctness of the outcome but simultaneously respects the privacy of the participants.In this work, we study three aspects of secret sharing, VSS and MPC, which we denote by fundamentals, generality, and efficiency.By fundamentals we mean the quest for understanding why a protocol works and is secure in abstract (and hopefully simple) mathematical terms.By generality we mean generality with respect to the underlying mathematical structure, in other words, minimizing the mathematical axioms required to do some task.And efficiency of course deals with the improvement of protocols with respect to some meaningful complexity measure.We briefly summarize our main results.(1) We give a complete characterization of blackbox secret sharing in terms of simple algebraic conditions on the integer sharing coefficients, and we propose a black-box secret sharing scheme with minimal expansion factor.Note that, in contrast to the classical field-based secret sharing schemes, a black-box secret sharing scheme allows to share a secret sampled from an arbitrary Abelian group and requires only black-box access to the group operations and to random group elements.Such a scheme may be very useful in the construction of threshold cryptosystems based on groups with secret order (like RSA).(2) We show that without loss of efficiency, MPC can be based on arbitrary finite rings.This is in sharp contrast to the literature where essentially all MPC protocols require a much stronger mathematical structure, namely a field.Apart from its theoretical value, this can lead to efficiency improvements since it allows a greater freedom in the (mathematical) representation of the task that needs to be securely executed.(3) We propose a unified treatment of perfectly secure linear VSS and distributed commitments (a weaker version of the former), and we show that the security of such a scheme can be reduced to a linear algebra condition.The security of all known schemes follows as corollaries whose proofs are pure linear algebra arguments, in contrast v to some hybrid arguments used in the literature.(4) We construct a new unconditionally secure VSS scheme with minimized reconstruction complexity in the setting of a dishonest minority.This improves on the reconstruction complexity of the previously best known scheme without affecting the (asymptotic) complexity of the sharing phase.In the context of MPC with pre-processing, our scheme allows to improve the computation phase of earlier protocols without increasing the complexity of the pre-processing.(5) Finally, we consider commitment multiplication proofs, which allow to prove a multiplicative relation among three commitments, and which play a crucial role in computationally secure MPC.We study a non-interactive solution which works in a distributed-verifier setting and essentially consists of a few executions of Pedersen's VSS.We simplify and improve the protocol, and we point out a (previously overlooked) property which helps to construct non-interactive proofs of partial knowledge in this setting.This allows for instance to prove the knowledge of ℓ out of m given secrets, without revealing which ones.We also construct a noninteractive distributed-verifier proof of circuit satisfiability, which-in principle-allows to prove anything that can be proven without giving away the proof.
Verifiable secret sharing (VSS) is a fundamental cryptographic primitive, lying at the core of secure multi-party computation (MPC) and, as the distributed analogue of a commitment functionality, used in numerous applications. In this paper we focus on unconditionally secure VSS protocols with honest majority. In this setting it is typically assumed that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Because broadcast cannot be simulated on a point-to-point network when a third or more of the parties are corrupt, it is impossible to construct VSS (and more generally, MPC) protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of VSS, primarily in terms of round complexity. In this work we consider a refinement of the round complexity of VSS, by adding a measure we term broadcast complexity. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked as well. We construct a (linear) VSS protocol which uses the broadcast channel only twice in the sharing phase, while running in an overall constant number of rounds. 1
In this work, we study unconditionally-secure multi-party computation (MPC) tolerating t<n/3t < n/3t<n/3 corruptions, where n is the total number of parties involved. In this setting, it is well known that if the underlying network is completely asynchronous, then one can achieve only statistical security; moreover it is impossible to ensure input provision and consider inputs of all the honest parties. The best known statistically-secure asynchronous MPC (AMPC) with t<n/3t<n/3t<n/3 requires a communication of Ω(n5)\varOmega (n^5)Ω(n5) field elements per multiplication. We consider a partially synchronous setting, where the parties are assumed to be globally synchronized initially for few rounds and then the network becomes completely asynchronous. In such a setting, we present a MPC protocol, which requires O(n2)\mathcal {O}(n^2)O(n2) communication per multiplication while ensuring input provision. Our MPC protocol relies on a new four round, communication efficient statistical verifiable secret-sharing (VSS) protocol with broadcast communication complexity independent of the number of secret-shared values.