Computing Asymptotic Bounds for the Automated Coppersmith Method via Linear Programming

Zhaopeng Ding; Zhaopeng Dai; Baofeng Wu; Yanshuo Zhang; Kejun Zhang

Paper 2026/1027

Computing Asymptotic Bounds for the Automated Coppersmith Method via Linear Programming

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

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 polynomial 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 POKE. We believe that our method could be useful for evaluating the security of a broader range of cryptographic settings.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Coppersmith’s method automated cryptanalysis asymptotic bounds linear programming
Contact author(s): 16678784491 @ 163 com
dzpeng @ amss ac cn
wubaofeng @ iie ac cn
zhang_yanshuo @ 163 com
zkj @ besti edu cn
History: 2026-05-24: revised; 2026-05-22: received; See all versions
Short URL: https://ia.cr/2026/1027
License: CC BY

BibTeX

@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}
}