# 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.