The Halting Problem

[Timothy C. May]

>It occurred to me that determining whether a set of random bytes is
>actually a crypto message could be reduced to the halting problem.
>Given this, it would be theoretically impossible to prove that an
>uncrackable message was indeed a crypto message.  The revelation here
>(for me, anyway) is that if arbitrary crypto were made illegal, the
>burden of proof would be on the prosecution which would have to crack
>the message (at least partially).
>
>Paul E. Baclace

Sorry I was out today and missed the halting problem debate!

Paul's intuition (or perhaps proof) is correct, at least according to a
paper Len Adleman wrote some years back, showing this. (I don't have the
paper, but I heard Len describe the results at the Crypto '88 Conference.
As with most such results, the result probably depends on a very careful
statement of what the terms mean, so take my comments as being only
indicative of the flavor of the results.)

What follows is not from Adleman's talk or paper, but from information theory.

The Kolmogorov-Chaitin view of "randomness" is very similar in spirit: how
does one know whether a sequence/string is "effectively random" (short
definition: effectively random means there is no shorter description of a
sequence than itself) or is instead describable by some shorter sequence?
Thus the string "31415926535897932384626433" is recognizable to most agents
(people, smart programs) as the first 25 digits of pi (however, it *could*
be something else, but I won't get into that right now). But the string
"67902371045873651853" is probably not recognizable as anything other than
this string.

Kolmogorov complexity is defined as the length of the shortest programs
which can generate (print) the object. Thus, "alternating 1s and Os" is
very short, "the digits of pi" is slightly longer, and the digit mentioned
above ("679023...") may not have any shorter program than itself. (The
famous Berry Paradox enters here: "The shortest not nameable in under ten
words." Does this number exist? If so, what is it?)

Finding the generating program is very similar to decrypting a message (I
suspect there's a way to formalize the equivalence of encryption and
Kolmogorov complexity, beyond this admitted hand-waving, but I don't know
it offhand). Strings or expressions which "appear" random but which are
actually very regular, or easy to describe, with the proper "key" are
called "crypto-regular." Encrypted messages are clearly crypto-regular.

Cover and Thomas, in "Elements of Information Theory," 1991, write: "One of
the consequences of the non-existence of an algorithm for the halting
problem is the non-computability of Kolmogorov complexity. The only way to
find the shortest program in general is to try all short programs and see
which if them can do the job. However, at any time some of the short
programs may not have halted and there is no effective (finite mechanical)
way to tell whether they will halt or not and what they will print out.
Hence, there is no effective way to find the shortest program to print a
given string."

(By the way, exhaustive search of a keyspace--as someone suggested--is also
not enough, as the cryptostring above (""679023...") may result in several
syntactically valid English expressions, such as "attack at dawn," "whopper
with fries," "robins migrate peripherally." Knowing when to stop further
crypanalysis of a message might be called the "crypto halting problem.")

Fascinating stuff!  (To my current thinking, the core of the universe!) I
recommend Gregory Chaitin's "Algorithmic Information Theory" and
"Algorithms and Randomness." And the Cover and Thomas book.


A (mundane) consequence for cypherpunks is that the sending of any
random-looking stuff may be banned, someday. (No doubt it is in many
countries, if they bother to look. Sending unreadable stuff is grounds for
a visit by the Federales.) 

And clearly even "real messages," like this one, like Peter Wayner's
baseball scores, like GIF images, etc., can have messages attached. If
simple cryptanalysis reveals simple English-like messages, Occam's razor
suggests a decryption has been made. But it can never be known for sure
whether other messages exist.

--Tim May


--
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay at 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^756839 | Public Key: by arrangement