NTRU with Hints: Recovering NTRU Secret Keys from Partial Leakage

Honglin Shao; Yuejun Liu; Mingyao Shao; Yongbin Zhou

Paper 2025/1229

NTRU with Hints: Recovering NTRU Secret Keys from Partial Leakage

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, State Key Laboratory of Cyberspace Security Defense, Beijing, China

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, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Abstract

NTRU-based structured lattices underpin several standardized post-quantum cryptographic schemes, most notably the Falcon signature algorithms. While offering compactness and efficiency, the algebraic structure of NTRU lattices introduces new vulnerabilities under physical attacks, where partial secret key leakage may occur. This work addresses the problem of full key recovery in NTRU-based schemes when adversaries obtain partial information through side-channel or fault attacks. Existing leakage-aware frameworks, including the DDGR estimator and the approach of May and Nowakowski, either lack scalability or are limited to structured, single-source leakage on one secret vector. These constraints make them ineffective against practical leakage patterns in NTRU settings. We propose a unified and scalable framework for recovering NTRU secret keys under partial leakage. Our method supports diverse hint types, such as perfect hints, modular hints, and low-bit leakage, and enables joint integration of leakage across both secret polynomials $ f $ and $ g $. At its core, the framework uses a dimension-reduction strategy to eliminate known coefficients and reduce the problem to a lower-dimensional NTRU instance suitable for lattice reduction. Additionally, we introduce a transformation that converts hints on $ g $ into modular constraints on $ f $, allowing unified hint embedding. We demonstrate practical attacks on Falcon using NIST reference implementations. Leaking 400 coefficients of $f$ in Falcon-512 reduces the required BKZ block size from over 350 to 38, enabling full key recovery within 6 hours. Compared to MN23, our method achieves significant speedups: $5.83\times$ for Falcon-512 with 400 leaked coefficients, and over $15\times$ for Falcon-1024 with 910 leaked coefficients. These results highlight the efficiency and scalability of our framework and the importance of leakage-resilient design for structured NTRU lattices.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Post-quantum cryptography NTRU lattice Cryptanalysis NTRU with hints Lattice reduction
Contact author(s): shaohonglin @ njust edu cn
liuyuejun @ njust edu cn
shaomingyao @ iie ac cn
zhouyongbin @ njust edu cn
History: 2025-07-09: approved; 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 Yongbin Zhou},
      title = {{NTRU} with Hints: Recovering {NTRU} Secret Keys from Partial Leakage},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1229},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1229}
}