peb> It occurred to me that determining whether a set of random bytes is peb> actually a crypto message could be reduced to the halting problem. I think I can prove this can't be done for most kinds of messages. For a wide range of cases we can know trivially that decryption is in NP. The line of reasoning is this: one definition of the class NP is the class of all problems whose solutions can be verified in polynomial time. 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. These conditions are met in the following cases: - Conventional public key encryption - Any cryptosystem with a short key and a space of allowable messages which is sparse enough that there's a low probability of two messages corresponding to the same ciphertext. This includes most cases in which a digital signature or CRC is added to the end of a message. -- Marc Ringuette (mnr@cs.cmu.edu)