Hacker News Reader

Comment by smtddr | Hacker News Reader

I have a problem with encryption being breakable, regardless of who's doing the breaking. I want encryption to be mathematically solid with the only option being brute-force older-than-age-of-earth time. When we get to quantum computing, then I don't know what we'll do...

View on HN

Quantom computing cannot break all of crypto. Anything based on P!=NP is believed to be secure against quantom computing, and there are several encryption methods backed by P!=NP

> Quantom computing cannot break all of crypto.

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/).

> the ones that CANNOT be done on polynomial time is "NP".

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)

The latter of which sounds suspiciously like what a quantum computer does.

How sure are we that BQP != NP?

We aren't: https://en.wikipedia.org/wiki/BQP

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.

I've seen post-selection demonstrated in a laboratory. It definitely isn't just a philosophical construct, except inasmuch as what it says about time making people want it to be less than real, and logic doesn't work that way.

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.

The latter of which is exactly what a quantom computer does. The problem is that when we make a measurement, we randomly select one of the execution paths and see its result. The problem is that once we make a measurement, we would have to repeat the experiment in order to make another measurement.

Yes, and that part of his comment would also imply P != NP:

> 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).

But we do know that BQP \ P is non-empty, which is what I was trying to say. In fact, factoring large integers lies in BQP \ P, and is also the basis of some commonly used encryption algorithms.

No, we don't know that either. For all we know, we could have BQP = P: today, we don't know any algorithm in P to factor integers, but that's not a proof that it doesn't exist. If we had such a proof, as mcpherrinm points out this would directly lead to a proof that P != NP (since we DO know that factoring is in NP).

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?

Oops... my bad. Sorry.

Everyone focuses on the decrypting power of quantum computing, which is warranted as it will break _modern_ cryptography (in theory). However, think about the encrypting power a quantum computer will have; being able to generate completely random keys among other facets of crypto that seem implausible with modern computers. I think it will just open the door to a whole new science of crypto we haven't reached yet.

The most concerning point is that transitional point where all of the old, quantum breakable, standards are in place when quantum systems roll around.

Either everything will fall apart or we'll have wised up before hand.

We've seen this phenomenon, just on a smaller scale. When an encryption standard is compromised, people either switch to something stronger or face the consequences of essentially leaving their data in the open.

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.

If we get quantum cryptography out the door in a reasonable space of time, then we can do secure one time pad exchanges on there. Doesn't matter what you throw at that, since with the right keys you can derive any message of the same length from it.

Reply on news.ycombinator.com