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

Yansong Feng; Hengyi Luo; Qiyuan Chen; Abderrahmane Nitaj; Yanbin Pan

Paper 2024/1330

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

Yansong Feng, Academy of Mathematics and Systems Science

Hengyi Luo, Academy of Mathematics and Systems Science

Qiyuan Chen, Academy of Mathematics and Systems Science

Abderrahmane Nitaj, Normandie University

Yanbin Pan, Academy of Mathematics and Systems Science

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.

Note: The code has been open-sourced, and the results of CI-HNP over CSURF have been further improved. In particular, we added asymptotic bounds for the Jochemsz-May Extended Strategy, including bounds for variants of this strategy extended to a system of polynomial equations. This update addresses earlier limitations and incorporates more efficient methods for these computations.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Coppersmith Sumsets Newton polytopes Additive combinatorics
Contact author(s): fengyansong @ amss ac cn
luohengyi @ amss ac cn
chenqiyuan @ amss ac cn
abderrahmane nitaj @ unicaen fr
panyanbin @ amss ac cn
History: 2025-02-14: last of 4 revisions; 2024-08-25: received; See all versions
Short URL: https://ia.cr/2024/1330
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1330,
      author = {Yansong Feng and Hengyi Luo and Qiyuan Chen and Abderrahmane Nitaj and Yanbin Pan},
      title = {Computing Asymptotic Bounds for Small Roots in Coppersmith's Method via Sumset Theory},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1330},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1330}
}