Paper 2024/280

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

Renas Bacho, CISPA Helmholtz Center for Information Security, Saarland University
Julian Loss, CISPA Helmholtz Center for Information Security
Gilad Stern, Tel Aviv University
Benedikt Wagner, CISPA Helmholtz Center for Information Security, Saarland University

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 $O(1)$ rounds 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 $t_r\geq 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.

Available format(s)
Cryptographic protocols
Publication info
Threshold SignaturesSchnorr SignaturesAdaptive SecurityRobustnessHigh-ThresholdAsynchronous Network
Contact author(s)
renas bacho @ cispa de
loss @ cispa de
gilad stern @ mail huji ac il
benedikt wagner @ cispa de
2024-02-23: approved
2024-02-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Renas Bacho and Julian Loss and Gilad Stern and Benedikt Wagner},
      title = {HARTS: High-Threshold, Adaptively Secure, and Robust Threshold Schnorr Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2024/280},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.