Show simple item record

dc.contributor.authorBudroni, Alessandro
dc.contributor.authorTenti, Andrea
dc.contributor.editorBuchmann, Johannes
dc.contributor.editorNitaj, Abderrahmane
dc.contributor.editorRachidi, Tajjeeddine
dc.date.accessioned2020-04-20T11:21:38Z
dc.date.available2020-04-20T11:21:38Z
dc.date.issued2019
dc.PublishedBudroni A, Tenti A. The mersenne low hamming combination search problem can be reduced to an ILP problem. Lecture Notes in Computer Science (LNCS). 2019;11627 LNCS:41-55eng
dc.identifier.issn1611-3349en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttps://hdl.handle.net/1956/21939
dc.description.abstractIn 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=2N−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 <N3 ILP problems of dimension 3.en_US
dc.language.isoengeng
dc.publisherSpringeren_US
dc.relation.ispartofseriesLecture Notes in Computer Scienceeng
dc.titleThe mersenne low hamming combination search problem can be reduced to an ILP problemen_US
dc.typeChapter
dc.typePeer reviewed
dc.typeJournal article
dc.date.updated2020-02-11T14:20:00Z
dc.description.versionacceptedVersionen_US
dc.rights.holderCopyright 2019 Springer Nature Switzerland AGen_US
dc.identifier.doihttps://doi.org/10.1007/978-3-030-23696-0_3
dc.identifier.cristin1712152
dc.source.journalLecture Notes in Computer Science (LNCS)


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record