Welcome to the resource topic for 2019/468
Title:
The Mersenne Low Hamming Combination Search Problem can be reduced to an ILP Problem
Authors: Alessandro Budroni, 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.
ePrint: https://eprint.iacr.org/2019/468
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 .