Paper 2024/1330

New Results for Coppersmith's Method from the Perspective of Sumsets Theory

Abstract

Coppersmith's method, combined with the Jochemsz-May strategy, is widely used to find the small roots of multivariate polynomials for cryptanalysis. At Asiacrypt'23, Meers and Nowakowski improved the Jochemsz-May strategy from a single polynomial equation to a system of polynomial equations and proposed a new method, called Automated Coppersmith. Note that it is typically a tedious and non-trivial task to determine asymptotic upper bounds for Coppersmith’s method and manual analysis has to be performed anew when a new set of polynomials is considered. By making certain heuristic assumption, Meers and Nowakowski showed that the bound can be obtained using Lagrange interpolation with the computer, but it is still time-consuming. Moreover, we find that sometimes the interpolation method may get stuck in local convergence, which will result in an incorrect bound when a natural termination strategy is employed in the method. In this paper, we revisit the Jochemsz-May strategy as well as the work of Meers and Nowakowski and point out that the bound can be obtained by calculating the leading coefficient of some Hilbert function, which is exactly the volume of the corresponding Newton polytope. To this end, we introduce the concept of Sumsets theory and propose a series of related results and algorithms. Compared with the Automated Coppersmith, we overcome the issue of getting stuck in local convergence and directly eliminate the time-consuming calculation for $f^m$ in Automated Coppersmith when $m$ is large, which brings a 1000x$\sim$1200x improvement in running time for some polynomials in our experiment. Additionally, our new method offers a new perspective on understanding Automated Coppersmith, thus providing proof of Meers and Nowakowski's Heuristic 2 for the system of a single polynomial.