International Association
for Cryptologic Research

We investigate cryptanalytic attacks on non-linear polynomial congruential generators (PCGs), a class of number-theoretic pseudorandom number generators. A PCG operates by iterating an algebraic map $F(x) \bmod{p}$ on a secret initial seed $v_0$ using fixed parameters, and outputs a truncated portion of each state (for example, the most significant bits). We propose new and improved lattice-based attacks that exploit systems of modular polynomial equations derived from PCGs.

Specifically, we analyze three common non-linear PCGs: the Quadratic Congruential Generator (QCG), the Power Generator, and the Pollard Generator. We establish asymptotic bounds for predicting these PCGs, assuming the adversary has access to an infinitely long output sequence. To derive these bounds, we develop new symbolic techniques that build on the automated Coppersmith's method framework recently developed by Feng et al. (Crypto '25). Our approach is more flexible than previous methods and is particularly well-suited for deriving symbolic bounds. Applying our techniques, we obtain the best-known analytical results for asymptotic attacks on these PCGs:

We present, for the first time, asymptotic attack bounds on QCGs with partially known coefficients. We extend and improve the asymptotic attack of Herrmann and May (Asiacrypt '09) on Power Generators. We improve the asymptotic attack of Bauer et al. (PKC '12) on Pollard Generators and confirm their conjecture.

We validate our theoretical findings with numerical experiments that demonstrate the practicality and efficacy of our attacks.