Paper 2026/244

Revisit Unravelled Linearization with Erhart (quasi-)Polynomial

Abstract

We study lattice constructions arising from Coppersmith’s method combined with the Unravelled Linearization technique introduced by Herrmann and May (ASIACRYPT~2009) for solving structured polynomial equations, which can yield improved asymptotic bounds. This work contributes in two aspects, theoretical and practical. Theoretical contribution: While Unravelled Linearization, introduced can lead to improved asymptotic bounds, computing these bounds is technically delicate. Previous works typically assume that the lattice dimension is a polynomial function of the scaling parameter $m$ and therefore rely on Lagrange interpolation to derive asymptotic bounds. We show that this assumption does not hold in general. In particular, the interpolation approach used in Herrmann and May (ASIACRYPT~2009) and in \texttt{cuso} (EUROCRYPT~2025) may yield incorrect results: in the former case, the exponant in the determinate may be a quasi-polynomial instead of polynomial, while in the latter it becomes polynomial only beyond a certain threshold. To address this issue, we present a rigorous analysis based on Ehrhart theory for computing asymptotic bounds. As applications, we improve five cryptanalytic results, including attacks on linear congruential generators, quadratic generators, the subset-sum pseudorandom generator, and a recent partial-key attack on isogenies in the P\`oke setting. In the latter case, we reduce the required leakage of most significant bits from $85.29\%$ to $79.81\%$, and further to $79.08\%$ in certain special cases. Practical contribution: Asymptotic bounds alone are insufficient for practical attacks, since one must also determine an appropriate lattice dimension. To avoid trivial guessing of the lattice dimension from small to large, we introduce an estimator, $\mathsf{DimOracle}$, based on Ehrhart theory. Our approach simultaneously estimates the lattice dimension and determinant via the associated Ehrhart (quasi-)polynomials. Due to Barvinok’s algorithm, any fixed number of leading coefficients of these (quasi-)polynomial can be computed in polynomial time by reducing the problem to volume computations of faces of the Newton polytope. Using these coefficients, $\mathsf{DimOracle}$ provides accurate predictions of the required lattice size in practice. We implement $\mathsf{DimOracle}$ and demonstrate its effectiveness through experimental results.