<p>Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring two-rounds or less are based on heavy tools such as (fully) homomorphic encryption ((F)HE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round signatures from classical assumptions either rely on idealized model such as algebraic group models or on one-more type assumptions, none of which we have a nice analogue in the lattice world. In this work, we construct the first efficient two-round lattice-based threshold signature without relying on FHE or HTDC. It has an offline–online feature where the first round can be preprocessed without knowing message or the signer sets, effectively making the signing phase non-interactive. The signature size is small and shows great scalability. For example, even for a threshold as large as 1024 signers, we achieve a signature size roughly 11 KB. At the heart of our construction is a new lattice-based assumption called the <i>Algebraic One-More Module Learning With Errors</i> (<InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9549_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="89" /> </InlineMediaObject> <EquationSource Format="TEX">$\textsf{AOM}\text {-}\textsf{MLWE} $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">AOM</mi> <mtext>-</mtext> <mi mathvariant="sans-serif">MLWE</mi> </mrow> </math></EquationSource> </InlineEquation>) assumption. We believe this to be a strong inclusion to our lattice toolkits with an independent interest. We establish the selective security of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9549_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="89" /> </InlineMediaObject> <EquationSource Format="TEX">$\textsf{AOM}\text {-}\textsf{MLWE} $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">AOM</mi> <mtext>-</mtext> <mi mathvariant="sans-serif">MLWE</mi> </mrow> </math></EquationSource> </InlineEquation> based on the standard Module Learning With Errors (<InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9549_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="48" /> </InlineMediaObject> <EquationSource Format="TEX">$\textsf{MLWE} $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">MLWE</mi> </math></EquationSource> </InlineEquation>) and Module Short Integer Solution (<InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="145_2025_9549_Article_IEq4.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="38" /> </InlineMediaObject> <EquationSource Format="TEX">$\textsf{MSIS} $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="sans-serif">MSIS</mi> </math></EquationSource> </InlineEquation>) assumptions and provide an in depth analysis of its adaptive security, which our threshold signature is based on.</p>

Two-Round Threshold Signature from Algebraic One-More Learning with Errors

期刊论文
发表日期：

2025年8月15日

查看全文

Thomas Espitau,
Shuichi Katsumata,
Kaoru Takemure

摘要

Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring two-rounds or less are based on heavy tools such as (fully) homomorphic encryption ((F)HE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round signatures from classical assumptions either rely on idealized model such as algebraic group models or on one-more type assumptions, none of which we have a nice analogue in the lattice world. In this work, we construct the first efficient two-round lattice-based threshold signature without relying on FHE or HTDC. It has an offline–online feature where the first round can be preprocessed without knowing message or the signer sets, effectively making the signing phase non-interactive. The signature size is small and shows great scalability. For example, even for a threshold as large as 1024 signers, we achieve a signature size roughly 11 KB. At the heart of our construction is a new lattice-based assumption called the Algebraic One-More Module Learning With Errors ( $\textsf{AOM}\text {-}\textsf{MLWE} $ $AOM - MLWE$ ) assumption. We believe this to be a strong inclusion to our lattice toolkits with an independent interest. We establish the selective security of $\textsf{AOM}\text {-}\textsf{MLWE} $ $AOM - MLWE$ based on the standard Module Learning With Errors ( $\textsf{MLWE} $ $MLWE$ ) and Module Short Integer Solution ( $\textsf{MSIS} $ $MSIS$ ) assumptions and provide an in depth analysis of its adaptive security, which our threshold signature is based on.