Paper 2019/468

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

Alessandro Budroni, Technology Innovation Institute
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, Geraud, 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 Integer Linear Programming (ILP). This opens new research directions for assessing the concrete robustness of such cryptosystem. In particular, we uncover a new family of weak keys, for whose our attack runs in polynomial time.

Note: Fixed typos, removed one section, reviewed statement.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. AfricaCrypt 2019
Keywords
Post-Quantum Cryptography Cryptanalysis Public-Key Cryptography Integer Linear Programming Mersenne-Based Cryptosystem
Contact author(s)
budroni alessandro @ gmail com
andreat tenti @ gmail com
History
2022-10-06: last of 3 revisions
2019-05-10: received
See all versions
Short URL
https://ia.cr/2019/468
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/468,
      author = {Alessandro Budroni and Andrea Tenti},
      title = {The Mersenne Low Hamming Combination Search Problem can be reduced to an ILP Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2019/468},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/468}},
      url = {https://eprint.iacr.org/2019/468}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.