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

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 \emph{classical} threshold Schnorr signature scheme already in real-world deployment --- stands out. Its appeal lies in three core features: \emph{partially non-interactive signing}, \emph{non-interactive identifiable abort (IA)}, and \emph{proactive security}. In contrast, while \emph{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 \textsf{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 \emph{everywhere-short} secret sharing, which splits a \emph{short} secret vector $\vecs \in \cR_q^\ell$ into \emph{short} shares and admits a \emph{short} linear reconstruction algorithm. While the resulting construction appears intuitive, its security proof requires a non-trivial, fine-grained analysis of the information on $\vecs$ 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.