Paper 2025/1940

GPV Preimage Sampling with Weak Smoothness and Its Applications to Lattice Signatures

Abstract

The lattice trapdoor associated with Ajtai's function is the cornerstone of many lattice-based cryptosystems. The current provably secure trapdoor framework, known as the GPV framework, uses a strong smoothness condition, i.e. $\epsilon\ll \frac{1}{n^2}$ for smoothing parameter $\eta_{\epsilon}(\mathbb{Z}^{n})$, to ensure the correctness of the security reduction. In this work, we investigate the feasibility of weak smoothness, e.g. $\epsilon = O,(\frac{1}{n})$ or even $O(1)$ in the GPV framework and present several positive results. First, we provide a theoretical security proof for GPV with weak smoothness under a new assumption. Then, we present Gaussian samplers that are compatible with the weak smoothness condition. As direct applications, we present several practical GPV signature instantiations based on a weak smoothness condition. Our first instantiation is a variant of Falcon, called, Falcon$^{a ws}$, achieving smaller size and higher security. The public key sizes are $21\%$ to $28\%$ smaller, and the signature sizes are $23.5\%$ to $29\%$ smaller than Falcon. We also showcase an NTRU-based GPV signature scheme that employs the Peikert sampler with weak smoothness. This offers a simple implementation while the security level is greatly lower. Nevertheless, at the NIST-3 security level, our scheme achieves a $49\%$ reduction in size compared to Dilithium-3. We also derive a weak smoothness variant of the Antrag signature scheme, called Antrag$^{ws}$, along with a floating-point free version, which offers an attractive trade-off among portability, efficiency and security. Compared to Antrag, Antrag$^{ws}$ achieves reductions of $16.5\%$ to $21.8\%$ in signature size and $14.3\%$ to $21.4\%$ in public key size. Furthermore, we adapt the compact gadget framework to the weak smoothness setting, removing the need for the new assumption and improving concrete parameters of gadget-based signatures, e.g. Hufu.