Paper 2023/427

SPRINT: High-Throughput Robust Distributed Schnorr Signatures

Fabrice Benhamouda, Algorand Foundation
Shai Halevi, Algorand Foundation
Hugo Krawczyk, Algorand Foundation
Yiping Ma, University of Pennsylvania
Tal Rabin, University of Pennsylvania

We describe high-throughput threshold protocols with guaranteed output delivery for generating Schnorr-type signatures. The protocols run a single message-independent interactive ephemeral randomness generation procedure (e.g., DKG) followed by a \emph{non-interactive} multi-message signature generation procedure. The protocols offer significant increase in throughput already for as few as ten parties while remaining highly-efficient for many hundreds of parties with thousands of signatures generated per minute (and over 10,000 in normal optimistic case). These protocols extend seamlessly to the dynamic/proactive setting, where each run of the protocol uses a new committee, and they support sub-sampling the committees from among an effectively unbounded number of nodes. The protocols work over a broadcast channel in both synchronous and asynchronous networks. The combination of these features makes our protocols a good match for implementing a signature service over an (asynchronous) public blockchain with many validators, where guaranteed output delivery is an absolute must. In that setting, there is a system-wide public key, where the corresponding secret signature key is distributed among the validators. Clients can submit messages (under suitable controls, e.g. smart contracts), and authorized messages are signed relative to the global public key. Asymptotically, when running with committees of $n$ parties, our protocols can generate $\Omega(n^2)$ signatures per run, while providing resilience against $\Omega(n)$ corrupted nodes, and using broadcast bandwidth of only $O(n^2)$ group elements and scalars. For example, we can sign about $n^2/16$ messages using just under $2n^2$ total bandwidth while supporting resilience against $n/4$ corrupted parties, or sign $n^2/8$ messages using just over $2n^2$ total bandwidth with resilience against $n/5$ corrupted parties. We prove security of our protocols by reduction to the hardness of the discrete logarithm problem in the random-oracle model.

Available format(s)
Cryptographic protocols
Publication info
Shnorr signaturesThreshold protocolAmortization
Contact author(s)
fbenhamo102 @ gmail com
shaih @ alum mit edu
hugokraw @ gmail com
yipingma @ seas upenn edu
talr @ seas upenn edu
2023-04-06: last of 2 revisions
2023-03-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fabrice Benhamouda and Shai Halevi and Hugo Krawczyk and Yiping Ma and Tal Rabin},
      title = {SPRINT: High-Throughput Robust Distributed Schnorr Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2023/427},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.