Practical Schnorr Threshold Signatures Without the Algebraic Group Model

Hien Chu; Paul Gerhart; Tim Ruffing; Dominique Schröder

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in CRYPTO 2023
DOI: 10.1007/978-3-031-38557-5_24
Keywords: Threshold Signatures Schnorr Signatures FROST
Contact author(s): hien chu @ fau de
paul gerhart @ fau de
crypto @ timruffing de
dominique schroeder @ fau de
History: 2023-08-22: revised; 2023-06-09: received; See all versions
Short URL: https://ia.cr/2023/899
License: CC BY

BibTeX

@misc{cryptoeprint:2023/899,
      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},
      url = {https://eprint.iacr.org/2023/899}
}