*1 "Anyone who attempts to generate random numbers by
     deterministic means is, of course, living in a
     state of sin." -- John Von Neumann

That said, it seems that most of these attacks on Pseudorandom
generators some of which are deliberately flawed, can be ameliorated
somewhat by using a known-good (if slow) Pseudorandom generator.

If we were to take the compromised products, rip out the PRNG's,
and replace them with Blum-Blum-Shub generators, we would have
products that work more slowly -- spending something like an
order of magnitude more time on the generation of Pseudorandom
bits -- but the security of those bits would be subject to an
actual mathematical proof that prediction of the next really is
at least equal in difficulty to a known-size factoring problem.
Factoring problems apparently aren't as hard as we used to think
but they *are* still pretty darn hard.

Slow or not, I think we do need to have at least one option
available in most PRNG-using systems which comes with a
mathematical proof that prediction is GUARANTEED to be hard.
Otherwise it's too easy for people and businesses to be caught
absolutely flatfooted and have no recourse when a flawed PRNG
is discovered or a trust issue requires them to do something
heroic in order to convince customers that the customers' data
can actually be safe.

We've been basing our notion of security on the idea that others
don't know something we don't know -- which is sort of nebulous
on its face and of course can never be provable. We can't really
change that until/unless we can say something definite about
P=NP, but we're a lot more sure that nobody else has anything
definite to say about P=NP than we are about most crypto

Do we know of anything faster than BBS that comes with a real
mathematical proof that prediction is at least as hard as

The cryptography mailing list

Reply via email to