Cryptology ePrint Archive: Report 2021/1055

Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions

Fran├žois Garillot and Yashvanth Kondi and Payman Mohassel and Valeria Nikolaenko

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.

Our scheme prioritizes computation cost, with each proof requiring only a small constant number of exponentiations.

Category / Keywords: cryptographic protocols / garbled circuits, oblivious transfer, zero-knowledge, threshold signatures

Original Publication (with major differences): IACR-CRYPTO-2021

Date: received 13 Aug 2021

Contact author: ykondi at ccs neu edu, francois at garillot net, payman at fb com, valerini at fb com

Available format(s): PDF | BibTeX Citation

Version: 20210816:132633 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]