Why is breaking the Blum Blum Shub PRNG not an undecidable problem? The Blum Blum Schub (BBS) pseudo random number generator (PRNG) is defined inductively by
$$
x_{i+1} = x_i^2 \mod N
$$
to generate the bit sequence $b_0b_1b_2...$ where the bits are taken to be the parity of the integers $x_i$, and $N$ and $x_0$ must satisfy particular properties (see this post for example).
The BBS generator is a cryptographically secure PRNG, modulo the Quadratic Residuosity problem; given the integer $N$; the authors reduced finding the prior bit stream to the problem of finding the two prime factors of $N$.
What I am unclear on is why the authors assumed the adversary has access to the integer $N$ and or $x_i$.  By the definition of a cryptographically secure PRNG on Wikipedia, given part or all of the internal state, an adversary should not be able to reconstruct the prior stream of random numbers.  Under this definition, would it not be sufficient to claim that the &quot;internal state&quot; is not the integers $x_i, N$, but rather the stream of bits $b_0b_1...$?
After all, if I am not mistaken, if an adversary obtained access to part of the pseudo random bit stream, then uniquely determining $x_0$ and $N$ from just that information should be very difficult or undecidable, so I am not sure why the authors reduced the challenge of reconstructing the prior bit stream to solving the quadratic residuosity problem.
In particular, how exactly is the &quot;internal state&quot; of a PRNG defined, if not off the random bit stream?  Is the internal state defined as being the random seed? A few iterations after the random seed?  If so, and the PRNG &quot;seed&quot; is reliant on a set of secret parameters $a_1, a_2,...a_m$, then how many of those parameters should be revealed to constitute an &quot;internal state&quot;?
By the definition of a cryptographically secure PRNG on Wikipedia, given part or all of the internal state, an adversary should not be able to reconstruct the prior stream of random numbers.

That's an engineering specification of what requirements a practical CSPRNG should be evaluated against. The definitions used for pseudorandom generator (PRG) in cryptographic theory are weaker than that. For example in Katz &amp; Lindell's textbook (2nd edition), Definition 3.14 (p. 62):

DEFINITION 3.14. Let $\ell$ be a polynomial and let $G$ be a deterministic polynomial-time algorithms such that for any $n$ and any input $ \in \{0,1\}^n$, the result $G(s)$ is a string of length $\ell(n)$. We say that $G$ is a pseudorandom generator if the following conditions hold:

(Expansion:) For every $n$ it holds that $\ell(n) &gt; n$.
(Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $\mathsf{negl}$ such that $$\bigg|\mathrm{Pr}\big[D(G(s)) = 1\big] - \mathrm{Pr}\big[D(r) = 1\big]\bigg| ≤ \mathsf{negl}(n)$$ where the first probability is taken over uniform choice of $s \in \{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$ and the randomness of $D$.


This is the sort of definition that Blum Blum Schub would be evaluated against, and it doesn't even assume that PRGs have an incrementally updated state.

The engineering requirements (I wouldn't call it a definition) that you're reading are, of course, contemplating a range of practical attacks that the theoretical work abstracts away from. But you'll find that practical cryptographic random generator designs routinely embed something like the theoretical definition as a module. For example, with Fortuna the recommendation for what it calls its &quot;generator&quot; submodule is to use a block cipher in CTR mode, whose state is a key/counter pair that allows trivially to reconstruct earlier states (just decrement the counter). But that state is scoped to individual calls to the larger Fortuna construction:

The key is also changed after every data request (however small), so that a future key compromise doesn't endanger previous generator outputs. This property is sometimes described as &quot;Fast Key Erasure&quot; or Forward Secrecy.

So a generator that doesn't have forward secrecy (a name for the property you ask about) is used as a building block to construct one that does.