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

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. ϵ≪1n² for smoothing parameter η_ϵ(Zⁿ), to ensure the correctness of the security reduction. In this work, we investigate the feasibility of weak smoothness, e.g. ϵ=O(1n) 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 two practical GPV signature instantiations based on a weak smoothness condition. Our first instantiation is a variant of Falcon 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.