TY - GEN
T1 - GPV Preimage Sampling with Weak Smoothness and Its Applications to Lattice Signatures
AU - Zhang, Shiduo
AU - Jia, Huiwen
AU - Ran, Delong
AU - Yu, Yang
AU - Yu, Yu
AU - Wang, Xiaoyun
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2026.
PY - 2026
Y1 - 2026
N2 - 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. ϵ≪1n2 for smoothing parameter ηϵ(Zn), 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.
AB - 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. ϵ≪1n2 for smoothing parameter ηϵ(Zn), 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.
KW - Falcon Signature Scheme
KW - Gaussian sampling
KW - GPV trapdoor
KW - Lattice-based cryptography
UR - https://www.scopus.com/pages/publications/105025370359
U2 - 10.1007/978-981-95-5099-9_8
DO - 10.1007/978-981-95-5099-9_8
M3 - 会议稿件
AN - SCOPUS:105025370359
SN - 9789819550982
T3 - Lecture Notes in Computer Science
SP - 233
EP - 264
BT - Advances in Cryptology - ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Hanaoka, Goichiro
A2 - Yang, Bo-Yin
PB - Springer Science and Business Media Deutschland GmbH
T2 - 31st Annual International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2025
Y2 - 8 December 2025 through 12 December 2025
ER -