[318] in Cypherpunks
Re: The Halting Problem
daemon@ATHENA.MIT.EDU (Marc.Ringuette@GS80.SP.CS.CMU.EDU)
Wed May 12 18:46:21 1993
Date: Wed, 12 May 1993 17:34-EDT
From: Marc.Ringuette@GS80.SP.CS.CMU.EDU
To: cypherpunks@toad.com
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)
