Path: utzoo!mnetor!uunet!lll-winken!lll-tis!ames!ncar!noao!arizona!sham
From: sham@arizona.edu (Shamim Pogner Mohamed)
Newsgroups: sci.crypt
Subject: Re: New(?) Random Number Genrator
Message-ID: <5075@megaron.arizona.edu>
Date: 21 Apr 88 21:29:45 GMT
References: <12968@mirror.TMC.COM>
Organization: U of Arizona CS Dept, Tucson
Lines: 35
Summary: a reference

In article <12968@mirror.TMC.COM>, billc@mirror.TMC.COM (Bill Callahan) writes:
> 
  -There is a tantalizing article in the science section of the NYTimes
> -today. ... [ text removed ]

> -	                              The mathematicians have proved
  -	that there is a peculiar connection between the randomness of
  -	the outcome and the difficulty of factoring large numbers.
  -	Specifically, they have proved that if factoring large numbers
  -	is truly hard --- as most believe likely --- the resulting
> -	sequence will be indistinguishable from true randomness."

"Indistinguishable" by a polynomial-time probabilistic algorithm, I think.
Most results have narrowed the restrictions further - if "squaring modulo a
Blum-integer (where a Blum-integer is the product of two distinct primes
both congruent to 3 mod 4) is a weak one-to-one one-way function" comes
to mind (memory a little hazy on this).
The generator has been referred to as a "Cryptographically Secure
Pseudo-Random Bit Generator" (CSPRB generator)
I'm not sure of the converse. Do the gurus out there have any opinions?

References:
Goldreich, Goldwasser & Micali - "How to construct random functions"
(FOCS 1984) (A sort of measure of randomness)
Blum & Micali - "How to generate cryptographically strong sequences of
pseudo-random bits" (FOCS 1982)  (CSPRB generators)
Blum, Blum & Shub - "A simple secure pseudo-random number generator"
(CRYPTO-82)
Yao - "Theory and applications of trapdoor functions" (FOCS 82) (on the
existence of CSPRB generators given a "weak one-way" function)

-- 
Shamim Mohamed,  Dept. of Computer Science,
U of Arizona, Tucson AZ 85721  (602) 621-4891

{ihnp4,allegra,cmcl2...}!arizona!sham  |  sham@arizona.edu