Re:Nope, wrong, invalid.. nothing to see here.
on
The End of Encryption?
·
· Score: 3, Interesting
Sure there are harder complexity classes than NP, but they are irrelevant to cryptography. The point of cryptography is that for some encrpted message E there is a key K that makes E easy to decode. So the problem is in NP -- the NP machine guesses K and does the decryption. If you make your decryption problem harder than NP, then even with the key it will take a ridiculous amount of time to decode the message.
Here of course I'm talking about public key encryption. The complexity issues are irrelevant to a one time pad, but a one time pad has to be as big as the message. So if you have a channel secure enough to send the one time pad, you may as well sent the message instead.
Sure, you may see some primitive QC within the next 40 years or so. But the probability of you seeing a QC capable of, say, solving Primes in P or one that can play you a DVD is quite low.
Actually, primes is already in P (good old deterministic, non-quantum P, in fact). (See http://www.cse.iitk.ac.in/primality.pdf)
What you meant was "factor in polynomial time"
which is harder than prime testing.
The GOOGLE_LIN and GOOGLE_WTA markets show why
efficient markets need to allow inventors to go short, not just long. The two futures in the GOOGLE_LIN market are complementary: On March 31, 2005, it is certain that IPO_DN + IPO_UP = 1.
So if IPO_DN + IPO_UP < 1, you can make guaranteed money by buying equal numbers of shares of both futures. But right now IPO_DN + IPO_UP = 1.15, so you could make guaranteed money by shorting equal numbers of shares of the two futures. Shorting isn't allowed, unfortunately. All we know is that the fools outnumber the wise, but we don't know who is which.
Likewise the GOOGLE_WTA market is designed so that
IPO_0-20 + IPO_20-25 + IPO_25-30 + IP0_30-35 + IPO_35-40 + IPO_40-45 + IPO_45-50 + IPO_g50 = 1
on March 31, 2005. At present the sum is 1.242,
so again the market on the whole is over bought.
(Which, come to think of it, is likely to be the fate of the Google shares themselves.)
Slashdot Mirror
Sure there are harder complexity classes than NP, but they are irrelevant to cryptography. The point of cryptography is that for some encrpted message E there is a key K that makes E easy to decode. So the problem is in NP -- the NP machine guesses K and does the decryption. If you make your decryption problem harder than NP, then even with the key it will take a ridiculous amount of time to decode the message. Here of course I'm talking about public key encryption. The complexity issues are irrelevant to a one time pad, but a one time pad has to be as big as the message. So if you have a channel secure enough to send the one time pad, you may as well sent the message instead.
The GOOGLE_LIN and GOOGLE_WTA markets show why efficient markets need to allow inventors to go short, not just long. The two futures in the GOOGLE_LIN market are complementary: On March 31, 2005, it is certain that IPO_DN + IPO_UP = 1. So if IPO_DN + IPO_UP < 1, you can make guaranteed money by buying equal numbers of shares of both futures. But right now IPO_DN + IPO_UP = 1.15, so you could make guaranteed money by shorting equal numbers of shares of the two futures. Shorting isn't allowed, unfortunately. All we know is that the fools outnumber the wise, but we don't know who is which.
Likewise the GOOGLE_WTA market is designed so that IPO_0-20 + IPO_20-25 + IPO_25-30 + IP0_30-35 + IPO_35-40 + IPO_40-45 + IPO_45-50 + IPO_g50 = 1 on March 31, 2005. At present the sum is 1.242, so again the market on the whole is over bought. (Which, come to think of it, is likely to be the fate of the Google shares themselves.)