Efficient Multiplicative-to-Additive Function from Joye-Libert Cryptosystem and Its Application to Threshold ECDSA.

Haiyang Xue, Man Ho Au, Mengling Liu, Yin Kwan Chan, Handong Cui, Xiang Xie, Tsz Hon Yuen, Chengru Zhang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

2 Citations (Scopus)

Abstract

Threshold ECDSA receives interest lately due to its widespread adoption in blockchain applications. A common building block of all leading constructions involves a secure conversion of multiplicative shares into additive ones, which is called the multiplicative-to-additive (MtA) function. MtA dominates the overall complexity of all existing threshold ECDSA constructions. Specifically, O(n2) invocations of MtA are required in the case of n active signers. Hence, improvement of MtA leads directly to significant improvements for all state-of-the-art threshold ECDSA schemes.

In this paper, we design a novel MtA by revisiting the Joye-Libert (JL) cryptosystem. Specifically, we revisit JL encryption and propose a JL-based commitment, then give efficient zero-knowledge proofs for JL cryptosystem which are the first to have standard soundness. Our new MtA offers the best time-space complexity trade-off among all existing MtA constructions. It outperforms state-of-the-art constructions from Paillier by a factor of 1.85 to 2 in bandwidth and 1.2 to 1.7 in computation. It is 7X faster than those based on Castagnos-Laguillaumie encryption only at the cost of 2X more bandwidth. While our MtA is slower than OT-based constructions, it saves 18.7X in bandwidth requirement. In addition, we also design a batch version of MtA to further reduce the amortised time and space cost by another 25%.
Original languageEnglish
Title of host publicationCCS '23: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security
PublisherAssociation for Computing Machinery (ACM)
Pages2974
Number of pages2988
ISBN (Electronic)979-8-4007-0050-7
ISBN (Print)979-8-4007-0050-7
Publication statusPublished - 21 Nov 2023
Event2023 ACM SIGSAC Conference on Computer and Communications Security - Copenhagen, Denmark
Duration: 26 Nov 202330 Nov 2023

Conference

Conference2023 ACM SIGSAC Conference on Computer and Communications Security
Country/TerritoryDenmark
CityCopenhagen
Period26/11/2330/11/23

Fingerprint

Dive into the research topics of 'Efficient Multiplicative-to-Additive Function from Joye-Libert Cryptosystem and Its Application to Threshold ECDSA.'. Together they form a unique fingerprint.

Cite this