Paper 2025/612

More NTRU+Sign Signatures from Cyclotomic Trinomials

Abstract

Recently, $$+$$ was proposed as a new compact signature scheme, following `Fiat-Shamir with Aborts' (FSwA) framework. Its compactness is mainly based on their novel NTRU-based key structure that fits well with bimodal distributions in the FSwA framework. However, despite its compactness, $$+$$ fails to provide a diverse set of parameters that can meet some desired security levels. This limitation stems from its reliance on a ring $$, where $$ is restricted to powers of two, limiting the flexibility in selecting appropriate security levels. To overcome this limitation, we propose a revised version of $$+$$ by adopting a ring $$ from cyclotomic trinomials, where $$ for some positive integers $$ and $$. Our parameterization offers three distinct security levels: approximately $$, $$, and $$ bits, while preserving the compactness in $$. We implement these re-parameterized $$+$$ schemes, showing that the performance of $$+$$ from cyclotomic trinomials is still comparable to previous lattice-based signature schemes such as $$ and $$.

Note: Preprint.