Improved Lattice-Based Attack on Mersenne Low Hamming Ratio Search Problem

Mengce Zheng; Wei Yan

Paper 2024/2080

Improved Lattice-Based Attack on Mersenne Low Hamming Ratio Search Problem

Mengce Zheng

, Zhejiang Wanli University

Wei Yan

, National University of Defense Technology

Abstract

This paper investigates the Mersenne number-based $AJPS$ cryptosystem, with a particular focus on its associated hard problem. Specifically, we aim to enhance the existing lattice-based attack on the Mersenne low Hamming ratio search problem. Unlike the previous approach of directly employing lattice reduction algorithm, we apply the lattice-based method to solving polynomial equations derived from the above problem. We extend the search range for vulnerabilities in weak keys and increase the success probability of key recovery attack. To validate the efficacy and accuracy of our proposed improvements, we conduct numerical computer experiments. These experiments serve as a concrete validation of the practicality and effectiveness of our improved attack.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. Minor revision. ACISP 2024
DOI: 10.1007/978-981-97-5028-3_10
Keywords: Attack Mersenne number Weak key Low Hamming weight Lattice
Contact author(s): mengce zheng @ gmail com
yan wei2023 @ nudt edu cn
History: 2024-12-27: approved; 2024-12-26: received; See all versions
Short URL: https://ia.cr/2024/2080
License: CC BY

BibTeX

@misc{cryptoeprint:2024/2080,
      author = {Mengce Zheng and Wei Yan},
      title = {Improved Lattice-Based Attack on Mersenne Low Hamming Ratio Search Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/2080},
      year = {2024},
      doi = {10.1007/978-981-97-5028-3_10},
      url = {https://eprint.iacr.org/2024/2080}
}