TY - GEN
T1 - Efficient Multiplicative-to-Additive Function from Joye-Libert Cryptosystem and Its Application to Threshold ECDSA
AU - Xue, Haiyang
AU - Au, Man Ho
AU - Liu, Mengling
AU - Chan, Kwan Yin
AU - Cui, Handong
AU - Xie, Xiang
AU - Yuen, Tsz Hon
AU - Zhang, Chengru
N1 - Publisher Copyright:
© 2023 Copyright held by the owner/author(s). Publication rights licensed to ACM
PY - 2023/11/21
Y1 - 2023/11/21
N2 - 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 7× faster than those based on Castagnos-Laguillaumie encryption only at the cost of 2× more bandwidth. While our MtA is slower than OT-based constructions, it saves 18.7× 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%.
AB - 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 7× faster than those based on Castagnos-Laguillaumie encryption only at the cost of 2× more bandwidth. While our MtA is slower than OT-based constructions, it saves 18.7× 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%.
KW - Joye-Libert cryptosystem
KW - Multiplicative-to-Additive function
KW - Threshold ECDSA
KW - Zero-knowledge proof
UR - https://www.scopus.com/pages/publications/85179855618
U2 - 10.1145/3576915.3616595
DO - 10.1145/3576915.3616595
M3 - Conference contribution
AN - SCOPUS:85179855618
T3 - CCS 2023 - Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security
SP - 2974
EP - 2988
BT - CCS 2023 - Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security
T2 - 30th ACM SIGSAC Conference on Computer and Communications Security, CCS 2023
Y2 - 26 November 2023 through 30 November 2023
ER -