Re: The Halting Problem

[Matt Blaze <mab@crypto.com>]

>
>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
>peb@procase.com
>

I don't see how determining that a particular string is an encrypted
message reduces to the halting problem.  For an arbitrary cipher, you can't
prove anything about any given potential ciphertext, since the cipher
could be a one-time pad.  (for one time pads, where keylength=message length,
any string can encrypt to any other string by selecting the right key).
So it's true that you can't prove anything about arbitrary ciphertext, but
that doesn't involve the halting problem.  If the cipher is known, on the
other hand, there are perfectly deterministic methods to determine whether
a particular ciphertext may coresponds to some given plaintext, simply
by exhaustive search of the keyspace.

However, I do agree with your basic conclusion - there is no way to determine,
by the bitstream alone, whether something has been encrypted with an arbitrary
cipher.

-matt