Newsgroups: sci.crypt.research
Path: illuminati.io.com!uunet!news.mathworks.com!news.duke.edu!godot.cc.duq.
+     edu!hudson.lm.com!news.pop.psu.edu!news.cac.psu.edu!newsserver.jvnc.net!
+     nntpserver.pppl.gov!princeton!tucson.princeton.edu!dawagner
From: beaver@castor.cse.psu.edu (Don Beaver)

Subject: Re: A cryptographic pseudorandom number generator
Message-ID: <1995Mar21.035817.15974@Princeton.EDU>
Originator: news@hedgehog.Princeton.EDU
Sender: dawagner@princeton.edu (sci.crypt.research co-moderator)
Nntp-Posting-Host: tucson.princeton.edu
Organization: Penn State Comp Sci & Eng
Date: Tue, 21 Mar 1995 03:58:17 GMT
Approved: crypt-request@cs.aukuni.ac.nz
Lines: 40


eachus@spectre.mitre.org (Robert I. Eachus) writes:
>beaver@castor.cse.psu.edu (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.

Don