Teddy: Two-Round Threshold Deterministic EdDSA Schemes

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

Abstract: In this talk, we present our plan to submit a t-out-of-n threshold EdDSA scheme, which we call Teddy.  To the best of our knowledge, all prior threshold EdDSA constructions are limited to the n-out-of-n setting.  The obstacle is that each party derives its deterministic local "randomness" solely from the secret key and the message, which lets an adversary recover the secret key by dynamically varying the active signing set.  Teddy—Threshold EdDSA with Dynamic signing set and message—addresses this.  Our technical contributions are twofold: a general t-out-of-n access structure for threshold EdDSA, and optimised zero-knowledge proofs for exponent-VRF computation across several PRF candidates, including Poseidon, AES, and SHA-3.

Joint work: Man Ho Au, Robert H. Deng, Liming Gao, Bowen Jiang, Xianhui Lu, Tian Qiu, Guofeng Tang, Ruida Wang, Haiyang Xue, Guomin Yang, Chengru Zhang.

Suggested readings

• Preview Writeup (PDF): Teddy: Threshold EdDSA Schemes
• Exponent-VRFs and Their Applications (ia.cr/2024/397)
• Sigmabus: Binding Sigmas in Circuits for Fast Curve Operations (ia.cr/2023/1406)