Let me take the examples already given. I should say I have no idea if the NSA knew about them pre-publication or not.

Shor’s algorithm. Surely the NSA would have taken the view that this posed no immediate threat. 20 years later there are still respectable academics who seem convinced that it will never pose a serious threat.

Quadratic sieve (1981 according to wikipedia). RSA-129 was cracked in 1994 using QS.

The number field sieve (1990). Another speed up, and it has been improved after years of refinement. RSA-768 was cracked in 2009.

I don’t think it is fair to say these techniques broke the RSA infrastructure.

I also don’t know what key sizes the US government used in 81 or 90 or what they predicted the abilities of these methods would be. Maybe someone here does.

However, we do know that if an algorithm were published that allowed you to crack RSA-4096, say, on a home desktop, this would fundamentally break the computer security of the US.

]]>Arguably, watching a region 1 DVD of the Matrix in France is less of a risk to national security than being to decrypt military communication.

Of course I agree with you that in some (thankfully not all) disturbing ways the US is fundamentally no different than the USSR.

(I would be very interested to hear what other, perhaps more knowledgeable, people think the NSA would do.)

]]>Thx again. Now it’s time I stop bothering you. One last thing ðŸ™‚ Was L a typo in “if you fix *R* in advance”?

]]>Yes, Josh was talking about Bennett and Gill’s result. As Josh pointed out himself, the reason there’s no contradiction is that “probability 1” is not the same as “all.” If P=NP, and you fix L in advance, then with probability 1 over R, your L will not witness P^{R}≠NP^{R}. On the other hand, with probability 1 over R, there *is* some L that witnesses P^{R}≠NP^{R}. These statements are perfectly consistent.

First he explicits the result: for any countable (computable or not) CâŠ‡AM, if P=NP, the “only” languages that witness the oracle separation P^Râ‰ NP^R are outside of C.

Second he noticed that it sounds like, for any L0 we could consider C=AMâˆª{L0}, and thereby “show” that no L0 realizes NP^Râ‰ P^R, contradicting the well-known theorem. Is it Bennet and Gill he had in mind?

Third, could we reexpressed this result as “if a language does not witness Pâ‰ NP, then it does not witness BPPâ‰ AM”? Isn’t that an immediate proof that AM=NP?

]]>In fact it’s a fun game to speculate what they would do. I suspect they would forcibly bring the person in for a gentle chat. Then sit around in panic meetings trying to work out what to do while you waited for hours if not days. Then they might offer you a highly paid classified job and appeal to your patrotism (assuming you of a nationality they approved of) and if you seemed unkeen they could quietly point out that you would be sent to jail for life if you leaked the factoring algorithm.

What do you think they would do?

]]>Scott, you are fighting a hopeless battle…

]]>