Paper 2022/619

Breaking the $t< n/3$ Consensus Bound: Asynchronous Dynamic Proactive Secret Sharing under Honest Majority

Abstract

A proactive secret sharing scheme (PSS), expressed in the dynamic-membership setting, enables a committee of n holders of secret-shares, dubbed as players, to securely hand-over new shares of the same secret to a new committee. We dub such a sub-protocol as a Refresh. All existing PSS under an honest majority, require the use of a broadcast (BC) in each refresh. BC is costly to implement, and its security relies on timing assumptions on the network. So the privacy of the secret and/or its guaranteed delivery, either depend on network assumptions, or, on the reliability of a public ledger. By contrast, PSS over asynchronous channels do not have these constraints. However, all of them (but one, with exponential complexity) use asynchronous verifiable secret sharing (AVSS) and consensus (MVBA and/or ACS), which are impossible under asynchrony beyond t<n/3 corruptions, whatever the setup. We present a PSS, named asynchronous-proactive secret sharing (APSS), which is the first PSS under honest majority with guaranteed output delivery in a completely asynchronous network. More generally, APSS allows any flexible threshold $t<n$, such that privacy and correctness are guaranteed up to t corruptions, and liveness as soon as $t+1$ players behave honestly. Correctness can be lifted to any number of corruptions, provided a linearly homomorphic commitment scheme. Moreover, each refresh completes at the record speed of $2\delta$, where $\delta$ is the actual message delivery delay. APSS demonstrates that proactive refreshes are possible as long as players of the initial committee only, have a common view on a set of (publicly committed or encrypted) shares. Despite not providing consensus on a unique set of shares, APSS surprisingly enables the opening of any linear map over secrets { non-interactively, without consensus }. This, in turn, applies to threshold signing, decryption and randomness generation. APSS can also be directly integrated into the asynchronous Schnorr threshold signing scheme "Roast" [CCS'22]. Of independent interest, we: - provide the first UC formalization (and proof) of proactive AVSS, furthermore for arbitrary thresholds; - provide additional mechanisms enabling players of a committee to start a refresh then erase their old shares, synchronously up to $\delta$ from each other; - improve by 50x the verification speed of the NIZKs of encrypted re-sharing of [Cascudo et al, Asiacrypt'22], by using novel optimizations of batch Schnorr proofs of knowledge. We demonstrate efficiency of APSS with an implementation which uses this optimization as baseline.

Note: Change log w.r.t. Version 3 of 2022-10-19: (a) NIZKs of resharings with 50x faster verification than [Cascudo et al, Asiacrypt'22], (b) interactive scheduling mechanism enabling to remove the synchrony assumption at the end of epochs, (c) other complexity improvements.