From pmetzger@lehman.com Wed May 12 15:28:22 1993

you missed the word "particular".

Well, I was considering this an unknown--that is, the cryptoanalyzer does *not* know the particular Turing machine, so it is an arbitrary machine, although the program is finite. That is, I am suggesting a decrypt-machine that is turing-complete, however, as:

From: Marc.Ringuette@GS80.SP.CS.CMU.EDU

points out:

So for any encryption method which allows the recipient to verify in polynomial time that his decryption is the only possible intended message, we know that the decryption problem is in NP.

a practical crypto algorithm must allow decrypt in P time and since NP problems do theoretically halt, then the halting problem is not a blanket defense. The realities Brian.Hawthorne@East.Sun.COM mentions are all too real: Anonymous remailers could be effectively broken by requiring tracability (say, they way banks must fill out special forms for any transaction over $10k (which is why Oliver North sent money to the Contras in $9.7k packets)); in the same law, the remailer would be shut down if it did not comply. I think the widespread use of video phones would make steganography easier, however. Paul E. Baclace peb@procase.com