Paper 2023/899

Practical Schnorr Threshold Signatures Without the Algebraic Group Model

Hien Chu, Friedrich-Alexander-Universität Erlangen-Nürnberg
Paul Gerhart, Friedrich-Alexander-Universität Erlangen-Nürnberg
Tim Ruffing, Blockstream Research
Dominique Schröder, Friedrich-Alexander-Universität Erlangen-Nürnberg

Threshold signatures are digital signature schemes in which a set of $n$ signers specify a threshold $t$ such that any subset of size $t$ is authorized to produce signatures on behalf of the group. There has recently been a renewed interest in this primitive, largely driven by the need to secure highly valuable signing keys, e.g., DNSSEC keys or keys protecting digital wallets in the cryptocurrency ecosystem. Of special interest is FROST, a practical Schnorr threshold signature scheme, which is currently undergoing standardization in the IETF and whose security was recently analyzed at CRYPTO'22. We continue this line of research by focusing on FROST's unforgeability combined with a practical distributed key generation (DKG) algorithm. Existing proofs of this setup either use non-standard heuristics, idealized group models like the AGM, or idealized key generation. Moreover, existing proofs do not consider all practical relevant optimizations that have been proposed. We close this gap between theory and practice by presenting the Schnorr threshold signature scheme Olaf, which combines the most efficient known FROST variant FROST3 with a variant of Pedersen's DKG protocol (as commonly used for FROST), and prove its unforgeability. Our proof relies on the AOMDL assumption (a weaker and falsifiable variant of the OMDL assumption) and, like proofs of regular Schnorr signatures, on the random oracle model.

Note: Fixed typos.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in CRYPTO 2023
Threshold SignaturesSchnorr SignaturesFROST
Contact author(s)
hien chu @ fau de
paul gerhart @ fau de
crypto @ timruffing de
dominique schroeder @ fau de
2023-08-22: revised
2023-06-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Hien Chu and Paul Gerhart and Tim Ruffing and Dominique Schröder},
      title = {Practical Schnorr Threshold Signatures Without the Algebraic Group Model},
      howpublished = {Cryptology ePrint Archive, Paper 2023/899},
      year = {2023},
      doi = {10.1007/978-3-031-38557-5_24},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.