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.
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.
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.
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
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
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.
In this work, we study perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries. Known protocols in a synchronous network are secure against Q(3) adversary structures, while in an asynchronous network, known protocols are secure against Q(4) adversary structures. A natural question is whether there exists a single protocol which remains secure against Q(3) and Q(4) adversary structures in a synchronous and in an asynchronous network respectively, where the parties are not aware of the network type. We design the first such best-of-both-worlds protocol against general adversaries. Our result generalizes the result of Appan, Chandramouli and Choudhury (PODC 2022), which presents a best-of-both-worlds perfectly-secure protocol against threshold adversaries. To design our protocol, we present two important building blocks which are of independent interest. The first building block is a best-of-both-worlds perfectly-secure Byzantine agreement (BA) protocol for Q(3) adversary structures, which remains secure both in a synchronous, as well as an asynchronous network. The second building block is a best-of-both-worlds perfectly-secure verifiable secret-sharing (VSS) protocol, which remains secure against Q(3) and Q(4) adversary structures in a synchronous network and an asynchronous network respectively.