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 source of issues in practice. In order to mitigate security issues due to bad randomness in deployments, EdDSA (which is a special case of Schnorr) is specified to derive its nonces as a function of the message and the secret key. Implementing this deterministic nonce derivation in a threshold fashion while only using standardized primitives (eg. SHA, AES) is challenging. In this work, we construct protocols that enable such stateless deterministic nonce derivation in a threshold setting, albeit by combining evaluations of standardized PRFs rather than thresholdizing a standardized PRF. While we do not realize a functionally equivalent threshold version of EdDSA, we demonstrate that it is practically feasible to achieve stateless deterministic nonce derivation using standardized primitives in threshold Schnorr.
NIST Workshop on Multi-Party Threshold Schemes (MPTS) 2020. https://csrc.nist.gov/events/2020/mpts2020
Based on joint work with François Garillot, Payman Mohassel, and Valeria Nikolaenko.
NIST Workshop on Multi-Party Threshold Schemes 2020
Starts: November 04, 2020Security and Privacy: cryptography