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 Statistical Asynchronous Verifiable Secret Sharing and Multiparty Computation with Optimal Resilience.

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

Published Jan 1, 2009• 6 citations
OpenAlex

Abstract

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

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

Asynchronous Computational VSS with Reduced Communication Complexity.

Michael Backes A, Amit Jyoti Datta, Aniket Kate

Verifiable secret sharing (VSS) is a vital primitive in secure distributed computing. It allows an untrusted dealer to verifiably share a secret among n parties in the presence of an adversary controlling at most t of them. VSS in the synchronous communication model has received tremendous attention in the cryptographic research community. Nevertheless, recent interest in deploying secure distributed computing over the Internet requires going beyond the synchronous communication model and thoroughly investigating VSS in the asynchronous communication model. In this work, we consider the communication complexity of asynchronous VSS in the computational setting for the optimal resilience of n = 3t + 1. The best known asynchronous VSS protocol by Cachin et al. has O(n 2) message complexity and O(κn 3) communication complexity, where κ is a security parameter corresponding to the size of the secret. We close the linear complexity gap between these two measures for asynchronous VSS by presenting two protocols with O(n 2) message complexity and O(κn 2) communication complexity. Our first protocol satisfies the standard VSS definition, and can be used in stand-alone VSS scenarios as well as in applications such as Byzantine agreement. Our second and more intricate protocol satisfies a stronger VSS definition, and is useful in all VSS applications including multiparty computation and threshold cryptography.

•Jan 1, 2012•2 citations

Perfectly-Secure Synchronous MPC with Asynchronous Fallback Guarantees

Ananya Appan, Anirudh Chandramouli, Ashish Choudhury

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.

arXiv:2201.12194•ACM Symposium on Principles of Distributed Computing (PODC)•Jul 20, 2022•20 citations

Broadcast and verifiable secret sharing: new security models and round optimal constructions

Jonathan I. Katz, Ranjit Kumaresan

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.

•Jan 1, 2012•1 citation

Network-Agnostic Verifiable Secret Sharing With Cryptographic Security

Nidhish Bhimrajka, Ashish Choudhury, Supreeth Varadarajan

Verifiable Secret-Sharing(VSS) is a fundamental primitive in secure distributed computing that allows a designated dealer to share a secret amongnparties in the presence of an adversary controlling at mosttof them. We study VSS in the presence ofcomputationally-boundedadversaries. Known VSS protocols tolerate up totstaperfectsecurity (Appan et al. IEEE IT 2023) where the threshold conditions arenotknown to be optimal or withstatistical security(Appan et al. TCC 2023) where the threshold conditions are optimal, but the parties need to performexponentialamount of computation and communication. Using our VSS protocol, we design a secureMulti-Party Computation(MPC) protocol in theplain Public Key Infrastructure (PKI) model, i.e., without assuming an expensive trusted setup. Although our proposed MPC protocol incurs higher communication complexity than state-of-the-art network-agnostic MPC protocols, it motivates alternative directions for designingcomputationally inexpensiveMPC protocols based on a plain PKI setup, which has not been explored in the domain of computationally secure networkagnostic MPC and offers valuable insights into designing it.

IEEE Transactions on Information Theory•Dec 11, 2025•0 citations

Brief Announcement: Optimally-Resilient Unconditionally-Secure Asynchronous Multi-Party Computation Revisited

Ashish Choudhury

In this paper, we present an optimally-resilient, unconditionally-secure asynchronous multi-party computation (AMPC) protocol for n parties, tolerating a computationally unbounded adversary, capable of corrupting up to t < n/3 parties. Our protocol needs a communication of 𝒪(n⁴) field elements per multiplication gate. This is to be compared with previous best AMPC protocol (Patra et al, ICITS 2009) in the same setting, which needs a communication of 𝒪(n⁵) field elements per multiplication gate. To design our protocol, we present a simple and highly efficient asynchronous verifiable secret-sharing (AVSS) protocol, which is of independent interest.

Leibniz international proceedings in informatics•Jan 1, 2020•0 citations
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
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)
Verifiable secret sharing (VSS) is a vital primitive in secure distributed computing. It allows an untrusted dealer to verifiably share a secret among n parties in the presence of an adversary controlling at most t of them. VSS in the synchronous communication model has received tremendous attention in the cryptographic research community. Nevertheless, recent interest in deploying secure distributed computing over the Internet requires going beyond the synchronous communication model and thoroughly investigating VSS in the asynchronous communication model. In this work, we consider the communication complexity of asynchronous VSS in the computational setting for the optimal resilience of n = 3t + 1. The best known asynchronous VSS protocol by Cachin et al. has O(n 2) message complexity and O(κn 3) communication complexity, where κ is a security parameter corresponding to the size of the secret. We close the linear complexity gap between these two measures for asynchronous VSS by presenting two protocols with O(n 2) message complexity and O(κn 2) communication complexity. Our first protocol satisfies the standard VSS definition, and can be used in stand-alone VSS scenarios as well as in applications such as Byzantine agreement. Our second and more intricate protocol satisfies a stronger VSS definition, and is useful in all VSS applications including multiparty computation and threshold cryptography.
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.
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.
Verifiable Secret-Sharing(VSS) is a fundamental primitive in secure distributed computing that allows a designated dealer to share a secret amongnparties in the presence of an adversary controlling at mosttof them. We study VSS in the presence ofcomputationally-boundedadversaries. Known VSS protocols tolerate up totstaperfectsecurity (Appan et al. IEEE IT 2023) where the threshold conditions arenotknown to be optimal or withstatistical security(Appan et al. TCC 2023) where the threshold conditions are optimal, but the parties need to performexponentialamount of computation and communication. Using our VSS protocol, we design a secureMulti-Party Computation(MPC) protocol in theplain Public Key Infrastructure (PKI) model, i.e., without assuming an expensive trusted setup. Although our proposed MPC protocol incurs higher communication complexity than state-of-the-art network-agnostic MPC protocols, it motivates alternative directions for designingcomputationally inexpensiveMPC protocols based on a plain PKI setup, which has not been explored in the domain of computationally secure networkagnostic MPC and offers valuable insights into designing it.
In this paper, we present an optimally-resilient, unconditionally-secure asynchronous multi-party computation (AMPC) protocol for n parties, tolerating a computationally unbounded adversary, capable of corrupting up to t < n/3 parties. Our protocol needs a communication of 𝒪(n⁴) field elements per multiplication gate. This is to be compared with previous best AMPC protocol (Patra et al, ICITS 2009) in the same setting, which needs a communication of 𝒪(n⁵) field elements per multiplication gate. To design our protocol, we present a simple and highly efficient asynchronous verifiable secret-sharing (AVSS) protocol, which is of independent interest.