Improved Cryptanalysis of the AJPS Mersenne Based Cryptosystem

At Crypto 2018, Aggarwal, Joux, Prakash and Santha (AJPS) described a new public-key
encryption scheme based on Mersenne numbers. Shortly after the publication of the cryptosystem,
Beunardeau et al. described an attack with complexity O(2^(2h)). In this paper, we describe an improvedattack with complexity O(2^(1.75h)) .