International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Compact Zero-Knowledge Proofs for Threshold ECDSA with Trustless Setup

Tsz Hon Yuen
Handong Cui
Xiang Xie
Search ePrint
Search Google
Presentation: Slides
Abstract: Threshold ECDSA signatures provide a higher level of security to a crypto wallet since it requires more than t parties out of n parties to sign a transaction. The state-of-the-art bandwidth efficient threshold ECDSA used the additive homomorphic Castagnos and Laguillaumie (CL) encryption based on an unknown order group G, together with a number of zero-knowledge proofs in G. In this paper, we propose compact zero-knowledge proofs for threshold ECDSA to lower the communication bandwidth, as well as the computation cost. The proposed zero-knowledge proofs include the discrete-logarithm relation in G and the well-formedness of a CL ciphertext. When applied to two-party ECDSA, we can lower the bandwidth of the key generation algorithm by 47%, and the running time for the key generation and signing algorithms are boosted by about 35% and 104% respectively. When applied to threshold ECDSA, our first scheme is more optimized for the key generation algorithm (about 70% lower bandwidth and 70% faster computation in key generation, at a cost of 20% larger bandwidth in signing), while our second scheme has an all-rounded performance improvement (about 60% lower bandwidth, 27% faster computation in key generation without additional cost in signing).
Video from PKC 2021
  title={Compact Zero-Knowledge Proofs for Threshold ECDSA with Trustless Setup},
  booktitle={Public-Key Cryptography - PKC 2021},
  author={Tsz Hon Yuen and Handong Cui and Xiang Xie},