Re: Randomness of a bit string

Tim writes:
>But can he ever say "I can prove the number is random"? No. There's
>always some chance an even-cleverer puzzle solver will find the
>pattern, the key that unlocks the randomness. For example, most
>ciphertexts pass nearly all statistical tests for randomness, "look"
>random, and even _act_ like random numbers (recall the Blum-Blum-Shub
>pseudorandom number generator and how good it is). But simple
>application of the key turns the seemingly random
>"100010001010110010101" into "ATTACK."

   But can we say that "100010001010110010101" has been ``compressed''
into "ATTACK"? How do we know? Let IC(x) stand for the amount of information
storage used by x. Is 

     IC(100010001010110010101) > IC(ATTACK) + IC(key) + IC(algorithm)?

   It is not at all clear that this relationship would hold. (in fact,
I don't think it will even begin to work out unless the cyphertext
is much longer than the plaintext) So in fact, cryptorandom numbers
can be considered incompressible if you take into account the algorithm
required to perform the operation -- just as if I had used a 100 terabyte 
dictionary to compress via lookup, or better yet, a one time pad.

-Ray
All of this is meaningless anyway. Information theory was proven wrong
by WEB technologies when they invented a compression program that can
recursively compress any input data down to 64k. Harddrives are now
obsolete.

-- Ray Cromwell        |    Engineering is the implementation of science;    --
-- rjc@gnu.ai.mit.edu  |       politics is the implementation of faith.      --

(I'm gonna take a breather on this "randomness of a bit string" thread
after sending this post off. I agree with what many folks have
written, and was especially glad to see Scott Collins' nice summary
earlier today about the difficulties in describing randomness. It's a
fascinating topic, with even some practical consequences for
Cypherpunks....maybe.) 

Ray Cromwell writes:

> Tim writes:
> >But can he ever say "I can prove the number is random"? No. There's
> >always some chance an even-cleverer puzzle solver will find the
> >pattern, the key that unlocks the randomness. For example, most
> >ciphertexts pass nearly all statistical tests for randomness, "look"
> >random, and even _act_ like random numbers (recall the Blum-Blum-Shub
> >pseudorandom number generator and how good it is). But simple
> >application of the key turns the seemingly random
> >"100010001010110010101" into "ATTACK."
> 
>    But can we say that "100010001010110010101" has been ``compressed''
> into "ATTACK"? How do we know? Let IC(x) stand for the amount of information

Let me first point out that _any_ string can be "compressed" into
"ATTACK" with the right mapping. My house could be stormed my Reno's
Raiders and the number 100010001010110010101 subjected to thorough
scrutiny at the Fort. Lo and behold, they could find the string which
when applied to my string (by some process) outputs "ATTACK."

There are some subtle issues of "relevance" that need to be addressed.
As an example, if a number written down somewhere in my house produces
the transformation into "ATTACK," that's presumably of more relevance
than if the NSA finds some number lying around (and of course they can
_construct_ such a number easily). I'm sure cryptanalysts take such
things into account, but formal theories don't seem to have addressed
this (but I may just be unaware of papers along these lines). And
certainly the courts have yet to touch on this issue, so far as I
know.

Scott Collins nicely summarized the difficulties in calling any number
random (echoing the points I was making, perhaps less formally), and
Phil Karns was right when he said "Randomness is in the eye of the
beholder." (He may've been making an ironic point about my arguments,
but he was still right.)

Back to Ray's point:

> storage used by x. Is 
> 
>      IC(100010001010110010101) > IC(ATTACK) + IC(key) + IC(algorithm)?
> 
>    It is not at all clear that this relationship would hold. (in fact,
> I don't think it will even begin to work out unless the cyphertext
> is much longer than the plaintext) So in fact, cryptorandom numbers
> can be considered incompressible if you take into account the algorithm
> required to perform the operation -- just as if I had used a 100 terabyte 
> dictionary to compress via lookup, or better yet, a one time pad.

Yeah, but the complexity of the algorithm, and the "CPU effort" needed
to mount the analysis is not considered part of "Kolmogorov
complexity." That's just the formalism. Since the effort is indeed
important (e.g., the complexity of DNA strings, for example, gives
evidence that many billions of years of compression, massaging, more
compression, etc. happened), others have developed measures of
complexity which take into account the effort, the CPU cycles, if you
will.

Greg Chaitin first looked at this in 1966, but it was left to fellow
IBM researcher Charles Bennett (whom Cypherpunks may know as the
coinventor with Gilles Brassard of "quantum cryptography," and also a
pioneer in reversible computation) to label the idea "logical depth"
and explore the ramifications more deeply (pun intended).

Logical depth addresses the issues Ray is raising. A good summary is
in "The Turing Machine: A Half-Century Survey," edited by Rolf Herken,
and published in about 1991.

> All of this is meaningless anyway. Information theory was proven wrong
> by WEB technologies when they invented a compression program that can
> recursively compress any input data down to 64k. Harddrives are now
> obsolete.

Yes, as Perry Metzger once showed on this list, even the longest of
posts can be compressed into the period at the end of this sentence.


--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.

Ray writes:
 > All of this is meaningless anyway. Information theory was proven wrong
 > by WEB technologies when they invented a compression program that can
 > recursively compress any input data down to 64k. Harddrives are now
 > obsolete.

Either I'm really dense in one of two ways (this is a joke I don't
get, or it's really true), or my pegging bullshit meter is right.
Could you go into a little more detail?

--
| GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com>       |
| TAKE TWA TO CAIRO.          ||| Tivoli Systems, Austin, TX:        |
|     (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |

Mike McNally writes:
> 
> 
> Ray writes:
>  > All of this is meaningless anyway. Information theory was proven wrong
>  > by WEB technologies when they invented a compression program that can
>  > recursively compress any input data down to 64k. Harddrives are now
>  > obsolete.
> 
> Either I'm really dense in one of two ways (this is a joke I don't
> get, or it's really true), or my pegging bullshit meter is right.
> Could you go into a little more detail?

  It's a joke. WEB technologies is a company which announced a compression
product about a year ago. They claimed that they had "violated the laws
of information theory" (a simple counting argument proves what they claim
was impossible) by producing a compressor which can compress its own
output! Furthermore, the compression was ALWAYS 16:1, no matter what the
input. (that's right, they claimed ALL files of a certain size were
compressible by this ratio)

  Everyone knew it was BS, but BYTE magazine did a story on it which seemed
to enhance its credibility. People called them and tried to get
specs, or demo software but they were given the run around. Finally, WEB
claimed that their engineer had made a mistake and their software wouldn't
do what it claimed. A more accurate and detailed story can be found in
the comp.compression faq.



-- Ray Cromwell        |    Engineering is the implementation of science;    --
-- rjc@gnu.ai.mit.edu  |       politics is the implementation of faith.      --

Actually, anybody with a DOS or UNIX box doesn't need any hard drives.
Each of these operating systems comes with a wonderful device known
as nul: or /dev/null.  It is an infinite storage device to which
you can write unlimited data to.

:-)

(Unfortunatly, they're still working on a way to read from it. :-)