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
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
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
participants (3)
-
Marc Horowitz
-
Matt Blaze
-
peb@PROCASE.COM