Welcome to the resource topic for 2025/2044
Title:
New Asymptotic Results on Predicting Non-linear Polynomial Congruential Generators
Authors: Mengce Zheng, Yansong Feng, Abderrahmane Nitaj, Yanbin Pan
Abstract: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.
ePrint: https://eprint.iacr.org/2025/2044
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .