Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:13:58
lcs Mixmaster Remailer (mix@anon.lcs.mit.edu)
10 Sep 1998 17:40:01 -0000
> > BTW there was a paper at Crypto 98 by Patel and Sundaram about a
> > discrete log based, provably secure RNG which is somewhat faster than BBS.
> > Can generate ~900 bits per exponentiation, compared to BBS which generates
> > 1 bit per squaring. Some people run BBS and use ~10 bits per squaring,
> > but I'm not sure that is provably secure. If you do that, BBS is faster,
> > otherwise the discrete log one is better.
>
> Is the paper online? Anyone have the address if so?
The authors are Sarvar Patel and Ganapathy S. Sundaram, email addresses
sarvar@bell-labs.com, , ganeshs@bell-labs.com. You might contact them and
see if they have an online version of their paper.
The paper is mostly a proof that most of the low order bits of the
discrete logarithm are simultaneously hard, i.e. learning some or all
of them is no easier than learning the whole discrete logarithm.
The RNG works modulo a prime p, such that p = 2q+1, where q is also prime,
and a generator g for the group Z_p* (the nonzero integers mod p). This
is a standard setup for discrete exponentiation using "strong primes".
The RNG is defined by:
"Pick a seed x_0 from Z_p*. Define x_(i+1) = g^x_i mod p. At the ith
step (i>0) output the lower n - omega(log n) bits of x_i, except the least
significant bit."
The value of omega(log n) relates to how much security you need against
an attacker. Basically it is the square of the work factor you want
to make the attacker do. Making it 160 bits means the attacker would
have to do 2^80 work. With a 1024 bit prime this produces 1024-160-1
or 859 bits per exponentiation, all provably strong. With a 512 bit
prime the exponentiation takes only 1/8 as long and produces 351 bits
per iteration, which would be faster. It's probably not a good idea to
go much lower than these values.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:13:58