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