NTRU with Hints: Secret Key Recovery under Partial Leakage on NTRU-based Signatures

Honglin Shao; Yuejun Liu; Mingyao Shao; Wei Cheng; Yongbin Zhou

Paper 2025/1229

NTRU with Hints: Secret Key Recovery under Partial Leakage on NTRU-based Signatures

Honglin Shao, School of Cyber Science and Engineering, Nanjing University of Science and Technology, Nanjing, China

Yuejun Liu, School of Cyber Science and Engineering, Nanjing University of Science and Technology, Nanjing, China

Mingyao Shao, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Wei Cheng, School of Cyber Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China, LTCI, Tel´ ecom Paris, Institut Polytechnique de Paris, Palaiseau 91120, France

Yongbin Zhou, School of Cyber Science and Engineering, Nanjing University of Science and Technology, Nanjing, China, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China

Abstract

Post-quantum cryptography has become pivotal for ensuring communication security in the quantum era. NTRU-based signature schemes have gained attention due to their computational efficiency and compact public keys and signatures, which reduce communication overheads. However, the algebraic structure of NTRU lattices introduces vulnerabilities in physical attack scenarios, where partial secret key leakage can severely undermine system security. In this paper, we propose the Dimension-and-Sample Reduced NTRU Attack (DSRNA). The core principle of DSRNA is to apply a dimension-reduction strategy that transforms the NTRU instance into a lower-dimensional NTRU instance with fewer samples, which is efficiently solvable via lattice basis reduction. Furthermore, we design a unified hint-embedding technique that jointly exploits side information from both secret keys $f$ and $g$, thereby improving both attack efficiency and success rates. We evaluate the residual security of Falcon and its variants Mitaka and Hawk, under perfect, modular and approximate leakage models. Experimental results demonstrate security degradation. Compared to the method of May et al. at Asiacrypt 2023, DSRNA achieves speedups of $5.8\times$ for Falcon-512 with 400 leaked coefficients and over $29.4\times$ for Falcon-1024 with 905 coefficients. This study reveals the potential vulnerability of NTRU-based signature schemes to partial secret key leakage.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Major revision. 2026 39th IEEE Computer Security Foundations Symposium (CSF)
DOI: 10.1109/CSF68417.2026.00025
Keywords: Post-quantum cryptography Lattice-based cryptanalysis NTRU-based signature Lattice reduction.
Contact author(s): shaohonglin @ njust edu cn
liuyuejun @ njust edu cn
shaomingyao @ iie ac cn
wei cheng @ njust edu cn
zhouyongbin @ njust edu cn
History: 2026-09-14: revised; 2025-07-02: received; See all versions
Short URL: https://ia.cr/2025/1229
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1229,
      author = {Honglin Shao and Yuejun Liu and Mingyao Shao and Wei Cheng and Yongbin Zhou},
      title = {{NTRU} with Hints: Secret Key Recovery under Partial Leakage on {NTRU}-based Signatures},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1229},
      year = {2025},
      doi = {10.1109/CSF68417.2026.00025},
      url = {https://eprint.iacr.org/2025/1229}
}