Paper 2023/445

Fully Adaptive Schnorr Threshold Signatures

Elizabeth Crites, University of Edinburgh
Chelsea Komlo, University of Waterloo, Zcash Foundation
Mary Maller, Ethereum Foundation, PQShield
Abstract

We prove adaptive security of a simple three-round threshold Schnorr signature scheme, which we call Sparkle. The standard notion of security for threshold signatures considers a static adversary – one who must declare which parties are corrupt at the beginning of the protocol. The stronger adaptive adversary can at any time corrupt parties and learn their state. This notion is natural and practical, yet not proven to be met by most schemes in the literature. In this paper, we demonstrate that Sparkle achieves several levels of security based on different corruption models and assumptions. To begin with, Sparkle is statically secure under minimal assumptions: the discrete logarithm assumption (DL) and the random oracle model (ROM). If an adaptive adversary corrupts fewer than t/2 out of a threshold of t + 1 signers, then Sparkle is adaptively secure under a weaker variant of the one-more discrete logarithm assumption (AOMDL) in the ROM. Finally, we prove that Sparkle achieves full adaptive security, with a corruption threshold of t, under AOMDL in the algebraic group model (AGM) with random oracles. Importantly, we show adaptive security without requiring secure erasures. Ours is the first proof achieving full adaptive security without exponential tightness loss for any threshold Schnorr signature scheme; moreover, the reduction is tight.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
threshold signaturesadaptive security
Contact author(s)
ecrites @ ed ac uk
ckomlo @ uwaterloo ca
mary maller @ ethereum org
History
2023-03-27: approved
2023-03-27: received
See all versions
Short URL
https://ia.cr/2023/445
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/445,
      author = {Elizabeth Crites and Chelsea Komlo and Mary Maller},
      title = {Fully Adaptive Schnorr Threshold Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2023/445},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/445}},
      url = {https://eprint.iacr.org/2023/445}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.