Paper 2025/2044 Original: eprint.iacr.org/2025/2044 ↗

New Asymptotic Results on Predicting Polynomial Congruential Generators

Abstract

We investigate cryptanalytic attacks for predicting polynomial congruential generators (PCGs) from arbitrarily long sequences of consecutive truncated outputs. Such attacks naturally yield systems of modular polynomial equations, which can be solved using Coppersmith's method. However, deriving the corresponding success conditions by hand requires substantial combinatorial summation, which is typically both time-consuming and tedious. Existing automated Coppersmith methods assist with this computation, but they generally provide only numerical bounds for fixed systems, whereas in our setting the number of equations is itself a parameter. Inspired by the Newton-polytope framework of Feng et al.~(Crypto~2025), we express the success condition as the volume of a high-dimensional polytope and compute it symbolically as a function of the number of outputs. We improve existing asymptotic bounds for the Pollard generator and for linear congruential generators. We also obtain new attacks on quadratic congruential generators (QCGs) with partially known coefficients and on perturbed Power Generators with an unknown masking constant, matching bounds previously achieved only under stronger assumptions on the map $F(x)$.