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

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

Available format(s): PDF | BibTeX Citation

Version: 20190602:114101 (All versions of this report)

Short URL: ia.cr/2019/610


[ Cryptology ePrint archive ]