Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
Indeed that answer is very helpful to put the security proofs of BBS in perspective. –  fgrieu Aug 18 '12 at 7:14
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.