Paper 2026/419

Hermine: An Efficient Lattice-based FROST-like Threshold Signature

Abstract

Threshold signatures have regained a strong interest recently, driven by applications in cryptocurrencies and NIST's ongoing call for threshold schemes. Among them, FROST - a classical threshold Schnorr signature scheme already in real-world deployment - stands out. Its appeal lies in three core features: partially non-interactive signing, non-interactive identifiable abort (IA), and proactive security. In contrast, while post-quantum (PQ) threshold signatures have seen significant advances in recent years, no existing scheme simultaneously provides even two of these features. Considering the imminent need to migrate to PQ cryptography, this state-of-the-art remains unsatisfactory. In this work, we propose Hermine, a lattice-based threshold signature that offers the full feature set of FROST under standard lattice assumptions. Hermine is designed to efficiently support the Medium scale of parties ($N \le 64$) as defined in the NIST threshold call, producing a small \Raccoon signature of size $11$ KB. Our main technical contribution is introducing an everywhere-short secret sharing, which splits a short secret vector $\mathbf{s} \in R_q^\ell$ into short shares and admits a short linear reconstruction algorithm. While the resulting construction appears intuitive, its security proof requires a non-trivial, fine-grained analysis of the information on $\mathbf{s}$ that is inherently leaked by the short shares. Furthermore, we formalize game-based unforgeability and IA definitions with proactive security, which may be of independent interest.

Note: Hermine consolidates and supersedes preliminary versions of this research found in ePrint 2025/871 and 2025/1166. The contributions regarding short secret sharing and Vandermonde-based short secret sharing are considered original to this project and are treated as novel components of the current work.