Newsgroups: sci.crypt.research
+     edu!!!!!
From: (Don Beaver)

Subject: Re: A cryptographic pseudorandom number generator
Message-ID: <1995Mar21.035817.15974@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: (sci.crypt.research co-moderator)
Organization: Penn State Comp Sci & Eng
Date: Tue, 21 Mar 1995 03:58:17 GMT
Lines: 40 (Robert I. Eachus) writes:
> (Don Beaver) writes:
>  > Not to quibble, but why are you assuming lg(512) bits are secure?
>  > It would be misleading to use theoretical results to assume this.
>   Huh?  The original Blum, Blum and Shub paper proved that at least
>one secure bit could be generated each iteration.  The lg2(N) lower
>bound on the amount of provably secure randomness came later.

These results are only *asymptotic* results.  Their implications
have been strongly misunderstood.

They say, essentially, that any (polytime) algorithm that tries
to predict a BBS generator using a window of 1 bit [or lg2(N) bits,
if you prefer] will have virtually no advantage, *for large enough N*.

They say nothing about the success or failure of polytime algorithms
on N that have fewer than a few thousand bits.

In fact, it is theoretically trivial to factor N when N is no bigger
than 2^1000000000000000.

(It may or may not be possible to get a prediction advantage using
lg2(N)-bit windows when the factors of N are known, although it
intuitively seems possible.  None of the theoretical results
address this issue.)

>(Techically, on the number of bits you can use and still have
>predicting the previous bits take non-polynomial time.)  Even so, it
>is a lower bound, and the proof can be easily extended if you are
>willing to accept a polynomial limit on the proven difficulty.

It's not clear what you mean by "extending" the proof.