Two-Round Stateless Deterministic Two-Party Schnorr Signatures From Pseudorandom Correlation Functions

Yashvanth Kondi; Claudio Orlandi; Lawrence Roy

Paper 2023/216

Two-Round Stateless Deterministic Two-Party Schnorr Signatures From Pseudorandom Correlation Functions

Yashvanth Kondi, Aarhus University

Claudio Orlandi

, Aarhus University

Lawrence Roy, Aarhus University

Abstract

Schnorr signatures are a popular choice due to their simplicity, provable security, and linear structure that enables relatively easy threshold signing protocols. The deterministic variant of Schnorr (where the nonce is derived in a stateless manner using a PRF from the message and a long term secret) is widely used in practice since it mitigates the threats of a faulty or poor randomness generator (which in Schnorr leads to catastrophic breaches of security). Unfortunately, threshold protocols for the deterministic variant of Schnorr have so far been quite inefficient, as they make non black-box use of the PRF involved in the nonce generation. In this paper, we present the first two-party threshold protocol for Schnorr signatures, where signing is stateless and deterministic, and only makes black-box use of the underlying cryptographic algorithms. We present a protocol from general assumptions which achieves covert security, and a protocol that achieves full active security under standard factoring-like assumptions. Our protocols make crucial use of recent advances within the field of pseudorandom correlation functions (PCFs). As an additional benefit, only two-rounds are needed to perform distributed signing in our protocol, connecting our work to a recent line of research on the trade-offs between round complexity and cryptographic assumptions for threshold Schnorr signatures.

Note: Updated for consistency with camera-ready version (minor edits, and paragraph on implementation).

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in CRYPTO 2023
Keywords: Threshold Cryptography Threshold Signatures Pseudorandom Correlation Functions Schnorr Signatures
Contact author(s): yash @ ykondi net
orlandi @ cs au dk
ldr709 @ gmail com
History: 2024-03-07: revised; 2023-02-17: received; See all versions
Short URL: https://ia.cr/2023/216
License: CC BY

BibTeX

@misc{cryptoeprint:2023/216,
      author = {Yashvanth Kondi and Claudio Orlandi and Lawrence Roy},
      title = {Two-Round Stateless Deterministic Two-Party Schnorr Signatures From Pseudorandom Correlation Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/216},
      year = {2023},
      url = {https://eprint.iacr.org/2023/216}
}