The Halting Problem

[Marc.Ringuette at GS80.SP.CS.CMU.EDU]

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 at cs.cmu.edu)