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

John Kelsey kelsey.j at ix.netcom.com
Tue Mar 21 14:22:49 EST 2006

>From: leichter_jerrold at emc.com
>Sent: Mar 21, 2006 9:58 AM
>To: solinym at gmail.com
>Cc: alex at alten.org, cryptography at metzdowd.com
>Subject: Re: pipad, was Re: bounded storage model - why is R organized as 	2-d array?

>| 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.    

>							-- Jerry

--John Kelsey

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com

More information about the cryptography mailing list