Paper 2026/1027

Computing Asymptotic Bounds for the Automated Coppersmith Method via Linear Programming

Zhaopeng Dai, School of Mathematics and Statistics, Qingdao University, Qingdao, China

Baofeng Wu, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cybersecurity, University of Chinese Academy of Sciences, Beijing, China

Yanshuo Zhang, Department of Cryptographic Science and Technology, Beijing Electronic Science and Technology Institute, Beijing, China

Kejun Zhang, Department of Cryptographic Science and Technology, Beijing Electronic Science and Technology Institute, Beijing, China

Abstract

Coppersmith's method is a foundational technique for finding small roots of modular equations, and determining asymptotic bounds for the recoverable roots is a central and challenging part of its analysis. In this paper, we transform the computation of asymptotic bounds for the Automated Coppersmith method, proposed by Meers and Nowakowski (ASIACRYPT 2023), into a linear programming problem, thereby obtaining a provably correct and explicitly computable formula. As applications of our method, we obtain improved asymptotic bounds for five cryptanalytic settings: the Commutative Isogeny Hidden Number Problem, the Modular Inversion Hidden Number Problem, the Elliptic Curve Hidden Number Problem, the Linear Congruential Generators with unknown multiplier, and the Leveled Isogeny Problem with Hints for POKÉ. We believe that our method could be useful for evaluating the security of a broader range of cryptographic settings.

@misc{cryptoeprint:2026/1027,
      author = {Zhaopeng Ding and Zhaopeng Dai and Baofeng Wu and Yanshuo Zhang and Kejun Zhang},
      title = {Computing Asymptotic Bounds for the Automated Coppersmith Method via Linear Programming},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1027},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1027}
}