[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: The Halting Problem




>From [email protected] 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: [email protected]

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 [email protected] 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
[email protected]