NODE 21e17704Re: The Halting Problem
peb@PROCASE.COMWed, 12 May 93 13:47:56 PDT
>From mab@crypto.com Wed May 12 13:26:04 1993
>I don't see how determining that a particular string is an encrypted
>message reduces to the halting problem.
Consider that the cyphertext is a program for an abstract machine
called the cyphercracker which returns TRUE if a message is encoded
otherwise FALSE. Such a system for determining message-ness could
take an arbitrary amount of cpu time and no amount of static
analysis could determine the return value quicker.
Paul E. Baclace
peb@procase.com
NODE c3bfd922Re: The Halting Problem
Marc Horowitz <marc@GZA.COM>Wed, 12 May 93 14:49:10 PDT
>> Consider that the cyphertext is a program for an abstract machine
>> called the cyphercracker which returns TRUE if a message is encoded
>> otherwise FALSE. Such a system for determining message-ness could
>> take an arbitrary amount of cpu time and no amount of static
>> analysis could determine the return value quicker.
Nope. Such a system will take no more than O(2^n) time, where n is
the number of bits in the key. You can never do worse than
brute-force. Now, you still might not be able to determine if a
message is encoded, since maybe I was just encoding true random noise
from a radioactive source. And you might have false positives, too,
esp. with one-time pads. But it will always halt. The failure modes
have nothing to do with the halting problem, they have to do with the
fact that is-encoded(message) cannot be formally defined.
Marc
NODE 772e71fdRe: The Halting Problem
Matt Blaze <mab@crypto.com>Wed, 12 May 93 15:46:01 PDT
>>From mab@crypto.com Wed May 12 13:26:04 1993
>
>>I don't see how determining that a particular string is an encrypted
>>message reduces to the halting problem.
>
>Consider that the cyphertext is a program for an abstract machine
>called the cyphercracker which returns TRUE if a message is encoded
>otherwise FALSE. Such a system for determining message-ness could
>take an arbitrary amount of cpu time and no amount of static
>analysis could determine the return value quicker.
>
>
>Paul E. Baclace
>peb@procase.com
>
>
Well, that formulation is a bit fuzzy, but I think you've got your reduction
technique backwards. To reduce something to the halting problem, you
need to show that you could use a machne that solves your problem to solve
halting, not the other way around.
-matt