### On the Hardness of the Mersenne Low Hamming Ratio Assumption

Marc Beunardeau, Aisling Connolly, Rémi Géraud, and David Naccache

##### Abstract

In a recent paper, Aggarwal, Joux, Prakash, and Santha (AJPS) describe an ingenious public-key cryptosystem mimicking NTRU over the integers. This algorithm relies on the properties of Mersenne primes instead of polynomial rings. The security of the AJPS cryptosystem relies on the conjectured hardness of the Mersenne Low Hamming Ratio Assumption, defined in [AJPS]. This work shows that AJPS' security estimates are too optimistic and describes an algorithm allowing to recover the secret key from the public key much faster than foreseen in [AJPS]. In particular, our algorithm is \emph{experimentally practical} (within the reach of the computational capabilities of a large organization), at least for the parameter choice $\{n=1279,h=17\}$ conjectured in [AJPS] as corresponding to a $2^{120}$ security level. The algorithm is fully parallelizable.

Note: Minor update on the probability estimate.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
remi geraud @ ens fr
History
2017-06-20: last of 3 revisions
See all versions
Short URL
https://ia.cr/2017/522

CC BY

BibTeX

@misc{cryptoeprint:2017/522,
author = {Marc Beunardeau and Aisling Connolly and Rémi Géraud and David Naccache},
title = {On the Hardness of the Mersenne Low Hamming Ratio Assumption},
howpublished = {Cryptology ePrint Archive, Paper 2017/522},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/522}},
url = {https://eprint.iacr.org/2017/522}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.