pipad, was Re: bounded storage model - why is R organized as 2-d array?

[leichter_jerrold at emc.com]

| >| 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 at metzdowd.com