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

Ondrej Mikle ondrej.mikle at gmail.com
Mon Aug 28 16:04:16 EDT 2006

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