Debunking the PGP backdoor myth for good. [was RE: Hypothesis: PGP backdoor (was: A security bug in PGP products?)]

[Ondrej Mikle]

On 8/28/06, Dave Korn <dave.korn at artimi.com> wrote:
>   The author has made the *exact* same error as when someone comes up with a
> magical compression algorithm that they say can compress absolutely any data
> down to a tiny size.  They always get the data to compress, sure, but they
> always have problems with the decompression stage.  They tend to think that
> this is just a minor bug in their decompressor they need more time to work on,
> but no amount of time will let them work around the fundamental mathematical
> fact that they've not got sufficient information in their compressed file to
> reconstruct the original.

Thanks, sorry for the hassle, me (and others) should've checked it
before asking.

Ad. compression algorithm: I conjecture there exists an algorithm (not
necessarily *finite*) that can compress large numbers
(strings/files/...) into "small" space, more precisely, it can
compress number that is N bytes long into O(P(log N)) bytes, for some
polynomial P. Here's a lead:

Take as an example group of Z_p* with p prime (in another words: DLP).
The triplet (Z, p, generator g) is a compression of a string of p-1
numbers, each number about log2(p) bits.

(legend: DTM - deterministic Turing machine, NTM - nondeterministic
Turing machine)

There exists a way (not necessarily fast/polynomial with DTM) that a
lot of strings can be compressed into the mentioned triplets. There
are \phi(p-1) different strings that can be compressed with these
triplets. Exact number of course depends on factorization of p-1.

Decompression is simple: take generator g and compute g, g^2, g^3,
g^4, ... in Z_p*

I conjecture that for every permutation on 1..N there exists a
function that compresses the permutation into a "short"
representation. It is possible that only NTM, possibly with infinite
algorithm (e.g. a human) can do it in some "short finite time". Again,
I could've/should've proven or disproven the conjecture, I just don't
want to do it - yet ;-)

Thanks
  OM

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