Cryptology ePrint Archive: Report 2019/468

The Mersenne Low Hamming Combination Search Problem can be reduced to an ILP Problem

Alessandro Budroni and Andrea Tenti

Abstract: In 2017, Aggarwal, Joux, Prakash, and Santha proposed an innovative NTRU-like public-key cryptosystem that was believed to be quantum resistant, based on Mersenne prime numbers \(q = 2^N-1\). After a successful attack designed by Beunardeau, Connolly, Géraud, and Naccache, the authors revised the protocol which was accepted for Round 1 of the Post-Quantum Cryptography Standardization Process organized by NIST. The security of this protocol is based on the assumption that a so-called Mersenne Low Hamming Combination Search Problem (MLHCombSP) is hard to solve. In this work, we present a reduction of MLHCombSP to an instance of Integer Linear Programming (ILP). This opens new research directions that are necessary to be investigated in order to assess the concrete robustness of such cryptosystem. We propose different approaches to perform such reduction. Moreover, we uncover a new family of weak keys, for whose our reduction leads to an attack consisting in solving \(<N^3\) ILP problems of dimension 3.

Category / Keywords: public-key cryptography / Post-Quantum Cryptography, Cryptanalysis, Public-Key Cryptography, Integer Linear Programming, Mersenne-Based Cryptosystem

Original Publication (in the same form): AfricaCrypt 2019

Date: received 7 May 2019, last revised 28 Jun 2019

Contact author: alessandro budroni at uib no, budroni alessandro at gmail com, andrea tenti at uib no, andreat tenti at gmail com

Available format(s): PDF | BibTeX Citation

Note: Fixed typos.

Version: 20190628:192224 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]