Impossible compression still not possible. [was RE: Debunking the PGP backdoor myth for good. [was RE: Hypothesis: PGP backdoor

[Ondrej Mikle]

Dave Korn wrote:
>   Of course, I could point out that there is precisely *1* bit of information
> in that huge GIF, so even compressing it to 35 bytes isn't a great
> achievement... it's one of the set of less-common inputs that grow bigger as a
> compromise so that real pictures, which tend to have at least *some*
> variation, grow smaller.
> 

OK, according to Shannon's definition of entropy, how much information 
is there in \pi or e or other transcendent number? AFAIK all finite 
strings are in fractional expansion of \pi (take positive integer base 
other than 10 if you want). Sure, the numbers are correlated, because we 
can express \pi or e as infinite series, though only couple of bytes is 
necessary.

But: if you take any finite string, there exists a finite natural number 
as index where the string can be found in \pi. So are there any "random 
strings" at all? What if I can express the digits starting at 2^(2^k)-th 
index analytically in a short, fast algorithm? In case no other can, 
then I have perfect one-time pad, at least for some time, because 
conventional computers will not reach the place in some reasonable time 
(yes, I know, there may be other correlations). The point I am trying to 
make: if I take e.g. a transcendent number and can analytically express 
a part of its fractional expansion, I *might* have a strong key.

The point for this: I am researching an authenticating scheme where keys 
are *programs*, not data. It means that key can change itself over time, 
for example. The strongest keys would therefore be somewhat recursive 
polymorphic code, that enumerates all possible permutations on some 
finite set in some deterministic, though seemingly random order.

I know that there are "short" descriptions for lots of infinite 
structures, the mentioned transcendent numbers, then take Mandelbrot 
set, various IFSs (iterated function systems), quaternions, unmeasurable 
sets, there are lots of possibilities. What I know for sure is that for 
many mathematical structures short descriptions (programs or (partially) 
recursive functions) exist. What I conjecture is that for each finite 
ordered set a short "compression function" exists. The whole trick is 
that it is almost impossible (meaning computationally infeasible) to 
look for the compression functions using a finite deterministic 
algorithm. Though a human can do it.

It will yet take some time until I have some more results about the 
categories of key programs.

Cheers,
   OM

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