Welcome to the resource topic for 2017/522
Title:
On the Hardness of the Mersenne Low Hamming Ratio Assumption
Authors: Marc Beunardeau, Aisling Connolly, Rémi Géraud, 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.
ePrint: https://eprint.iacr.org/2017/522
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .