Paper 2026/1027 Original: eprint.iacr.org/2026/1027 ↗
Computing Asymptotic Bounds for the Automated Coppersmith Method via Linear Programming
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.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2026-09-18: last updated
- 2026-05-22: published
- Short URL
- https://ia.cr/2026/1027
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}