International Association
for Cryptologic Research

This work presents an improved attack on LWE with hints. Our attack follows a generic and efficient framework that converts an arbitrary number of perfect hints, modular hints, and approximate hints into a problem on lattice. Based on the approach, we give a complexity estimator for solving LWE with hints, and exploit the ``too many hints'' regime with a new method of converting this phenomenon to lattice. The essential component of our work is an improved hint integration method, which decomposes LWE with hints into the SIS part and the LWE part. This new perspective on LWE with hints offers an insight on how hints help us solve the problem, and motivates us to efficiently reduce its dimension via Gaussian elimination instead of LLL reduction. We demonstrate the performance of our attack on LWE instances up to cryptographic dimensions. Experiments show that our method runs significantly faster than the method proposed by May and Nowakowski at Asiacrypt 2023. For example, given 200 perfect hints about CRYSTALS-KYBER 512, our method reduces the running time from 7 hours to 1 hour. When we use our method to solve NTRU, we achieve a 10 times acceleration given 200-350 perfect hints. Furthermore, our method requires fewer hints to carry out successful attacks in the too many hints regime. These results stresses the importance to protect post-quantum cryptography schemes against leakage.

<p> The Learning with Errors (LWE) problem has become one of the most prominent candidates of post-quantum cryptography, offering promising potential to meet the challenge of quantum computing. From a theoretical perspective, optimizing algorithms to solve LWE is a vital task for the analysis of this cryptographic primitive. In this paper, we propose a fine-grained time/memory trade-off method to analyze c-sum BKW variants for LWE in both classical and quantum models, then offer new complexity bounds for multiple BKW variants determined by modulus q, dimension k, error rate alpha, and stripe size b. Through our analysis, optimal parameters can be efficiently found for different settings, and the minimized complexities are lower than existing results. Furthermore, we enhance the performance of c-sum BKW in the quantum computing model by adopting the quantum Meet-in-the-Middle technique as c-sum solver instead of the naive c-sum technique. Our complexity trade-off formula also applies to the quantum version of BKW, and optimizes the theoretical quantum time and memory costs, which are exponentially lower than existing quantum c-sum BKW variants. </p>

<p>At PKC 2009, May and Ritzenhofen proposed the implicit factorization problem (IFP). They showed that it is undemanding to factor two h-bit RSA moduli N1=p1q1, N2=p2q2 where q1, q2 are both αh-bit, and p1, p2 share uh&gt;2αh the least significant bits (LSBs). Subsequent works mainly focused on extending the IFP to the cases where p1, p2 share some of the most significant bits (MSBs) or the middle bits (MBs). In this paper, we propose a novel generalized IFP where p1 and p2 share an arbitrary number of bit blocks, with each block having a consistent displacement in its position between p1 and p2, and we solve it successfully based on Coppersmith’s method. Specifically, we generate a new set of shift polynomials to construct the lattice and optimize the structure of the lattice by introducing a new variable z=p1. We derive that we can factor the two moduli in polynomial time when u&gt;2(n+1)α(1−α^1/(n+1)) with p1, p2 sharing n blocks. Further, no matter how many blocks are shared, we can theoretically factor the two moduli as long as u&gt;2αln(1/α). In addition, we consider two other cases where the positions of the shared blocks are arbitrary or there are k&gt;2 known moduli. Meanwhile, we provide the corresponding solutions for the two cases. Our work is verified by experiments. </p>