Path: illuminati.io.com!uunet!comp.vuw.ac.nz!waikato!auckland.ac.nz!news
From: eachus@spectre.mitre.org (Robert I. Eachus)
Newsgroups: sci.crypt.research

Subject: Re: A cryptographic pseudorandom number generator
Date: 19 Mar 1995 03:11:42 GMT
Organization: The Mitre Corp., Bedford, MA.
Lines: 35
Sender: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator)
Approved: crypt-submission@cs.aukuni.ac.nz
Message-ID: <3kg7de$8st@net.auckland.ac.nz>
References: <3jdkuc$k6h@lyra.csx.cam.ac.uk> <3jl8lu$pdv@net.auckland.ac.nz>
+           <3jpiuj$c7j@net.auckland.ac.nz>
Reply-To: eachus@spectre.mitre.org (Robert I. Eachus)
NNTP-Posting-Host: cs26.cs.auckland.ac.nz
X-Newsreader: NN version 6.5.0 #3 (NOV)





In article <3jpiuj$c7j@net.auckland.ac.nz> 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.
(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.
 
   The "problem" with Blum, Blum, and Shub is that it is inherently a
public key system where the sequence can be forced forward.  In an
application like this factoring N is not necessary to break security,
all you have to do is find N.  (This is why, just as RSA is used in
PGP, you only want to use BBS to conceal randomly generated private
keys.  That way no one can guess a partial text, and read the
remainder of the message.)
 
--
 
                                        Robert I. Eachus
 
with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...