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