Paper 2017/1171

Attacks on the AJPS Mersenne-based cryptosystem

Koen de Boer, Léo Ducas, Stacey Jeffery, and Ronald de Wolf

Abstract

Aggarwal, Joux, Prakash and Santha recently introduced a new potentially quantum-safe public-key cryptosystem, and suggested that a brute-force attack is essentially optimal against it. They consider but then dismiss both Meet-in-the-Middle attacks and LLL-based attacks. Very soon after their paper appeared, Beunardeau et al.\ proposed a practical LLL-based technique that seemed to significantly reduce the security of the AJPS system. In this paper we do two things. First, we show that a Meet-in-the-Middle attack can also be made to work against the AJPS system, using locality-sensitive hashing to overcome the difficulty that Aggarwal et al.\ saw for such attacks. We also present a quantum version of this attack. Second, we give a more precise analysis of the attack of Beunardeau et al., confirming and refining their results.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. PQCrypto 2018
Keywords
CryptanalysisMersenneNTRUMeet-in-the-MiddleLattice
Contact author(s)
kboer @ cwi nl
History
2018-01-25: revised
2017-12-06: received
See all versions
Short URL
https://ia.cr/2017/1171
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1171,
      author = {Koen de Boer and Léo Ducas and Stacey Jeffery and Ronald de Wolf},
      title = {Attacks on the AJPS Mersenne-based cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1171},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1171}},
      url = {https://eprint.iacr.org/2017/1171}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.