Why is breaking the Blum Blum Shub PRNG not an undecidable problem?

Question

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 "internal state" 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 "internal state" 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 "seed" 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 "internal state"?

Answer 1

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 & 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:

1. (Expansion:) For every $n$ it holds that $\ell(n) > n$.
2. (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 "generator" 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 "Fast Key Erasure" 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.

Answer 2

I think Luis Casilla's answer answers the question underlying your post (and is thus quite valuable), but not exactly the question you asked.

State is a concept used primarily in computer science (and not other areas of mathematics). Wikipedia offers the relevant article State (computer science) where it explains the general idea that an algorithm's output can depend on previous inputs (and not just current inputs, as a mathematical function does). The internal state of a process is all the information not output (thus internal) that is used by the process to produce future outputs. In the case of the algorithm you mention, both $N$ and $x_i$ are needed to compute $x_{i+1}$. It is possible to make other implementation choices, but obvious alternatives allow $N$ and $x_i$ to be recovered - for example, you could store $(p,q,x_0,i)$ and compute $x_{i+1} = {{x_0}^2}^{i+1}\,\text{mod}\,(p\cdot q)$.

Given this understanding, it looks like Blum, Blum, Shub demonstrate exactly what is described by your link about "state compromise extensions": given the information $(N, x_i)$ to calculate future output, it is hard to calculate previous output. Since the next output bit is unpredictable given previous output bits, you need to store additional information in order to compute the next output bit. They don't prove that you have to store $(N, x_i)$, but they do show that using the obvious implementation still satisfies the "state compromise extensions" requirement.