From: peb@PROCASE.COM
Date: Wed, 12 May 93 17:01:21 PDT
To: cypherpunks@toad.com
Subject: Re: The Halting Problem
Message-ID: <9305130000.AA09703@banff>
MIME-Version: 1.0
Content-Type: text/plain



>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