hbACSS: How to Robustly Share Many Secrets
Thomas Yurek, Licheng Luo, Jaiden Fairoze, Aniket Kate, Andrew K. Miller · 2022
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