Stoats: Short Two-round vOle-bAsed Threshold Signatures

"Preview Talk" (by team The Stoats) @ TCPT3, in reply to the NIST Threshold Call

Abstract: This presentation covers our plan to submit Stoats, a family of two-round two-party threshold signature crypto-systems built from pseudorandom correlation functions (PCFs). The principal crypto-systems computes ECDSA (Elliptic Curve Digital Signature Algorithm) or Schnorr signatures in two rounds with about a hundred bytes of communication and a runtime in the range of one millisecond. The crypto-systems from the Stoats family satisfy malicious security in the universal composability framework and include variants with stateless and deterministic signing, i.e., nonces are derived pseudorandomly without keeping state across signing sessions. Signing is enabled by a one-time interactive setup that distributes keys for a PCF generating vector oblivious linear evaluation (VOLE) correlations; the PCF is based on the well-studied sparse learning-parity-with-noise (LPN) assumption in the random oracle model. The underlying VOLE-PCF and its maliciously secure distributed key generation are also specified as a standalone gadget and submitted as a crypto-system.

Joint work: Lennart Braun, Geoffroy Couteau, Kelsey Melissaris, Mahshid Riahinia, Peter Rindal, Elahe Sadeghi.

Suggested readings

• Preview Writeup (PDF): Stoats: Short Two-round vOle-bAsed Threshold Signatures: Two-Party Signing from Pseudorandom Correlated Functions for Vector OLE
• Succinct Two-Round Two-Party Signing from PCFs (ia.cr/2026/1978)
• Fast Pseudorandom Correlation Functions from Sparse LPN (ia.cr/2025/1644)