CryptoDB
GPV Preimage Sampling with Weak Smoothness and Its Applications to Lattice Signatures
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| 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}(\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. %Interestingly, the additional assumption has \emph{no impact on the concrete security} of practical GPV signatures. 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 \emph{smaller size} and \emph{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. |
BibTeX
@inproceedings{asiacrypt-2025-35913,
title={GPV Preimage Sampling with Weak Smoothness and Its Applications to Lattice Signatures},
publisher={Springer-Verlag},
author={Shiduo Zhang and Huiwen Jia and Delong Ran and Yang Yu and Yu Yu and Xiaoyun Wang},
year=2025
}