Miyaji Laboratory

Lattice-based cryptography has received a great deal of attention, with the standardization of post-quantum cryptography by the National Institute of Standards and Technology. The Middle-Product Learning with Errors (MP-LWE) problem is one of the problems used for the security assumption in lattice-based cryptography. The MP-LWE problem mitigates the security risk of the Polynomial LWE (PLWE) problem in that its security depends on a particular polynomial. The MP-LWE problem can be viewed as a special case of the LWE problem. Therefore, we can use any of the known algorithms for the LWE problem to solve the MP-LWE problem. Two methods for solving the MP-LWE problem have been proposed: one applies the Primal Attack and the other applies Kannan's embedding method. In this study, we propose new methods for solving the MP-LWE problem. The first method is the Weighted Primal Attack, which is an improved method of the Primal Attack. Experimental results suggest that the MP-LWE problem, which uses the polynomial doubled as the error, is vulnerable to the Weighted Primal Attack. The second method involves reducing the MP-LWE problem to the vulnerable PLWE problem. This attack can be executed in polynomial time with the dimension. We showed the condition under which the MP-LWE problem can be reduced to the vulnerable PLWE problem. Furthermore, we experimentally confirmed that the MP-LWE problem, which is reducible to the vulnerable PLWE problem, can be solved.