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. \(\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 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.