Paper 2024/358

Stateless Deterministic Multi-Party EdDSA Signatures with Low Communication

Qi Feng, Wuhan University
Kang Yang, State Key Laboratory of Cryptology
Kaiyi Zhang, Shanghai Jiao Tong University
Xiao Wang, Northwestern University
Yu Yu, Shanghai Jiao Tong University, Shanghai Qi Zhi Institute
Xiang Xie, PADO Labs, Shanghai Qi Zhi Institute
Debiao He, Wuhan University
Abstract

EdDSA, standardized by both IRTF and NIST, is a variant of the well-known Schnorr signature scheme based on Edwards curves, benefitting from stateless and deterministic derivation of nonces (i.e., it does not require a reliable source of randomness or state continuity). Recently, NIST called for multi-party threshold EdDSA signatures in one mode of verifying such nonce derivation via zero-knowledge (ZK) proofs. However, it is challenging to translate the stateless and deterministic benefits of EdDSA to the multi-party threshold setting, as no fresh randomness is available for signing the same message. In this paper, we present a new stateless and deterministic multi-party EdDSA protocol in the full-threshold setting, tolerating all-but-one malicious corruptions. Compared to the state-of-the-art multi-party EdDSA protocol by Garillot et al. (Crypto'21), we improve the communication cost by a factor of 56x and have the same three rounds, at the cost of increasing the computational cost by about 2.25x. We adopt information-theoretic message authenticated codes (IT-MACs) in the multi-verifier setting to authenticate values, and convert them from a Boolean domain to an arithmetic domain by refining multi-verifier extended doubly-authenticated bits (\edabits). We adopt pseudorandom correlation function (\PCF) to generate IT-MACs statelessly and deterministically. Together, we design a multi-verifier zero-knowledge (MVZK) protocol to derive nonces statelessly and deterministically.

Metadata
Available format(s)
PDF
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-05-28: revised
2024-02-28: received
See all versions
Short URL
https://ia.cr/2024/358
License
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2024/358}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.