{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T20:04:09Z","timestamp":1778789049609,"version":"3.51.4"},"reference-count":44,"publisher":"International Association for Cryptologic Research","issue":"2","license":[{"start":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T00:00:00Z","timestamp":1744070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,6,2]]},"abstract":"<jats:p>We introduce techniques to transform existing stateful hash based signature (HBS) schemes, such as LMS or XMSS, into efficient threshold and distributed signature schemes. Our approach requires a trusted dealer for setup, and uses a large (up to a few GiB, typically) common reference value  for each new public key.  The dealer generates the keypair and distributes shares of the signing key to the trustees, while creating the CRV.  Signing involves an untrusted aggregator communicating point-to-point with a set of trustees.  Only the aggregator needs access to the CRV; the trustees need only a PRF key and enough space to remember which one-time keys they have helped to sign with so far.  Signing requires two round trips between the aggregator and each participating trustee, and only a little more computation from the trustees and aggregator than is done when signing with the underlying HBS scheme. We reduce the security of our scheme to that of the underlying HBS scheme, assuming the availability of a secure PRF.  A dishonest aggregator or tampered CRV can prevent valid signatures from being constructed, but does not allow forgeries.  Our techniques offer a powerful practical defense against accidental reuse of a one-time key in stateful HBS schemes by requiring multiple trustees to fail in the same way in order for key reuse to occur. <\/jats:p>","DOI":"10.62056\/a6ksudy6b","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:09Z","timestamp":1751922549000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":2,"title":["Turning Hash-Based Signatures into Distributed Signatures and Threshold Signatures"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3427-1744","authenticated-orcid":false,"given":"John","family":"Kelsey","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05xpvk416","id-type":"ROR","asserted-by":"publisher"}],"name":"National Institute of Standards and Technology","place":["100 Bureau Drive, Gaithersburg, Maryland, 20899, USA"]},{"id":[{"id":"https:\/\/ror.org\/05f950310","id-type":"ROR","asserted-by":"publisher"}],"name":"COSIC, KU Leuven","place":["Kasteelpark Arenberg 10, box 2452, Leuven, Vlaams-Brabant, 3001, Belgium"],"department":["Computer Security and Industrial Cryptography"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2768-9878","authenticated-orcid":false,"given":"Nathalie","family":"Lang","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/031v4g827","id-type":"ROR","asserted-by":"publisher"}],"name":"Bauhaus-Universit\u00e4t Weimar","place":["Bauhausstr. 111, Weimar, 99425, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4906-5131","authenticated-orcid":false,"given":"Stefan","family":"Lucks","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/031v4g827","id-type":"ROR","asserted-by":"publisher"}],"name":"Bauhaus-Universit\u00e4t Weimar","place":["Bauhausstr. 111, Weimar, 99425, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"48349","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"ref1:rfc8554","doi-asserted-by":"crossref","DOI":"10.17487\/RFC8554","volume-title":"Leighton-Micali Hash-Based Signatures","author":"McGrew","year":"2019","ISSN":"https:\/\/id.crossref.org\/issn\/2070-1721","issn-type":"electronic"},{"key":"ref2:rfc8391","doi-asserted-by":"crossref","DOI":"10.17487\/RFC8391","volume-title":"XMSS: eXtended Merkle Signature Scheme","author":"H\u00fclsing","year":"2018","ISSN":"https:\/\/id.crossref.org\/issn\/2070-1721","issn-type":"electronic"},{"key":"ref3:lamport-79","volume-title":"Constructing Digital Signatures from a One Way Function","author":"Leslie Lamport","year":"1979"},{"key":"ref4:C:Merkle87","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/3-540-48184-2_32","article-title":"A Digital Signature Based on a Conventional Encryption\n  Function","volume":"293","author":"Ralph C. Merkle","year":"1988"},{"key":"ref5:C:Merkle89a","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1007\/0-387-34805-0_21","article-title":"A Certified Digital Signature","volume":"435","author":"Ralph C. Merkle","year":"1990"},{"key":"ref6:WOTSPaper","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-642-38553-7_10","article-title":"W-OTS+ - Shorter Signatures for Hash-Based Signature\n  Schemes","volume":"7918","author":"Andreas H\u00fclsing","year":"2013"},{"key":"ref7:EC:BHHLNP15","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/978-3-662-46800-5_15","article-title":"SPHINCS: Practical Stateless Hash-Based Signatures","volume":"9056","author":"Daniel J. Bernstein","year":"2015"},{"key":"ref8:NISTPQC-R1:Gravity-SPHINCS17","volume-title":"Gravity-SPHINCS","author":"Jean-Phillippe Aumasson","year":"2017"},{"key":"ref9:NISTPQC-R1:SPHINCS+17","volume-title":"SPHINCS+","author":"Andreas Hulsing","year":"2017"},{"key":"ref10:SP800-208","volume-title":"Recommendation for Stateful Hash-Based Signature Schemes","author":"David Cooper","year":"2020"},{"key":"ref11:C:Desmedt87","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/3-540-48184-2_8","article-title":"Society and Group Oriented Cryptography: A New Concept","volume":"293","author":"Yvo Desmedt","year":"1988"},{"key":"ref12:C:DesFra89","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/0-387-34805-0_28","article-title":"Threshold Cryptosystems","volume":"435","author":"Yvo Desmedt","year":"1990"},{"key":"ref13:EC:Shoup00a","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/3-540-45539-6_15","article-title":"Practical Threshold Signatures","volume":"1807","author":"Victor Shoup","year":"2000"},{"key":"ref14:MotiThresholdRSA","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/10719994_16","article-title":"On Threshold RSA-Signing with no Dealer","volume":"1787","author":"Shingo Miyazaki","year":"1999"},{"key":"ref15:NISTIR8214","doi-asserted-by":"publisher","DOI":"10.6028\/NIST.IR.8214","volume-title":"Threshold Schemes for Cryptographic Primitives: Challenges\n  and Opportunities in Standardization and Validation of Threshold\n  Cryptography","author":"Lu\u00eds T. A. N. Brand\u00e3o","year":"2019"},{"key":"ref16:DBLP:conf\/crypto\/GarillotKMN21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-030-84242-0_6","article-title":"Threshold Schnorr with Stateless Deterministic Signing from\n  Standard Assumptions","volume":"12825","author":"Fran\u00e7ois Garillot","year":"2021"},{"key":"ref17:ISC:HPGS03","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/10958513_10","article-title":"Distributed RSA Signature Schemes for General Access\n  Structures","volume":"2851","author":"Javier Herranz","year":"2003"},{"key":"ref18:CTRSA:WWWCQL14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/978-3-319-04852-9_16","article-title":"Practical Distributed Signatures in the Standard Model","volume":"8366","author":"Yujue Wang","year":"2014"},{"key":"ref19:TCS:WWWCQLD15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.tcs.2015.06.029","article-title":"Practical (fully) distributed signatures provably secure in\n  the standard model","volume":"595","author":"Yujue Wang","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref20:DBLP:conf\/pqcrypto\/BansarkhaniM18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-319-79063-3_21","article-title":"G-Merkle: A Hash-Based Group Signature Scheme from\n  Standard Assumptions","volume":"10786","author":"Rachid El Bansarkhani","year":"2018"},{"key":"ref21:SharingTheLUOV","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/978-3-030-35199-1_7","article-title":"Sharing the LUOV: Threshold Post-quantum Signatures","volume":"11929","author":"Daniele Cozzo","year":"2019"},{"key":"ref22:KCLM22","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1145\/3488932.3524128","article-title":"Aggregating and Thresholdizing Hash-based Signatures using\n  STARKs","author":"Irakliy Khaburzaniya","year":"2022"},{"key":"ref23:cryptoeprint:2021\/1048","volume-title":"Aggregating and thresholdizing hash-based signatures using\n  STARKs","author":"Irakliy Khaburzaniya","year":"2021"},{"key":"ref24:DBLP:journals\/cacm\/RivestSA78","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A Method for Obtaining Digital Signatures and Public-Key\n  Cryptosystems","volume":"21","author":"Ronald L. Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref25:DBLP:journals\/ijisec\/JohnsonMV01","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/s102070100002","article-title":"The Elliptic Curve Digital Signature Algorithm (ECDSA)","volume":"1","author":"Don Johnson","year":"2001","journal-title":"Int. J. Inf. Sec."},{"key":"ref26:rfc8032","series-title":"Request for Comments","doi-asserted-by":"publisher","DOI":"10.17487\/RFC8032","volume-title":"Edwards-Curve Digital Signature Algorithm (EdDSA)","author":"Simon Josefsson","year":"2017"},{"key":"ref27:FIPS186-4","doi-asserted-by":"publisher","DOI":"10.6028\/NIST.FIPS.186-4","volume-title":"Digital Signature Standard (DSS)","author":"National Institute of Standards","year":"2013"},{"key":"ref28:DBLP:journals\/iacr\/AumassonHS20","first-page":"1390","article-title":"A Survey of ECDSA Threshold Signing","author":"Jean-Philippe Aumasson","year":"2020","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref29:DBLP:conf\/crypto\/CritesKM23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1007\/978-3-031-38557-5_22","article-title":"Fully Adaptive Schnorr Threshold Signatures","volume":"14081","author":"Elizabeth C. Crites","year":"2023"},{"key":"ref30:PQCpage","volume-title":"NIST Post-Quantum Cryptography Standardization","author":"National Institute of Standards","year":"2016"},{"key":"ref31:PQConramp","volume-title":"NIST Round 1 Additional Signatures","author":"National Institute of Standards","year":"2023"},{"key":"ref32:FIPS204","doi-asserted-by":"publisher","DOI":"10.6028\/NIST.FIPS.204","volume-title":"Module-Lattice-Based Digital Signature Standard","author":"National Institute of Standards","year":"2024"},{"key":"ref33:DBLP:conf\/crypto\/BonehGGJKRS18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/978-3-319-96884-1_19","article-title":"Threshold Cryptosystems from Threshold Fully Homomorphic\n  Encryption","volume":"10991","author":"Dan Boneh","year":"2018"},{"key":"ref34:DBLP:journals\/joc\/DamgardOTT22","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/s00145-022-09425-3","article-title":"Two-Round n-out-of-n and Multi-Signatures and Trapdoor\n  Commitment from Lattices","volume":"35","author":"Ivan Damg\u00e5rd","year":"2022","journal-title":"J. Cryptol."},{"key":"ref35:DBLP:conf\/ccs\/AgrawalKSY22","series-title":"LIPIcs","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.8","article-title":"Round-Optimal Lattice-Based Threshold Signatures,\n  Revisited","volume":"229","author":"Shweta Agrawal","year":"2022"},{"key":"ref36:SP800-185","doi-asserted-by":"crossref","DOI":"10.6028\/NIST.SP.800-185","volume-title":"SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and\n  ParallelHash","author":"John Kelsey","year":"2016"},{"key":"ref37:onemore","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/978-981-96-0875-1_14","article-title":"One-More Unforgeability for Multi - and Threshold\n  Signatures","volume":"15484","author":"Sela Navot","year":"2024"},{"key":"ref38:iana-lms-registry","volume-title":"Leighton-Micali Signatures (LMS) Parameters","author":"Internet Assigned Numbers Authority","year":"2019"},{"key":"ref39:fips205","doi-asserted-by":"crossref","DOI":"10.6028\/NIST.FIPS.205","volume-title":"Stateless Hash-Based Digital Signature Standard","author":"National Institute of Standards","year":"2024"},{"key":"ref40:DBLP:journals\/iacr\/Atapoor23","first-page":"1459","article-title":"Identity-Based Threshold Signatures from Isogenies","author":"Shahla Atapoor","year":"2023","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref41:10.1007\/978-3-031-47818-5_12","isbn-type":"print","first-page":"220","article-title":"Identity-Based Threshold Signatures from\u00a0Isogenies","author":"Shahla Atapoor","year":"2024","ISBN":"https:\/\/id.crossref.org\/isbn\/9783031478185"},{"key":"ref42:DBLP:journals\/iacr\/FluhrerD24","first-page":"18","article-title":"Smaller Sphincs+","author":"Scott R. Fluhrer","year":"2024","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref43:cryptoeprint:2022\/778","volume-title":"SPHINCS+C: Compressing SPHINCS+ With (Almost) No Cost","author":"Mikhail Kudinov","year":"2022"},{"key":"ref44:sphincs+c","doi-asserted-by":"publisher","first-page":"1435","DOI":"10.1109\/SP46215.2023.10179381","article-title":"SPHINCS+C: Compressing SPHINCS+ With (Almost) No Cost","author":"Andreas H\u00fclsing","year":"2023"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:10:03Z","timestamp":1751922603000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/2\/24"}},"subtitle":["Delegate Your Signing Capability, and Distribute it Among Trustees"],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":44,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,7,7]]}},"URL":"https:\/\/doi.org\/10.62056\/a6ksudy6b","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,7]]},"assertion":[{"value":"2025-04-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-2-60"}}