Cryptology ePrint Archive: Report 2019/610

Improved Cryptanalysis of the AJPS Mersenne Based Cryptosystem

Jean-Sebastien Coron and Agnese Gini

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 O(2^(2h)). In this paper, we describe an improved attack with complexity O(2^(1.75h)).

Category / Keywords: public-key cryptography / Mersenne numbers, LLL.

Original Publication (in the same form): Number-Theoretic Methods in Cryptology 2019

Date: received 31 May 2019, last revised 25 Jun 2021

Contact author: jscoron at gmail com, agnese gini at uni lu

Available format(s): PDF | BibTeX Citation

Version: 20210625:194158 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]