LaTSEC: Lattice-Based Threshold Signature from Expander Codes

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

Abstract: In this talk, we present our plan to submit two related cryptosystems to the NIST Threshold Call. Lattice-based threshold signatures with identifiable abort, where misbehaving signers are pinpointed rather than merely detected, need a secret sharing scheme whose shares and reconstruction coefficients are all short; existing schemes of this kind give each participant many short sub-shares, and with them many public verification keys. We first introduce SEC, a secret sharing scheme over integer modules built from a lossless bipartite expander graph, which gives each participant exactly one short share, and we explain why its privacy is computational, reducing to the Module Learning With Errors (MLWE) problem. We then present LaTSEC, a three-round threshold signature over an authenticated broadcast channel that uses SEC as its sharing layer: each participant holds one short signing share and one public abort key, so every partial response is checked independently and non-interactively, without zero-knowledge proofs. We outline its security under the MLWE and Module Short Integer Solution (MSIS) assumptions and show concrete parameters: for 60 participants at 128-bit security, each participant stores a 15.19-KiB share, many times smaller than in the closest comparable scheme. We also discuss the trade-offs, namely a gap between the corruption and signing thresholds, larger signatures, and a trusted dealer, and our plans for the submission package.

Joint work: Muhammad Arzaki, Muhammed F. Esgin, Markku-Juhani O. Saarinen, Amin Sakzad, Ron Steinfeld.

Suggested readings

• Preview Writeup (PDF): LaTSEC: Lattice-Based Threshold Signature from Expander Codes: Identifiable Aborts from Everywhere-Short Secret Sharing over Integer Modules
• Blackbox secret sharing revisited: A coding-theoretic approach with application to expansionless near-threshold schemes (ia.cr/2019/1134)
• Threshold Raccoon: Practical threshold signatures from standard lattice assumptions (ia.cr/2024/184)
• Hermine: An efficient lattice-based FROST-like threshold signature (ia.cr/2026/419)