Cryptology ePrint Archive: Report 2021/205

Compact Zero-Knowledge Proofs for Threshold ECDSA with Trustless Setup

Tsz Hon Yuen and Handong Cui and Xiang Xie

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).

Category / Keywords: Threshold signature, ECDSA, Zero-knowledge Proof

Original Publication (with minor differences): IACR-PKC-2021

Date: received 24 Feb 2021, last revised 22 Jul 2021

Contact author: thyuen at cs hku hk

Available format(s): PDF | BibTeX Citation

Note: Correct some typos and minor corrections in the probability analysis in the proof of Thm 2 and 4.

Version: 20210722:073052 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]