HARTS: High-Threshold, Adaptively Secure, and Robust Threshold Schnorr Signatures

Summary

Threshold variants of the Schnorr signature scheme have recently been at the center of attention due to their applications to Bitcoin, Ethereum, and other cryptocurrencies. However, existing constructions for threshold Schnorr signatures among a set of n parties with corruption threshold t_c suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) cubic or higher communication cost to generate a single signature, (iii) strong synchrony assumptions on the network, or (iv) t_c+1 are sufficient to generate a signature, i.e., the corruption threshold of the scheme equals its reconstruction threshold. Especially (iv) turns out to be a severe limitation for many asynchronous real-world applications where t_c < n/3 is necessary to maintain liveness, but a higher signing threshold of n-t_c is needed. A recent scheme, ROAST, proposed by Ruffing et al. (ACM CCS `22) addresses (iii) and (iv), but still falls short of obtaining subcubic complexity and adaptive security. In this work, we present HARTS, the first threshold Schnorr signature scheme to incorporate all these desiderata. More concretely: - HARTS is adaptively secure and remains fully secure and operational even under asynchronous network conditions in the presence of up to t_c < n/3 malicious parties. This is optimal. - HARTS outputs a Schnorr signature of size lambda with a near-optimal amortized communication cost of O(lambda n^2 log n) bits and a single online round per signature. - HARTS is a high-threshold scheme: no fewer than t_r+1 signature shares can be combined to yield a full signature, where any t_r in [t_c,n-t_c) is supported. This especially covers the case t_r >= 2n/3 > 2t_c. This is optimal. We prove our result in a modular fashion in the algebraic group model. At the core of our construction, we design a new simple and adaptively secure high-threshold AVSS scheme which may be of independent interest.