Thimza: Stateless Threshold Signatures Over Module Lattices with O(1) Signer State

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

Abstract: In this presentation, we will talk about Thimza, a threshold signature over module lattices. In a (t,n) threshold signature scheme, a signing key is distributed among n parties such that any subset of at least t members of participants can jointly produce a valid signature which can be verified by an ordinary verifier. The signatures in Thimza are based on Raccoon system (CRYPTO’ 24). Threshold Raccoon is a lattice-based signature scheme which is a Fiat-Shamir construction and has had a significant influence on threshold lattice-based signatures that avoid expensive operations. This scheme and its variants hide partial signatures behind one-time additive masks. However, there are three main issues with this mechanism. First, a signer needs to remember every session identifier it has ever used to avoid repeating masks, which could leak the key share. Moreover, in the two-round case, a signer set is fixed. The next issue is that the channels need to be authenticated by some message authentication code. Previous attempts to address this issue have resulted in signature inflation from 11 to 30-50 kilobytes. The third issue is that the amount of communication per signer is in the range of 27 to 613 kilobytes, which is inefficient. In our signature scheme, we address all these issues. We first show that interactive Fiat-Shamir threshold signatures cannot be stateless; however, one ephemeral self-erasing token per session is enough. Then, we discuss that masks derived from signer’s view imply a view-partition lemma stating that honest responses decompose based on the views of honest parties. This removes authenticated channels and preprocessing awareness of the signer set. We discuss the security analysis of our scheme and show that it is more efficient than previous schemes. For threshold t=1024, the communication per signer is 16.3 KiB which is 1.6 times less than best prior schemes, while it is at least 1.6 times faster.

Joint work: Navid Abapour, Hamidreza Amini Khorasgani.

Suggested readings

• Preview Writeup (PDF): Thimza: Stateless Threshold Signatures at Optimal Bandwidth
• Raccoon: A Masking-Friendly Signature Proven in the Probing Model (ia.cr/2024/1291)
• Threshold Raccoon: Practical Threshold Signatures from Standard Lattice Assumptions (ia.cr/2024/184)
• Lattice Signatures without Trapdoors (ia.cr/2011/537)