Proactive secret sharing (PSS) schemes are designed for settings where long-term con-dentiality of secrets has to be guaranteed, specically, when all participating parties may eventually be corrupted. PSS schemes periodically refresh secrets and reset corrupted parties to an uncorrupted state; in PSS the corruption threshold t is replaced with a corruption rate which cannot be violated. In dynamic proactive secret sharing (DPSS) the number of parties can vary during the course of execution. DPSS is ideal when the set of participating parties changes over the lifetime of the secret or where removal of parties is necessary if they become severely corrupted. This paper presents the rst DPSS schemes with optimal amortized, O(1), per-secret communication compared to O(n4) or exp(n) in number of parties, n, required by existing schemes. We present perfectly and statistically secure schemes with near-optimal threshold in each case. We also describe how to construct a communication-ecient dynamic proactively-secure multiparty computation (DPMPC) protocol which achieves the same thresholds.
Proactive secret sharing (PSS) schemes are designed for settings where long-term con-dentiality of secrets has to be guaranteed, specically, when all participating parties may eventually be corrupted. PSS schemes periodically refresh secrets and reset corrupted parties to an uncorrupted state; in PSS the corruption threshold t is replaced with a corruption rate which cannot be violated. In dynamic proactive secret sharing (DPSS) the number of parties can vary during the course of execution. DPSS is ideal when the set of participating parties changes over the lifetime of the secret or where removal of parties is necessary if they become severely corrupted. This paper presents the rst DPSS schemes with optimal amortized, O(1), per-secret communication compared to O(n4) or exp(n) in number of parties, n, required by existing schemes. We present perfectly and statistically secure schemes with near-optimal threshold in each case. We also describe how to construct a communication-ecient dynamic proactively-secure multiparty computation (DPMPC) protocol which achieves the same thresholds.
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 a t-out-of-n robust secret sharing scheme, a secret message is shared among n parties who can reconstruct the message by combining their shares. An adversary can adaptively corrupt up to t of the parties, get their shares, and modify them arbitrarily. The scheme should satisfy privacy, meaning that the adversary cannot learn anything about the shared message, and robustness, meaning that the adversary cannot cause the reconstruction procedure to output an incorrect message. Such schemes are only possible in the case of an honest majority, and here we focus on unconditional security in the maximal corruption setting where n = 2t+ 1. In this scenario, to share an m-bit message with a reconstruction failure probability of at most 2−k, a known lower-bound shows that the share size must be at least m + k bits. On the other hand, all prior constructions have share size that scales linearly with the number of parties n, and the prior state-of-the-art scheme due to Cevallos et al. (EUROCRYPT ’12) achieves m+ Õ(k + n). In this work, we construct the first robust secret sharing scheme in the maximal corruption setting with n = 2t+ 1, that avoids the linear dependence between share size and the number of
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
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
An error decodable secret-sharing scheme is a secret-sharing scheme with the additional property that the secret can be recovered from the set of all shares, even after a coalition of participants corrupts the shares they possess. In this paper, schemes that can tolerate corruption by sets of participants belonging to a monotone coalition structure are considered. This coalition structure may be unrelated to the authorised sets of the secret-sharing scheme. This is generalisation of both a related notion studied in the context of multiparty computation, and the well-known error-correction properties of threshold schemes based on Reed-Solomon codes. Necessary and sufficient conditions for the existence of such schemes are deduced, and methods for reducing the storage requirements of a technique of Kurosawa for constructing error-decodable secret-sharing schemes with efficient decoding algorithms are demonstrated. In addition, the connection between one-round perfectly secure message transmission (PSMT) schemes with general adversary structures and secret-sharing schemes is explored. We prove a theorem that explicitly shows the relation between these structures. In particular, an error decodable secret-sharing scheme yields a one-round PSMT, but the converse does not hold. Furthermore, we are able to show that some well-known results concerning one-round PSMT follow from known results on secret-sharing schemes. These connections are exploited to investigate factors affecting the performance of one-round PSMT schemes such as the number of channels required, the communication overhead, and the efficiency of message recovery.
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)