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 popular for their simplicity and security, but their deterministic variants (which avoid the need for a random number generator) have been challenging to implement in a distributed, threshold setting. Existing solutions for deterministic Schnorr signatures in a distributed setting either require many rounds, make non-black-box use of cryptographic primitives (making them less efficient and harder to analyze), or only achieve weaker security guarantees. The core problem is how to achieve stateless, deterministic signing in a two-party setting with provable security, while only relying on standard cryptographic assumptions and black-box usage of primitives.

Methods

The authors leverage Pseudorandom Correlation Functions (PCFs), a relatively new cryptographic primitive that acts as a multiparty analogue of pseudorandom functions. PCFs allow parties to share correlated random values, which is key to enabling distributed computation.

Specifically, they adapt a Vector Oblivious Linear Evaluation (VOLE) correlation. Their approach involves:

  • A Novel PCF-based Methodology: Instead of relying on zero-knowledge proofs for nonce derivation (as in prior work), they use PCFs to natively translate the stateless deterministic signing technique to the distributed setting.
  • Two Instantiations:
    • Covert Security: This construction uses a simpler VOLE PCF (SoftSpoken VOLE) and achieves security against adversaries who only deviate in ways that are unlikely to be detected. It has very low communication overhead.
  • Full Malicious Security: This construction uses a more complex VOLE PCF (based on Paillier encryption) and achieves full security against active adversaries. It requires a careful translation mechanism to ensure security over a prime field, reducing security to standard assumptions like Decisional Composite Residuosity (DCR) and Strong RSA. This construction offers very low bandwidth consumption.
  • Stateless Deterministic Signing: The core idea is that each party derives its part of the signing nonce using a PCF, and the correlation within the PCF allows them to efficiently verify each other's contributions without needing to reveal their secret keys or rely on external randomness.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • PCFs as a Powerful Tool for Distributed Cryptography: The paper demonstrates that PCFs are a natural fit for translating single-party cryptographic techniques (like stateless deterministic signing) into the multiparty setting, offering a more efficient and elegant solution than traditional zero-knowledge approaches.
  • Bridging the Gap to Practical Threshold Signatures: By achieving stateless deterministic signing with black-box primitive usage and low round complexity, this work significantly advances the practicality of threshold Schnorr signatures for real-world applications.
  • VOLE Correlation's Suitability: The specific VOLE correlation proves to be well-suited for Schnorr signing, enabling efficient distributed nonce generation and verification.
  • The Challenge of Modulus Translation: A key technical hurdle overcome is translating correlations from a composite modulus (used in Paillier-based PCFs) to the prime modulus required for Schnorr signatures, while maintaining security.

Key Results

  • First Two-Party, Two-Round, Stateless, Deterministic Schnorr Signing: The paper presents the first protocol that achieves all these properties while using cryptographic primitives in a black-box manner.
  • Covert Security Protocol: Achieves very low communication overhead (a single group element) and computation cost, comparable to naive semi-honest protocols.
  • Full Malicious Security Protocol: Achieves the lowest bandwidth consumption of any known stateless deterministic Schnorr signing scheme (a few hundred bytes) with reasonable computation overhead (a few exponentiations).
  • Efficiency: The protocols are efficient, with the fully secure version being significantly more bandwidth-efficient than prior work.

Limitations and Future Work

  • Setup Phase: The paper focuses on the signing phase and does not deeply optimize the key generation/setup phase, which requires an ideal PCF setup oracle. Future work could focus on instantiating this setup efficiently.
  • Achieving Both Malicious Security and Standard Assumptions Simultaneously: While the paper presents one protocol for covert security (under standard assumptions like PRF) and another for full security (under stronger assumptions like DCR and Strong RSA), achieving full security under only standard assumptions (like PRF and OT) remains an open question.
  • Generalization: The work focuses on the two-party setting. Extending these techniques to the multi-party (t, n) threshold setting would be a natural next step.

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},
}
Figure