Improved cryptanalysis of the AJPS Mersenne based cryptosystem

Abstract

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 𝓞(22h). In this paper, we describe an improved attack with complexity 𝓞(21.75h).

Keywords

• ajps cryptosystem
• lattice attack
• lll
• 94a60