Paper 2026/1705

New Attacks on Mersenne Number-Based Cryptosystems: Relaxing Size Constraints

Abstract

In 2017, Aggarwal, Joux, Prakash, and Santha proposed an integer analogue of the NTRU cryptosystem, known as the AJPS cryptosystem. This scheme is based on Mersenne numbers, and is believed to be resistant to quantum attacks. This paper revisits the security of AJPS by reexamining its inherent hard problems. We propose novel attacks that apply the continued fraction-based method and the lattice-based solving strategy for modular polynomial equations, rather than directly using lattice reduction algorithms. Our methods significantly relax the size constraints on the unknown private key. Specifically, we either eliminate the need to estimate upper bounds on the unknowns or extend the attack range of vulnerable weak keys, while enhancing the success probability under unbalanced parameter settings. To validate our theoretical findings, we conduct extensive numerical experiments with parameters of various sizes. The experiments confirm both the practicality and the effectiveness of our proposed attacks.