Honest-Majority Threshold ECDSA with Batch Generation of Key-Independent Presignatures

Jonathan Katz; Antoine Urban

doi:10.62056/a0l5wol7

Honest-Majority Threshold ECDSA with Batch Generation of Key-Independent Presignatures

Authors

Jonathan Katz, Antoine Urban

Jonathan Katz

Google, USA
jkatz2 at gmail dot com

Antoine Urban

Telecom Paris, France
antoine dot urban at gmail dot com

Abstract

Several protocols have been proposed recently for threshold ECDSA signatures, mostly in the dishonest-majority setting. Yet in so-called key-management networks, where a fixed set of servers share a large number of keys on behalf of multiple users, it may be reasonable to assume that a majority of the servers remain uncompromised, and in that case there may be several advantages to using an honest-majority protocol.

With this in mind, we describe an efficient protocol for actively secure, honest-majority threshold ECDSA supporting batch generation of key-independent presignatures that allow for “non-interactive” online signing; these properties are not available in existing dishonest-majority protocols. Our protocol offers low latency and high throughput, and runs at an amortized rate of roughly 1.3 ms per presignature (after which signatures can be generated in less than 100 microseconds).

References

[CCL⁺19]

Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker. Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations. In Advances in Cryptology—Crypto 2019, Part III, volume 11694 of LNCS, pages 191–221. 2019. Springer. DOI: 10.1007/978-3-030-26954-8_7

Google Scholar ePrint

[CCL⁺23]

Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker. Bandwidth-efficient threshold EC-DSA revisited: Online/offline extensions, identifiable aborts proactive and adaptive security. Theoretical Computer Science, 939:78–104, 2023. Preliminary version in PKC 2020 DOI: 10.1016/J.TCS.2022.10.016

Google Scholar ePrint

[CDI05]

Ronald Cramer, Ivan Damgård, and Yuval Ishai. Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation. In Theory of Cryptography Conference (TCC) 2005, volume 3378 of LNCS, pages 342–362. 2005. Springer. DOI: 10.1007/978-3-540-30576-7_19

Google Scholar ePrint

[CGG⁺20]

Ran Canetti, Rosario Gennaro, Steven Goldfeder, Nikolaos Makriyannis, and Udi Peled. UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts. In ACM Conf. on Computer and Communications Security (CCS), pages 1769–1787. 2020. ACM. DOI: 10.1145/3372297.3423367

Google Scholar ePrint

[CHI⁺23]

Koji Chida, Koki Hamada, Dai Ikarashi, Ryo Kikuchi, Daniel Genkin, Yehuda Lindell, and Ariel Nof. Fast Large-Scale Honest-Majority MPC for Malicious Adversaries. J. Cryptology, 36(3), 2023. Preliminary version in Crypto 2018 DOI: 10.1007/S00145-023-09453-7

Google Scholar ePrint

[DJN⁺22]

Ivan Damgård, Thomas P. Jakobsen, Jesper Buus Nielsen, Jakob Illeborg Pagter, and Michael Bæksvang Østergaard. Fast threshold ECDSA with honest majority. J. Comp. Security, 30(1):167–196, 2022. Preliminary version in SCN 2020 DOI: 10.3233/JCS-200112

Google Scholar ePrint

[DKLS18]

Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat. Secure Two-party Threshold ECDSA from ECDSA Assumptions. In IEEE Symp. on Security and Privacy, pages 980–997. 2018. IEEE. DOI: 10.1109/SP.2018.00036

Google Scholar ePrint

[DKLS19]

Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat. Threshold ECDSA from ECDSA Assumptions: The Multiparty Case. In IEEE Symposium on Security and Privacy, pages 1051–1066. 2019. IEEE. DOI: 10.1109/SP.2019.00024

Google Scholar ePrint

[DKLS23]

Jack Doerner, Yashvanth Kondi, Eysa Lee, and Abhi Shelat. Threshold ECDSA in Three Rounds. In IEEE Symp. on Security and Privacy 2023. 2023. IEEE. DOI: 10.1109/SP54263.2024.00178

Google Scholar ePrint

[DOK⁺20]

Anders P. K. Dalskov, Claudio Orlandi, Marcel Keller, Kris Shrishak, and Haya Shulman. Securing DNSSEC Keys via Threshold ECDSA from Generic MPC. In ESORICS 2020, volume 12309 of LNCS, pages 654–673. 2020. Springer. DOI: 10.1007/978-3-030-59013-0_32

Google Scholar ePrint

[GJKR01]

Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Robust Threshold DSS Signatures. Information and Computarion, 164(1):54–84, 2001. Preliminary version in Eurocrypt '99 DOI: 10.1006/INCO.2000.2881

Google Scholar ePrint

[GKSS20]

Adam Gągol, Jędrzej Kula, Damian Straszak, and Michał Świętek. Threshold ECDSA for Decentralized Asset Custody. See https://ia.cr/2020/498. 2020.

Google Scholar ePrint

[GS22]

Jens Groth and Victor Shoup. On the Security of ECDSA with Additive Key Derivation and Presignatures. In Advances in Cryptology—Eurocrypt 2022, Part I, volume 13275 of LNCS, pages 365–396. 2022. Springer. DOI: 10.1007/978-3-031-06944-4_13

Google Scholar ePrint

[GSZ20]

Vipul Goyal, Yifan Song, and Chenzhi Zhu. Guaranteed Output Delivery Comes Free in Honest Majority MPC. In Advances in Cryptology—Crypto 2020, Part II, volume 12171 of LNCS, pages 618–646. 2020. Springer. DOI: 10.1007/978-3-030-56880-1_22 See https://eprint.iacr.org/2020/134

Google Scholar ePrint

[Lin21]

Yehuda Lindell. Fast Secure Two-Party ECDSA Signing. J. Cryptology, 34(4), 2021. Preliminary version in Crypto 2017 DOI: 10.1007/S00145-021-09409-9

Google Scholar ePrint

[LN18]

Yehuda Lindell and Ariel Nof. Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody. In ACM Conf. on Computer and Communications Security (CCS), pages 1837–1854. 2018. ACM. DOI: 10.1145/3243734.3243788

Google Scholar ePrint

[MR04]

Philip D. MacKenzie and Michael K. Reiter. Two-party generation of DSA signatures. Intl. J. Info. Security, 2(3-4):218–239, 2004. Preliminary version in Crypto 2001 DOI: 10.1007/S10207-004-0041-0

Google Scholar ePrint

[Pet21]

Michaella Pettit. Efficient Threshold-Optimal ECDSA. In CANS 2021, volume 13099 of LNCS, pages 116–135. 2021. Springer. DOI: 10.1007/978-3-030-92548-2_7

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a0l5wol7

History

Submitted: 2024-12-12
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Jonathan Katz and Antoine Urban, Honest-Majority Threshold ECDSA with Batch Generation of Key-Independent Presignatures. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a0l5wol7.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.