TALH: Threshold Authentication via Leaf-sharing in Hash-based Signatures

"Preview Talk" (by team TALH) @ TCPT3, in reply to the NIST Threshold Call

Abstract: In this talk, I will preview TALH and ASPEN, two hash-based threshold signature schemes planned for submission to the NIST Multi-Party Threshold Cryptography (MPTC) Call. Both schemes rest on the security of a hash function alone, rather than on a structured algebraic problem. TALH (Threshold Authentication via Leaf-sharing in Hash-based Signatures) is stateless. It distributes among the trustees the secret leaves of a forest of random subsets (FORS) and signs in three rounds, two of which fix a randomizer by commit-then-reveal. I will present two ways of sharing these secrets: a compact version based on replicated seeds, whose storage grows combinatorially with the number of trustees, and a scalable version based on Shamir sharing, which avoids that growth and therefore also fits the medium and large party-count profiles of the Call. ASPEN is stateful. It removes the randomizer, so that signing takes a single round and no interaction among trustees is needed, turning the stateful standards XMSS (eXtended Merkle Signature Scheme) and LMS (Leighton-Micali Signatures) into threshold schemes with a non-interactive signing phase. Both schemes assume a trusted dealer, and the aggregator holds only public data, so any trustee can play its role. I will also discuss how the schemes fit categories S1 and N1.5 of the Call.

Joint work: Muhammed Said Gündoğan.

Suggested readings:

• Preview Writeup (PDF): TALH: Threshold Authentication via Leaf-sharing in Hash-based Signatures
• Turning hash-based signatures into distributed signatures and threshold signatures (ia.cr/2022/241)
• Haystack: Threshold and Distributed Stateful Hash-Based Signatures (Preview writeup)
• FIPS 205: Stateless Hash-Based Digital Signature Standard.