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?
| 
| There's even an efficient digit-extraction (a/k/a "random access to
| fractional bits") formula, conveniently base 16:
| http://mathworld.wolfram.com/BBPFormula.html
| 
| I dub this "pi pad".
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.

I doubt anyone knows.  What would worry me is exactly the existence
of the algorithm that would make this approach workable:  A way to
compute the i'th digit of pi without computing all the earlier ones.

As a starter problem, how about a simpler version:  Take n=1!  That
is, the key is simply a starting position in pi - taken from a
suitably large set, say the first 2^256 bits of pi - and we use
as our one-time pad the bits of pi starting from there.  An
attackers problem now turns into:  Given a sequence of k successive
bits of pi taken from among the first 2^256 bits, can you do better
than chance in predicting the k+1'st bit?  The obvious approach of
searching through pi for matches doesn't look fruitful, but perhaps
we can do better.  Note that if pi *isn't* normal to base 2 - and
we still don't know if it is - this starter problem is soluable.

BTW, Bailey and Crandall's work - which led to this discussion -
ties the question of normality to questions about chaotic
sequences.  If the approach of using pi as a one-time pad
works, then all the systems based on chaotic generators
will suddenly deserve a closer look!  (Many fail for much
simpler reasons than relying on such a generator, but some
are untrustworthy not because we don't know of an attack
but because we have no clue how to tell if there is one.)


| Is this idea transcendental or irrational?
Mathematician's insult:  You're transcendental (dense and totally
irrational).
							-- Jerry

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