Improved Attacks Against Lattice-Based KEMs Using Hints From Hertzbleed

The Number Theoretic Transform (NTT) is widely employed to accelerate computations in lattice-based cryptography. At CHES 2024, Yu et al. introduced a class of side-channel attacks targeting NTT operations in the simplified Kyber and NTTRU schemes. Their work demonstrated that side-channel leakages - modeled as modular hints - can reveal partial information about the private key. These modular hints were subsequently integrated into the Learning With Errors (LWE) or NTRU lattices to reduce the overall computational complexity of key recovery. However, their approach fails to fully exploit the potential of these modular hints. Our key observation is that these modular hints is sufficient to directly construct lowdimensional lattices, rather than integrating them into the original high-dimensional one.In this paper, for the simplified CPA-secure Kyber scheme, we directly utilize the extracted modular hints to construct low-dimensional lattices. Subsequently, the adversary leverages lattice reduction algorithms to search for non-zero shortest vectors within these lattices. Our experimental results confirm that the full private key can be recovered within 400 seconds on a personal computer. Therefore, our attack practically recovers the private key. However, the method proposed by Yu et al. at CHES 2024 cannot achieve this.Furthermore, for the CCA-secure NTTRU scheme, we extract additional modular hints based on the side-channel methodology proposed by Yu et al. We combine the special structure of the NTTRU private key with the Gaussian elimination to generate low-dimensional lattices, and subsequently estimate the hardness of solving the non-zero Shortest Vector Problem using the estimation methodology adopted by Yu et al. The results indicate that we reduce the computational complexity of key recovery to 234-a significant improvement over the 2114 computational complexity reported by Yu et al. at CHES 2024.