Welcome to the resource topic for 2025/1940
Title:
GPV Preimage Sampling with Weak Smoothness and Its Applications to Lattice Signatures
Authors: Shiduo Zhang, Huiwen Jia, Delong Ran, Yang Yu, Yu Yu, Xiaoyun Wang
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 \emph{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 \emph{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.
ePrint: https://eprint.iacr.org/2025/1940
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .