| >| Anyone see a reason why the digits of Pi wouldn't
form an excellent
| >| public large (infinite, actually) string of
"random" bits?
|
| >The issue would be: Are there any dependencies amoung
the bits of
| >pi that would make it easier to predict where an XOR
of n streams of
| >bits taken from different positions actually come from
- or, more
| >weakly, to predict subsequent bits.
|
| When you build this scheme, you have to compare it to all
other ways
| of generating random-looking keystream for a stream
cipher. That
| means comparing it with generators which are guaranteed to
be as hard
| to predict output bits for as a large integer is hard to
factor, for
| example. Beyond the coolness factor of pi, it's hard to
work out what
| additional guarantee we're getting from using it here.
|
| I don't know what the performance of the algorithm for
generating the
| next n bits of pi looks like, but I'm guessing that I can
do a fair
| number of
AES/Serpent/Twofish/MARS/RC6/Blowfish/CAST/3DES/IDEA/RC5
| calculations for the same cost. And we know how to build
a stream
| cipher out of all those ciphers (running in OFB or counter
mode) which
| is guaranteed to be as strong as the strongest of them.
|
| It's all about tradeoffs between performance, security,
and what
| strong statements you can make about your security when
you're done.
| In some applications, I am willing to give up a lot of
performance for
| a solid proof of security; in others, I am willing to give
up any hope
| of a proof of security to get really good performance.
I agree 100% from a practical point of view. Given that you
would
have to use a very large prefix of pi - at least 2^128 bits,
probably
more - just the large-number arithmetic needed pretty much
guarantees
that you aren't going to get a competitive system.
I do find this interesting from a theoretical point of view,
since it
*might* give us some kind of provable security. We don't
seem to have
any techniques that have any hope of proving security for
any
conventional system. What we have are reductions. An
approach like
this ties into a very rich body of mathematics, and *might*
lead to
a path to a proof. (Given the connection that this work has
to
chaotic dynamical systems, there's even the outside
possibility that
one might get a provably secure efficient random bit
generator out of
such systems.)
I certainly wouldn't want to place any bets here. In fact,
my guess
is that this won't go through - that the best you'll get
is a result
of the form: The set of reals for which a system is *not*
provably
secure has measure 0. Unfortunately, either you can't
write down
any *particular* r that works, or there are artificially
constructed
r's that are too expensive to compute.
-- Jerry
------------------------------------------------------------
---------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe
cryptography" to majordomo metzdowd.com
|