Improved Cryptanalysis of the AJPS Mersenne Based Cryptosystem

Jean-Sebastien Coron; Agnese Gini

Paper 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)).

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Number-Theoretic Methods in Cryptology 2019
Keywords: Mersenne numbers LLL.
Contact author(s): jscoron @ gmail com
agnese gini @ uni lu
History: 2021-06-25: revised; 2019-06-02: received; See all versions
Short URL: https://ia.cr/2019/610
License: CC BY

BibTeX

@misc{cryptoeprint:2019/610,
      author = {Jean-Sebastien Coron and Agnese Gini},
      title = {Improved Cryptanalysis of the AJPS Mersenne Based Cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2019/610},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/610}},
      url = {https://eprint.iacr.org/2019/610}
}