How many bits can be safely extracted from the BBS generator at each step?

The Blum-Blum-Shub generator is a deterministic Pseudo-Random Bit Generator with security reducible to that of integer factorization.

Setup: Secretly chose random primes $P$, $Q$, with $P\equiv Q\equiv 3\pmod4$, and compute $N=P\cdot Q$. Secretly chose a random seed $x_0$ in $[1\dots n-1]$ with $\gcd(x_0,N)=1$.

Use: To generate the $i$-th bit, compute $x_i=x_{i-1}^2\bmod N$, and output the low-order bit of $x_i$.

In that definition, BBS produce 1 bit per iteration. For a given $N$, how much can this be improved while maintaining security demonstrably reducible to factorization of $N$ (or determining quadratic residuosity $\bmod N$)?

This is discussed in Vazirani & Vazirani: Efficient and Secure Pseudo-Random Number Generation, with proof that the low 2 bits can be safely extracted, and even (if I get it correctly) $\log n$ bits where $n=\lg_2 N$. However the authors "notice that in all the proofs, $\log n$ can be replaced by $c\cdot\log n$, for any constant $c$". Note 5.41 in the HAC gives it as $c\cdot\lg_2n$ bits and warns that "for a modulus $N$ of a fixed bitlength (eg. $n=$1024 bits), an explicit range of values of $c$ for which the resulting generator is cryptographically secure under the intractability assumption of the integer factorization problem has not been determined".

-

The direct answer to your question is in Koblitz and Menezes (Indocrypt 2006). They pointed out that, for practical parameters, one can produce only $1$ bit per iteration if one wants provable security. See Section 6 of the paper for the detail.