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

See my answer to Blum Blum Shub vs. AES-CTR or other CSPRNGs, which cites references that provide detailed analysis of this question and answers this question for some specific examples. I see no point on repeating it here.

The short summary: How many bits should you extract from BBS? None. In practice, you shouldn't be using BBS; you should be using something else.

• Indeed that answer is very helpful to put the security proofs of BBS in perspective.
– fgrieu
Aug 18, 2012 at 7:14
• I don't like this answer. Even if you want to advise against using BBS, you should still answer the question of the OP. You can do both.
– Nova
Feb 7, 2015 at 17:18
• @Nova, but I did answer the question of the OP. (Perhaps you missed it?) The answer is: zero bits, for practical parameters. There is no number of bits that can be extracted safely, with provable security, for practical parameter settings. That does answer the question that was asked.
– D.W.
Feb 8, 2015 at 1:28

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.

Additional note: if you can change the assumption from the hardness of integer factoring, then you can produce more and more. I found an example in Steinfeld, Pieprzyk, and Wang “On the Provable Security of an Efficient RSA-Based Pseudorandom Generator” (ASIACRYPT 2006).