Welcome to the resource topic for 2025/1229
Title:
NTRU with Hints: Recovering NTRU Secret Keys from Partial Leakage
Authors: Honglin Shao, Yuejun Liu, Mingyao Shao, Yongbin Zhou
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.
ePrint: https://eprint.iacr.org/2025/1229
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 .