Paper 2021/1055

Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions

François Garillot, Yashvanth Kondi, Payman Mohassel, and Valeria Nikolaenko


Schnorr's signature scheme permits an elegant threshold signing protocol due to its linear signing equation. However each new signature consumes fresh randomness, which can be a major attack vector in practice. Sources of randomness in deployments are frequently either unreliable, or require state continuity, i.e. reliable fresh state resilient to rollbacks. State continuity is a notoriously difficult guarantee to achieve in practice, due to system crashes caused by software errors, malicious actors, or power supply interruptions (Parno et al., S&P '11). This is a non-issue for Schnorr variants such as EdDSA, which is specified to derive nonces deterministically as a function of the message and the secret key. However, it is challenging to translate these benefits to the threshold setting, specifically to construct a threshold Schnorr scheme where signing neither requires parties to consume fresh randomness nor update long-term secret state. In this work, we construct a dishonest majority threshold Schnorr protocol that enables such stateless deterministic nonce derivation using standardized block ciphers. Our core technical ingredients are new tools for the zero-knowledge from garbled circuits (ZKGC) paradigm to aid in verifying correct nonce derivation: - A mechanism based on UC Commitments that allows a prover to commit once to a witness, and prove an unbounded number of statements online with only cheap symmetric key operations. - A garbling gadget to translate intermediate garbled circuit wire labels to arithmetic encodings. Our scheme prioritizes computation cost, with each proof requiring only a small constant number of exponentiations.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2021
garbled circuitsoblivious transferzero-knowledgethreshold signatures
Contact author(s)
ykondi @ ccs neu edu
francois @ garillot net
payman @ fb com
valerini @ fb com
2021-08-16: received
Short URL
Creative Commons Attribution


      author = {François Garillot and Yashvanth Kondi and Payman Mohassel and Valeria Nikolaenko},
      title = {Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1055},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.