International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Computing Asymptotic Bounds for Small Roots in Coppersmith's Method via Sumset Theory

Authors:
Yansong Feng , Academy of Mathematics and System Science, Chinese Academy Sciences
Hengyi Luo , Academy of Mathematics and System Science, Chinese Academy Sciences
Qiyuan Chen , Academy of Mathematics and System Science, Chinese Academy Sciences
Abderrahmane Nitaj , Normandie University
Yanbin Pan , Academy of Mathematics and System Science, Chinese Academy Sciences
Download:
Search ePrint
Search Google
Conference: CRYPTO 2025
Abstract: Coppersmith's method is a well-known and practical method for solving polynomial modular equations involved in some cryptosystems such as RSA. An important and tedious task in this method consists in computing the asymptotic bounds. In this work, we address the challenge of computing such asymptotic bounds by introducing the Sumsets theory from Additive Combinatorics as a new analytical tool, which significantly streamlines manual calculations. More precisely, we develop the first provable algorithm for determining these asymptotic bounds, whereas the recent methods based on simple Lagrange interpolation are heuristic. Moreover, the experiments showed that our method is much more efficient than the previous method in practice. We also employ our method to improve the cryptanalytic results for the Commutative Isogeny Hidden Number Problem. Our approach may deepen the understanding of Coppersmith's method and inspire more security analysis methodologies.
BibTeX
@inproceedings{crypto-2025-35638,
  title={Computing Asymptotic Bounds for Small Roots in Coppersmith's Method via Sumset Theory},
  publisher={Springer-Verlag},
  author={Yansong Feng and Hengyi Luo and Qiyuan Chen and Abderrahmane Nitaj and Yanbin Pan},
  year=2025
}