The issue to me has always been how and what data they access and store, and how it is used.
I draw the line at collecting everything without specific warrants, regardless of what they do with it, against their charter and the Constitution.
I draw the line at hardware backdoors for equipment that I buy, and insertion of vulnerabilities into encryption standards that I take advantage of. Or I guess I should say that take advantage of me.
I'm quite opposed to what the NSA has done - but I don't see anything happening that will change it. If the recent revelations haven't done anything to stir Congress to action I don't know what will. Additionally, until and/or unless the NSA ever uses data collected this way against an American citizen in a judicial/criminal way, the courts are quite likely to find that petitioners lack any standing.
So - yes, my most immediate legal concern is how the US government could use the data collection against me contrary to protections given. That doesn't mean there are many more and larger concerns to be thought through, I was merely speaking to one of them.
Their "breaking" of encryption is a combination of purposefully introducing vulnerabilities into standards, surreptitiously altering software and hardware to give the NSA a backdoor, hacking into private systems and stealing keys, etc etc.
I'm cool with an NSA super computer trying to brute force my VPN traffic to YouTube, I'm not cool with the NSA planting an engineer at a chip fab and changing designs to add a backdoor (a backdoor that could also be exploited by other actors).
If the NSA recommends AES to the US government, but knows there's a vulnerability, then they have to assume that any adversary may be as good as whoever designed it. Which means an adversary would be perfectly capable of discovering and exploiting the weakness. Which in turn means the NSA has just made the entire US government vulnerable to foreign or non-state actors.
The same applies to anything you might imagine doing to chipmakers. Not only is there the risk of being found out (how do you explain to a talented engineer spotting a flaw in a schematic, how high up do you have to go to try and stop that leaking?) but there's the more serious risk that you've just added a backdoor to hardware you yourself need to be secure. Which again, could be discovered by an adversary and used against you.
This whole line of argument has always been speculative fiction on the part of the internet: it's looking for unicorns because you heard hoofs.
Did you read the article?
> By this year, the Sigint Enabling Project had found ways inside some of the encryption chips that scramble information for businesses and governments, either by working with chipmakers to insert back doors or by surreptitiously exploiting existing security flaws, according to the documents.
Seems pretty cut and dry.
Yes, and it says this in the article.
And it makes perfect sense too. If you were the NSA, wouldn't you want a heads up if someone was talking about budget cuts?
The leaked documents confirm that this is exactly what happened.
1. They obviously can't keep their own secrets, so it's unlikely that they will do any better than keeping yours. Eventually, your data will leak out to non-NSA people.
2. By adding backdoors, they weaken the encryption. This implies that anyone with sufficient skill who goes looking for backdoors may be able to exploit the hole that the NSA opened up. This is a big deal, especially if you have secrets that you need to protect.
Correct (except for the spelling of "Quantum").
> Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP
Incorrect, well mostly. The deal is that there are problems that can be done in "polynomial time" (how long it takes is not exponential in the size of they key) for a normal computer (or person); the set of these is called "P", the ones that CANNOT be done on polynomial time is "NP". And there are problems that can be done in "polynomial time" (with reasonable limits on errors) by a quantum computer; the set of these is called "BQP". If P = BQP it would mean that quantum computers can (in reasonable time) solve all the same problems that classical computers can. But in fact, P is a subset of BQP: there are problems that are "hard" for classical computers but "easy" for quantum computers.
An example of this is factoring numbers. Shor's algorithm is a way to factor numbers using a quantum computer and it runs in polynomial time. Now it isn't practical today: the biggest quantum computers in existence are hard put to factor the number "10", much less some 40-digit monstrosity. But computers only get better.
Fortunately, there are problems which are NOT in BQP -- problems that are hard even for quantum computers. And these are the ones you want (not those in NP) if you want to stymie a quantum computer.
For more details, see http://www.scottaaronson.com/papers/bqpph.pdf or frankly ANYTHING written by Scott Aaronson (http://www.scottaaronson.com/blog/).
I see you've solved one of the great open problems!
NP is defined as problems that a nondeterministic turing machine can solve in polynomial time. Imagine, if you will, a turing machine that when it "branches" always chooses the right path (Or: chooses "both" without overhead)
> Fortunately, there are problems which are NOT in BQP
We don't know yet if NP \ BQP is non-empty (and neither do we know if BQP \ NP is non-empty).
Also, I don't mean to pile on, but this wasn't what you were trying to say in the paragraph I quoted: in that paragraph, you said that we just had to pick problems outside BQP to make cryptography work despite quantum computers. I don't know if that's what you had in mind, but for such an algorithm to be tractable, it should at least be in NP (nobody with a deterministic computer wants to spend an exponential amount of time establishing an SSL connection): so the mathematical statement is whether NP \ BQP is non-empty. Did I miss something?
How sure are we that BQP != NP?
However a quantum machine that would be capable of post-selection is described by the more powerful class PostBQP = PP, and we know that PP includes NP, so this justifies your analogy.
I don't know much about quantum physics or quantum computing, so I may be mistaken, but it seems to me that post-selection is more of a philosophical construct than something that is physically possible, though.
As for whether you could make a PostBQP-capable computer, though.. I don't think so, at least in the most general case. I don't understand this nearly well enough to be sure, but from what I've heard, tricking causality like that has the problem that you're increasing the chance of your circuitry failing right along with the chance of getting the right result, and quantum computers are already hard enough.
Either everything will fall apart or we'll have wised up before hand.
DES was an acceptable standard until the late 90s, but you'd be foolish to use it now. RSA is the accepted standard now, but it is said to fall within 5 years or so. At that point, people will either start paying for a license to use Elliptic curve encryption algos or something new will be found. It's a vicious cycle, but I certainly don't think encryption ends with quantum computing, but maybe disrupts it quite a bit for some time.