research-article

Efficient Online-friendly Two-Party ECDSA Signature

Authors:

Handong CuiAuthors Info & Claims

CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

Pages 558 - 573

https://doi.org/10.1145/3460120.3484803

Published: 13 November 2021 Publication History

Abstract

Two-party ECDSA signatures have received much attention due to their widespread deployment in cryptocurrencies. Depending on whether or not the message is required, we could divide two-party signing into two different phases, namely, offline and online. Ideally, the online phase should be made as lightweight as possible. At the same time, the cost of the offline phase should remain similar to that of a normal signature generation. However, the existing two-party protocols of ECDSA are not optimal: either their online phase requires decryption of a ciphertext, or their offline phase needs at least two executions of multiplicative-to-additive conversion which dominates the overall complexity. This paper proposes an online-friendly two-party ECDSA with a lightweight online phase and a single multiplicative-to-additive function in the offline phase. It is constructed by a novel design of a re-sharing of the secret key and a linear sharing of the nonce. Our scheme significantly improves previous protocols based on either oblivious transfer or homomorphic encryption. We implement our scheme and show that it outperforms prior online-friendly schemes (i.e., those have lightweight online cost) by a factor of roughly 2 to 9 in both communication and computation. Furthermore, our two-party scheme could be easily extended to the 2-out-of-n threshold ECDSA.

References

[1]

Jean-Philippe Aumasson, Adrian Hamelink, and Omer Shlomovits. 2020. A Survey of ECDSA Threshold Signing. (2020). https://eprint.iacr.org/2020/1390.pdf.

[2]

Carsten Baum, Daniel Escudero, Alberto Pedrouzo-Ulloa, Peter Scholl, and Juan Ramón Troncoso-Pastoriza. 2020. Efficient Protocols for Oblivious Linear Function Evaluation from Ring-LWE. In SCN. Springer, 130--149.

[3]

Donald Beaver. 1991. Efficient multiparty protocols using circuit randomization. In CRYPTO. Springer, 420--432.

[4]

Manuel Blum, Paul Feldman, and Silvio Micali. 1988. Non-interactive zero-knowledge and its applications. In STOC. 103--112.

[5]

Fabrice Boudot. 2000. Efficient proofs that a committed number lies in an interval. In EUROCRYPT. Springer, 431--444.

[6]

Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, and Udi Peled. 2020. UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts. In ACM CCS. 1769--1787.

[7]

Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker. 2019. Two-party ECDSA from hash proof systems and efficient instantiations. In CRYPTO. Springer, 191--221.

[8]

Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker. 2020. Bandwidth-efficient threshold EC-DSA. In PKC. Springer, 266--296.

[9]

Guilhem Castagnos and Fabien Laguillaumie. 2015. Linearly homomorphic encryption from DDH. In CT-RSA. Springer, 487--505.

[10]

Tung Chou and Claudio Orlandi. 2015. The simplest protocol for oblivious transfer. In LATINCRYPT. Springer, 40--58.

[11]

William M Daley and Raymond G Kammer. 2000. Digital signature standard (DSS). Technical Report. BOOZ-ALLEN AND HAMILTON INC MCLEAN VA.

[12]

Ivan Damgård, Marcel Keller, Enrique Larraia, Christian Miles, and Nigel P Smart. 2012. Implementing AES via an actively/covertly secure dishonest-majority MPC protocol. In SCN. Springer, 241--263.

[13]

Yvo Desmedt. 1987. Society and group oriented cryptography: A new concept. In CRYPTO. Springer, 120--127.

[14]

Yvo Desmedt and Yair Frankel. 1989. Threshold cryptosystems. In CRYPTO. Springer, 307--315.

[15]

Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat. 2018. Secure two-party threshold ECDSA from ECDSA assumptions. In IEEE Symposium on Security and Privacy. IEEE, 980--997.

[16]

Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat. 2019. Threshold ECDSA from ECDSA assumptions: the multiparty case. In IEEE Symposium on Security and Privacy. IEEE, 1051--1066.

[17]

Paul Feldman. 1987. A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987). IEEE, 427--438.

Digital Library

[18]

Amos Fiat and Adi Shamir. 1986. How to prove yourself: Practical solutions to identification and signature problems. In CRYPTO. Springer, 186--194.

Digital Library

[19]

Rosario Gennaro and Steven Goldfeder. 2018. Fast multiparty threshold ECDSA with fast trustless setup. In ACM CCS. 1179--1194.

[20]

Satrajit Ghosh, Jesper Buus Nielsen, and Tobias Nilges. 2017. Maliciously secure oblivious linear function evaluation with constant overhead. In ASIACRYPT. Springer, 629--659.

[21]

Niv Gilboa. 1999. Two party RSA key generation. In CRYPTO. Springer, 116--129.

[22]

Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin, Tomas Toft, and Angelo Agatino Nicolosi. 2019. Efficient RSA key generation and threshold paillier in the two-party setting. Journal of Cryptology, Vol. 32, 2 (2019), 265--323.

Digital Library

[23]

Marcel Keller, Emmanuela Orsini, and Peter Scholl. 2015. Actively secure OT extension with optimal overhead. In CRYPTO. Springer, 724--741.

[24]

C Kerry and P Gallagher. 2013. FIPS PUB 186--4: Digital Signature Standard (DSS). Federal Information Processing Standards Publication. National Institute of Standards und Technology (2013).

[25]

Yehuda Lindell. 2017. Fast secure two-party ECDSA signing. In CRYPTO. Springer, 613--644.

[26]

Yehuda Lindell and Ariel Nof. 2018. Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody. In ACM CCS. 1837--1854. Refer https://eprint.iacr.org/2018/987.pdf for the full version.

[27]

Philip MacKenzie and Michael K Reiter. 2001. Two-party generation of DSA signatures. In CRYPTO. Springer, 137--154.

[28]

NEUCRYPO. 2021. mp-ecdsa. https://gitlab.com/neucrypt/mpecdsa.

[29]

Claus-Peter Schnorr. 1991. Efficient signature generation by smart cards. Journal of cryptology, Vol. 4, 3 (1991), 161--174.

Digital Library

[30]

Adi Shamir. 1979. How to share a secret. Commun. ACM, Vol. 22, 11 (1979), 612--613.

Digital Library

[31]

Victor Shoup. 1997. Lower bounds for discrete logarithms and related problems. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 256--266.

[32]

ZenGo X. 2021. multi-party-ecdsa. https://github.com/ZenGo-X/multi-party-ecdsa.

[33]

Tsz Hon Yuen, Handong Cui, and Xiang Xie. 2021. Compact Zero-Knowledge Proofs for Threshold ECDSA with Trustless Setup. In PKC. Springer, 481--511.

Cited By

Wang Z(2025)Blockchain-Assisted Robust Subgroup ECDSA Multisignature for ConsensusIEEE Internet of Things Journal10.1109/JIOT.2024.348521512:4(4525-4535)Online publication date: 15-Feb-2025
https://doi.org/10.1109/JIOT.2024.3485215
Xie ZLiu MXue HAu MDeng RYiu SLuo BLiao XXu JKirda ELie D(2024)Direct Range Proofs for Paillier Cryptosystem and Their ApplicationsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690261(899-913)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690261
Xiong HGong LLi RKumari SChen CAmoon M(2024)Blockchain-Enabled Distributed Identity-Based Ring Signature With Identity Abort for Consumer ElectronicsIEEE Transactions on Consumer Electronics10.1109/TCE.2024.342610170:3(5340-5352)Online publication date: Aug-2024
https://doi.org/10.1109/TCE.2024.3426101
Show More Cited By

Index Terms

Efficient Online-friendly Two-Party ECDSA Signature
1. Security and privacy
  1. Cryptography
    1. Key management
    2. Public key (asymmetric) techniques
      1. Digital signatures

Recommendations

UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts
CCS '20: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security

Building on the Gennaro & Goldfeder and Lindell & Nof protocols (CCS '18), we present two threshold ECDSA protocols, for any number of signatories and any threshold, that improve as follows over the state of the art: -- For both protocols, only the last ...
Fast two-party signature for upgrading ECDSA to two-party scenario easily
Abstract
ECDSA is a standardized signature scheme and is widely used in many fields. However, most two-party ECDSA require a complicated multi-party computation technique to compute the multiplication of many shared secrets and necessitate expensive zero-...
An Efficient Two-Party ECDSA Scheme for Cryptocurrencies
Information Systems Security
Abstract
Threshold signatures have emerged as a promising solution to secure cryptocurrencies. While some signature algorithms like Schnorr, BLS, EdDSA are threshold-friendly, the structure of ECDSA makes it challenging to construct such schemes. As such ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '21: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security

November 2021

3558 pages

ISBN:9781450384544

DOI:10.1145/3460120

General Chairs:
Yongdae Kim
KAIST, Republic of Korea
,
Jong Kim
POSTECH, Republic of Korea
,
Program Chairs:
Giovanni Vigna
University of California, Santa Barbara / VMware, USA
,
Elaine Shi
Carnegie Mellon University, USA

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 November 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

the National Natural Science Foundation of China
the National Key Research and Development Program of China
the Research Grant Council of Hong Kong

Conference

CCS '21

Sponsor:

SIGSAC

CCS '21: 2021 ACM SIGSAC Conference on Computer and Communications Security

November 15 - 19, 2021

Virtual Event, Republic of Korea

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
853
Total Downloads

Downloads (Last 12 months)143
Downloads (Last 6 weeks)17

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang Z(2025)Blockchain-Assisted Robust Subgroup ECDSA Multisignature for ConsensusIEEE Internet of Things Journal10.1109/JIOT.2024.348521512:4(4525-4535)Online publication date: 15-Feb-2025
https://doi.org/10.1109/JIOT.2024.3485215
Xie ZLiu MXue HAu MDeng RYiu SLuo BLiao XXu JKirda ELie D(2024)Direct Range Proofs for Paillier Cryptosystem and Their ApplicationsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690261(899-913)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690261
Xiong HGong LLi RKumari SChen CAmoon M(2024)Blockchain-Enabled Distributed Identity-Based Ring Signature With Identity Abort for Consumer ElectronicsIEEE Transactions on Consumer Electronics10.1109/TCE.2024.342610170:3(5340-5352)Online publication date: Aug-2024
https://doi.org/10.1109/TCE.2024.3426101
Wang JYuan XXu YZhang Y(2024)An Efficient Multiparty Threshold ECDSA Protocol against Malicious Adversaries for Blockchain‐Based LLMsIET Information Security10.1049/2024/22528652024:1Online publication date: 17-Oct-2024
https://doi.org/10.1049/2024/2252865
Chen JWang ZSrivastava GAlghamdi TKhan FKumari SXiong H(2024)Industrial blockchain threshold signatures in federated learning for unified space-air-ground-sea model trainingJournal of Industrial Information Integration10.1016/j.jii.2024.10059339(100593)Online publication date: May-2024
https://doi.org/10.1016/j.jii.2024.100593
Snetkov NVakarjuk JLaud P(2024)TOPCOAT: towards practical two-party Crystals-DilithiumDiscover Computing10.1007/s10791-024-09449-227:1Online publication date: 10-Jul-2024
https://doi.org/10.1007/s10791-024-09449-2
Cheng JWang YChen RHuang X(2024)Subverting Cryptographic Protocols from a Fine-Grained Perspective- A Case Study on 2-Party ECDSAInformation Security and Privacy10.1007/978-981-97-5028-3_19(370-390)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5028-3_19
Xue HAu MLiu MChan KCui HXie XYuen TZhang CMeng WJensen CCremers CKirda E(2023)Efficient Multiplicative-to-Additive Function from Joye-Libert Cryptosystem and Its Application to Threshold ECDSAProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3616595(2974-2988)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3616595
Zhong LWang YDu JLiang DZhong ZHe KZhang A(2023)Fast 2-out-of-n ECDSA Threshold Signature2023 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00092(456-465)Online publication date: 21-Dec-2023
https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom59178.2023.00092
Choi SSon YPaek JLee H(2023)Experimental Analysis of the Recent Key Recovery Protocol with respect to Commitment Schemes2023 14th International Conference on Information and Communication Technology Convergence (ICTC)10.1109/ICTC58733.2023.10392697(669-674)Online publication date: 11-Oct-2023
https://doi.org/10.1109/ICTC58733.2023.10392697
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten