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

Yashvanth Kondi, Claudio Orlandi, Lawrence Roy

TL;DR

This paper introduces the first two-party, two-round, stateless, and deterministic Schnorr signature scheme that only uses cryptographic primitives in a black-box manner. This is a significant step towards more secure and practical threshold signature schemes, especially for applications like cryptocurrency wallets.

What Problem Does This Paper Address?

Schnorr signatures are a popular choice for their simplicity and provable security. However, ensuring their security in distributed settings, especially when dealing with deterministic nonce generation (to avoid randomness failures), presents a significant challenge. Previous attempts to create distributed, stateless, and deterministic Schnorr signatures often relied on non-black-box use of cryptographic primitives or were inefficient. This paper tackles the problem of achieving stateless deterministic Schnorr signatures in a two-party setting with provable security, while only making black-box use of underlying cryptographic primitives, and doing so in just two rounds.

Methods

The core of this work lies in leveraging Pseudorandom Correlation Functions (PCFs). PCFs are a generalization of pseudorandom functions (PRFs) to multiparty settings, allowing parties to derive correlated random values from short keys. The authors adapt PCFs to the specific needs of Schnorr signature nonce generation.

They present two main instantiations:

  1. Covert Security: This construction uses the SoftSpoken VOLE PCF and makes black-box use of any PRF. It achieves covert security, meaning a malicious party can only cheat with a small probability. The overhead is minimal, with only additions in Zq and a single group element for bandwidth.
  2. Full Active Security: This construction uses a Paillier encryption-based PCF and achieves full malicious security. It requires a more complex PCF for a large field and involves a novel technique to translate correlations from a ring (ZN) to a prime field (Zq) while preserving security. This is reduced to the Decisional Composite Residuosity (DCR) and Strong RSA assumptions. This protocol achieves the lowest bandwidth consumption among known stateless deterministic Schnorr signing schemes.

A key technical innovation is the development of an (ε, G)-PCFDL (Pseudorandom Correlation Function for Discrete Logarithm), which provides pseudorandom nonces with simulatable proofs. This object is crucial for enabling the stateless and deterministic signing protocol.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • PCFs as the Key Abstraction: The paper highlights PCFs as a powerful tool for building secure and efficient distributed cryptographic protocols, particularly for stateless and deterministic settings. They offer a way to "commit" to random tapes during setup, which can then be accessed by parties to derive correlated values.
  • Bridging the Gap from ZN to Zq: A significant technical hurdle overcome is the translation of correlations from a ring (like ZN, used in Paillier encryption) to a prime field (Zq, used in Schnorr signatures) while maintaining security. This involves a novel mechanism to handle potential cheating.
  • Two-Round Signing is Achievable: The paper demonstrates that two-round stateless deterministic Schnorr signing is possible under standard assumptions, a feat that has been notoriously difficult to achieve previously.
  • Trade-offs in Security and Assumptions: The work presents two protocols showcasing the trade-offs: one with covert security and weaker assumptions (PRF), and another with full security but relying on stronger assumptions (DCR, Strong RSA).

Key Results

  • First two-party, two-round, stateless, deterministic Schnorr signing with black-box primitives.
  • Covert security construction: Minimal overhead, only additions in Zq, and a single group element for bandwidth.
  • Full active security construction: Achieves the lowest bandwidth consumption (a few hundred bytes) among known stateless deterministic Schnorr signing schemes, with a few exponentiations for computation.
  • Security reductions: The constructions are proven secure against the DCR and Strong RSA assumptions.

Limitations and Future Work

  • Setup Phase: The paper acknowledges that the setup phase (key generation) is not optimized and could be further improved. While generic MPC instantiations exist, tailored solutions for specific PCF constructions are left for future work.
  • Open Question: The authors pose an open question about whether a scheme can achieve both full malicious security and rely solely on generic assumptions like OT and PRF simultaneously.
  • Efficiency: While the full security construction is efficient in bandwidth, further optimization of computation might be possible. The covert security construction has very low computational overhead.

Summary updated

BibTeX
@article{kondi2023two,
  author = {Yashvanth Kondi and Claudio Orlandi and Lawrence Roy},
  title = {{Two-Round Stateless Deterministic Two-Party Schnorr Signatures from Pseudorandom Correlation Functions}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2023},
  url = {https://openreview.net/forum?id=QPDv44GaxhK},
}

Loading related content...

Figure