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.
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.
Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. The optimal resilience for perfectly-secure MPC in synchronous and asynchronous networks is t < n/3 and t < n/4 respectively, where n is the number of parties and t is the number of corruptions. A natural question is whether there exists a protocol tolerating ts < n/3 corruptions in a synchronous network and ta < n/4 corruptions in an asynchronous network. We design such a protocol, if 3ts + ta < n. For our protocol, we present a perfectly-secure Byzantine agreement (BA) protocol, tolerating t < n/3 corruptions in any network and a perfectly-secure verifiable secret-sharing (VSS) protocol, tolerating ts and ta corruptions in a synchronous and an asynchronous network respectively.
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 Ω(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) 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.
Securemulti-party computation(MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set ofnmutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC withinformation-theoreticsecurity (also calledunconditional security) provides the strongest security guarantees and remains secure even againstcomputationally unboundedadversaries.Perfectly-secureMPC protocols are a class of information-theoretically secure MPC protocols, which provide all the security guarantees in anerror-freefashion. The focus of this work is perfectly-secure MPC. Known protocols are designedassumingeither asynchronousorasynchronouscommunication network. It is well known that perfectly-securesynchronousMPC is possible as long as the adversary can corrupt anyts<n/3parties. On the other hand, perfectly-secureasynchronousMPC protocols can tolerate up tota<n/4corrupt parties. A natural question is does there exist asingleMPC protocol for the setting where the parties arenot awareof the exact network type and which can tolerate up tots<n/3corruptions in a synchronous network and up tota<n/4corruptions in anasynchronousnetwork. We design such abest-of-both-worldsperfectly-secure MPC protocol, provided3ts+ta<nholds. For designing our protocol, we design two important building blocks which are of independent interest. The first building block is a best-of-both-worldsByzantine agreement(BA) protocol toleratingt<n/3corruptions which remains securebothin a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worldsverifiable secret-sharing(VSS) protocol, which can tolerate up totsandtacorruptions in asynchronousand in anasynchronousnetwork respectively.
Abstract. Secure multiparty computation (MPC) allows a set of parties to securely evaluate any agreed function of their inputs, even when up to t of the n parties are faulty. Protocols for synchronous networks (where every sent message is assumed to arrive within a constant time) tolerate up to t < n/2 faulty parties, whereas in the more realistic asynchronous setting (with no a priory information on maximal message delay) only security against t < n/3 is possible. Note that even asynchronous Byzantine agreement requires t < n/3. In this paper, we are interested in the minimal synchronicity assumption for achieving security against t < n/2. It turns out that the bottleneck of asynchronous MPC is the distribution of the inputs: Once the inputs are correctly distributed, any deterministic function can be computed over a fully asynchronous network with t < n/2. Furthermore, we show that the inputs can be verifiably distributed with t < n/2, if a single round of synchronous broadcast is available. Composing the above, we obtain the first MPC protocol that achieves security against t < n/2 without assuming a fully synchronous network. Actually our protocol guarantees security against any faulty minority in an almost asynchronous network, i.e. in a network with one single round of synchronous broadcast (followed by a fully asynchronous communication). Furthermore our protocol takes inputs of all parties (in a fully asynchronous network only inputs of n−t parties can be guaranteed), and so achieves everything that is possible in synchronous networks (but impossible in fully asynchronous networks) at the price of just one synchronous broadcast round. As tools for our protocol we introduce the notions of almost non-interactive verifiable secret-sharing and almost non-interactive zero-knowledge proof of knowledge, which are of independent interest as they can serve as efficient replacements for fully non-interactive verifiable secret-sharing and fully non-interactive zero-knowledge proof of knowledge.
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)
Broadcast and verifiable secret sharing (VSS) are central building blocks for secure multi-party computation. These protocols are required to be resilient against a Byzantine adversary who controls at most t out of the n parties running the protocol. In this dissertation, we consider the design of fault-tolerant protocols for broadcast and verifiable secret sharing with stronger security guarantees and improved round complexity. Broadcast allows a party to send the same message to all parties, and all parties are assured they have received identical messages. Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. We address two important issues related to broadcast: (1) Almost all existing protocols do not distinguish between corrupted parties (who do not follow the protocol) and honest parties whose secret (signing) keys have been compromised (but who continue to behave honestly); (2) all existing protocols for broadcast are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. We propose new security models that capture these issues, and present tight feasibility and impossibility results. In the problem of verifiable secret sharing, there is a designated player who shares a secret during an initial sharing phase such that the secret is hidden from an adversary that corrupts at most t parties. In a subsequent reconstruction phase of the protocol, a unique secret, well-defined by the view of honest players in the sharing phase, is reconstructed. The round complexity of VSS protocols is a very important metric of their efficiency. We show two improvements regarding the round complexity of information-theoretic VSS. First, we construct an efficient perfectly secure VSS protocol tolerating t < n/3 corrupted parties that is simultaneously optimal in both the number of rounds and the number of invocations of broadcast. Second, we construct a statistically secure VSS protocol tolerating t < n/2 corrupted parties that has optimal round complexity, and an efficient statistical VSS protocol tolerating t < n/2 corrupted parties that requires one additional round.