Paper 2025/2044

New Asymptotic Results on Predicting Polynomial Congruential Generators

, State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, School of Mathematical Sciences, University of Chinese Academy of Sciences

Abderrahmane Nitaj, Normandie Univ, UNICAEN, CNRS, LMNO

Yanbin Pan, State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, School of Mathematical Sciences, University of Chinese Academy of Sciences

Mengce Zheng, Zhejiang Wanli University

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)$.

@misc{cryptoeprint:2025/2044,
      author = {Yansong Feng and Abderrahmane Nitaj and Yanbin Pan and Mengce Zheng},
      title = {New Asymptotic Results on Predicting Polynomial Congruential Generators},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/2044},
      year = {2025},
      url = {https://eprint.iacr.org/2025/2044}
}