From: tcmay@netcom.com (Timothy C. May)
Date: Thu, 10 Feb 94 10:00:21 PST
To: klbarrus@owlnet.rice.edu (Karl Lui Barrus)
Subject: Re: real encryptor...and Chaitin
In-Reply-To: <9402101649.AA00123@rufous.owlnet.rice.edu>
Message-ID: <199402101800.KAA25713@mail.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



> So if indeed this is nothing but RSA then it should be impossible to
> tell the output of the file from random noise.  (And incidentally, I
> checked out Chaitin's Algorithmic Information Theory and have tried to
> read the chapter on random numbers, but let's just say that it is
> extremely slow reading :) I guess that's because it builds on stuff
> from previous chapters or something...)
> 
> Karl Barrus

Chaitin's book is indeed tough sledding! For one thing, it's meant as
a monograph, giving his proofs in condensed form. (I assume Karl is
talking about "Algorithmic Information Theory.") And his two other
books are mostly collections of papers, articles, speeches, etc. Not
very pedagogically appealing. A more useful _text_ is the new "An
Introducution to Kolmogorov Complexity and Its Applications," by Li
and Vitanyi, 1993.

However, even this book will not help much in determining whether some
random block of numbers (no pun intended) is indeed "random." Most of
these results in Kolmogorov-Chaitin complexity are of an abstract
nature, not a _computational_ nature. That is, one doesn't find much
to help in determining if a number or set of numbers is random or not.

The best measures I know of remain the simple things like _entropy_,
but for "almost all" large enough blocks, the calculated entropy is
likely to be nearly maximal (e.g., 7.999... bits per ASCII character).

As interesting as I find K-C complexity and AIT in general to
be--especially in terms of things like why Occam's Razor works, how
induction and Bayesian statistics relate to the real world, etc.--I
can't say I've seen any ways in which it helps in cryptography or
crypanalysis.

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power:2**859433 | Public Key: PGP and MailSafe available.