Black-Box Threshold Signing of Hash-Based Signatures is Impossible

Abstract: We show a general impossibility result that broadly rules out efficient threshold signing protocols for all known hash-based signature schemes. In particular, we formally model hash-based signatures as schemes which are provably secure in the random oracle model and base their security purely on the security of the underlying random oracle. Using techniques from straight-line extractable NIZKs (non-interactive zero knowledge proofs), our main result shows that there exists no protocol secure against a majority of malicious parties that realizes the signing algorithm of any hash-based signature scheme in an oracle-respecting manner, ie. where each of the parties has only black-box access to the random oracle. The result shows that any protocol to distributively sign a hash-based signature scheme must distributively evaluate the hash function, which significantly reduces efficiency. Our result is broad and encompasses all known hash-based signature schemes in practice, including SPHINCS, SPHINCS+ and XMSS, extending the recent work of [DKR24] that only applied to a limited class of hash-based schemes that use MPC-in-the-head (and notably not to any presently standardized schemes). We believe this serves as a strong argument against the adoption of the SLH-DSA standard in settings which may require threshold signing.

Joint work: Yashvanth Kondi, Naman Kumar, Akira Hernan Vanegas.

[Slides] Suggested reading: Sometimes You Can’t Distribute Random-Oracle-Based Proofs (ia.cr/2023/1381)