Paper 2024/1677

Batch Range Proof: How to Make Threshold ECDSA More Efficient

Guofeng Tang, Digital Technologies, Ant Group
Shuai Han, Shanghai Jiao Tong University
Li Lin, Digital Technologies, Ant Group
Changzheng Wei, Digital Technologies, Ant Group
Ying Yan, Digital Technologies, Ant Group
Abstract

With the demand of cryptocurrencies, threshold ECDSA recently regained popularity. So far, several methods have been proposed to construct threshold ECDSA, including the usage of OT and homomorphic encryptions (HE). Due to the mismatch between the plaintext space and the signature space, HE-based threshold ECDSA always requires zero-knowledge range proofs, such as Paillier and Joye-Libert (JL) encryptions. However, the overhead of range proofs constitutes a major portion of the total cost. In this paper, we propose efficient batch range proofs to improve the efficiency of threshold ECDSA. At the heart of our efficiency improvement is a new technical tool called Multi-Dimension Forking Lemma, as a generalization of the well-known general forking lemma [Bellare and Neven, CCS 2006]. Based on our new tool, we construct efficient batch range proofs for Paillier and JL encryptions, and use them to give batch multiplication-to-addition (MtA) protocols, which are crucial to most threshold ECDSA. Our constructions improve the prior Paillier-based MtA by a factor of 2 and the prior JL-based MtA by a factor of 3, in both computation and bandwidth in an amortized way. Our batch MtA can be used to improve the efficiency of most Paillier and JL based threshold ECDSA. As three typical examples, our benchmarking results show: -- We improve the Paillier-based CGGMP20 [Canetti et al., CCS 2020] in bandwidth by a factor of 2.1 to 2.4, and in computation by a factor of 1.5 to 1.7. -- By implementing threshold ECDSA with the batch JL MtA of XAL+23 [Xue et al., CCS 2023] and our batch JL MtA, respectively, our batch construction improves theirs in bandwidth by a factor of 2.0 to 2.29, and in computation by a factor of 1.88 to 2.09. -- When replacing OT-based MtA in DKLs24 [Doerner et al., S$\&$P 2024] with our Paillier-based batch MtA, we improve the bandwidth efficiency by $7.8\times$ at the cost of $5.7\times$ slower computation.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2024
DOI
10.1145/3658644.3670287
Keywords
Batch range proofMultiplication-to-Addition protocolThreshold ECDSAGeneral forking lemma
Contact author(s)
tang guofeng789 @ gmail com
dalen17 @ sjtu edu cn
felix ll @ antgroup com
changzheng wcz @ antgroup com
fuying yy @ antgroup com
History
2024-12-05: revised
2024-10-16: received
See all versions
Short URL
https://ia.cr/2024/1677
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1677,
      author = {Guofeng Tang and Shuai Han and Li Lin and Changzheng Wei and Ying Yan},
      title = {Batch Range Proof: How to Make Threshold {ECDSA} More Efficient},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1677},
      year = {2024},
      doi = {10.1145/3658644.3670287},
      url = {https://eprint.iacr.org/2024/1677}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.