International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions

Authors:
Francois Garillot , Novi/Facebook
Yashvanth Kondi , Northeastern University
Payman Mohassel , Facebook
Valeria Nikolaenko , Novi/Facebook
Download:
Search ePrint
Search Google
Conference: CRYPTO 2021
Abstract: 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. A proof per our scheme requires only a small constant number of exponentiations.
Video from CRYPTO 2021
BibTeX
@inproceedings{crypto-2021-31271,
  title={Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions},
  publisher={Springer-Verlag},
  author={Francois Garillot and Yashvanth Kondi and Payman Mohassel and Valeria Nikolaenko},
  year=2021
}