Paper 2024/358
Stateless Deterministic Multi-Party EdDSA Signatures with Low Communication
Abstract
EdDSA, standardized by both IRTF and NIST, is a variant of the well-known Schnorr signature based on Edwards curves, and enjoys the benefit of statelessly and deterministically deriving nonces (i.e., it does not require reliable source of randomness or state continuity). Recently, NIST calls for multi-party threshold EdDSA signatures in one mode of deriving nonce statelessly and deterministically and verifying such derivation via zero-knowledge (ZK) proofs. Multi-party full-threshold EdDSA signatures in the dishonest-majority malicious setting have the advantage of strong security guarantee, and specially cover the two-party case. However, it is challenging to translate the stateless and deterministic benefit of EdDSA to the multi-party setting, as no fresh randomness is available for the protocol execution. We present the notion of information-theoretic message authenticated codes (IT-MACs) over groups in the multi-verifier setting, and adopt the recent pseudorandom correlation function (PCF) to generate IT-MACs statelessly and deterministically. Furthermore, we generalize the two-party IT-MACs-based ZK protocol by Baum et al. (Crypto'21) into the multi-verifier setting, which may be of independent interest. Together with multi-verifier extended doubly-authenticated bits (mv-edabits) with errors, we design a multi-verifier zero-knowledge (MVZK) protocol to derive nonces statelessly and deterministically. Building upon the MVZK protocol, we propose a stateless deterministic multi-party EdDSA signature, tolerating all-but-one malicious corruptions. Compared to the state-of-the-art multi-party EdDSA signature by Garillot et al. (Crypto'21), we improve communication cost by a factor of $61\times$, at the cost of increasing computation cost by about $2.25\times$ and requiring three extra rounds.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Multi-Party EdDSA SigningMulti-Verifier Zero-Knowledge ProofIT-MACs over GroupSecure Multi-Party Computation
- Contact author(s)
-
fengqi whu @ whu edu cn
yangk @ sklc org
kzoacn @ cs sjtu edu cn
wangxiao @ northwestern edu
yuyu @ yuyu hk
xiexiangiscas @ gmail com
hedebiao @ 163 com - History
- 2024-03-01: approved
- 2024-02-28: received
- See all versions
- Short URL
- https://ia.cr/2024/358
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/358, author = {Qi Feng and Kang Yang and Kaiyi Zhang and Xiao Wang and Yu Yu and Xiang Xie and Debiao He}, title = {Stateless Deterministic Multi-Party EdDSA Signatures with Low Communication}, howpublished = {Cryptology ePrint Archive, Paper 2024/358}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/358}}, url = {https://eprint.iacr.org/2024/358} }