International Association for Cryptologic Research

International Association
for Cryptologic Research


Fully Adaptive Schnorr Threshold Signatures

Elizabeth Crites , University of Edinburgh
Chelsea Komlo , University of Waterloo & Zcash Foundation
Mary Maller , Ethereum Foundation & PQShield
DOI: 10.1007/978-3-031-38557-5_22 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Award: Best Early Career Paper
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.
  title={Fully Adaptive Schnorr Threshold Signatures},
  author={Elizabeth Crites and Chelsea Komlo and Mary Maller},