Encryption v.s. quantum computers

[ktoz]

Hi

I've been hearing for years now that quantum computers have the potential to render encryption obsolete. My layman's understanding is that it would do this by taking advantage of the fact that qbits can exist in multiple states not just zero and one.

I imagine there must be some limit to how efficient even quantum computers can be, so was wondering if encryption could be rendered safe with sufficiently large keys? If a quantum computer can make quick work of 512 bit encryption, how about 1 million bit encryption? 1 billion bit encryption? Is there some point where it would take absurdly long times to crack an encrypted message even with a quantum computer?

 

[peter0302]

No. If you were at the point where classical computers were devoting an entire gigabit to an encryption key (which is pretty ridiculous) then there's no reason the quantum computers wouldn't themselves have register sizes of one gigaqubit, in which case the quantum computer will make as short work of your gigabit encryption key as it would have your 512-bit key.

It's the RSA method itself that will be obsoleted by quantum computers. It's not a size issue.

Fortunately, however, quantum computers also provide new means of encryption. Entanglement for example allows you to send messages that are theoretically impossible to intercept - even if you managed to intercept the classical sublight coincidence signal.

 

[ktoz]

No. If you were at the point where classical computers were devoting an entire gigabit to an encryption key (which is pretty ridiculous) then there's no reason the quantum computers wouldn't themselves have register sizes of one gigaqubit, in which case the quantum computer will make as short work of your gigabit encryption key as it would have your 512-bit key.

It's the RSA method itself that will be obsoleted by quantum computers. It's not a size issue.

Fortunately, however, quantum computers also provide new means of encryption. Entanglement for example allows you to send messages that are theoretically impossible to intercept - even if you managed to intercept the classical sublight coincidence signal.

Thanks Peter.

How exactly does a quantum computer crack an encrypted code? I imagine there must be some sort of algorithm and that the algorithm must have some "time to solution" associated with it.

 

[Oberst Villa]

Thanks Peter.

How exactly does a quantum computer crack an encrypted code? I imagine there must be some sort of algorithm and that the algorithm must have some "time to solution" associated with it.

Have a look at Shor's algorithm: http://en.wikipedia.org/wiki/Shor's_algorithm (I can't really comment on the quality of the page because this stuff is way over my head. But it contains a lot of links that might be helpful.)

 

[madmike159]

Why would a quantum computer be able to solve a encryption with a very long length. Surely if it was long enough it wouldn't be able to. My understand ing of quantum computers is limted to the fact that a qubit can exsist in more than one state and not just 0 and 1.

*Edit*
I just had a thought. If you use entanglement to creat a quantum encryption, a normal transistor based computer wouldn't be able to run it. I guess you would just use the quantum computers speed to creat a very long normal encryption.

 

[f95toli]

Well, if you use a key which is as long as the message: No, a quantum computer won't be able to break that code; this is known as "blanket encryption" and is impossible to crack.
However, this is not how most encryption algorithms work; mainly because both the sender and receiver must have a copy of the key; and how do you get the key to the receiver?
In most cases this system is not practical and is only used for VERY secret messages.

Now, most modern encryption schemes get round the problem of key distribution by using schemes that CAN be cracked, it is just very time-consuming. The most famous example is the RSA algorithm which relies on the fact that classical computers are very bad at factorising large numbers.
It is quite easy to show that the time it takes for an ordinary computer to break a code based on this scheme grows exponentially with the length of the key; simply because there are no efficient classical algorithms for factorizing numbers. This means that there is nothing stopping you from using a key so long that it would take even the fastest computer in the world a millions years to crack it (just download the right software, e.g. PGP).

Now, the neat thing with Shor's algorithm (which can ONLY run on a quantum computer) is that the time it takes to factorize a number (and therefore break the code) grows polynomially.
So, yes, using a longer key will mean that it will take more time to break the code even for a quantum computer but the time will still be "reasonable" (or you could use bigger computer).
It would take an ordinary computer millions of years to crack a message encrypted using 1024 bit RSA key (which is the strongest encryption that is routinely used); a "reasonably sized" quantum computer (i.e. something that we think might be possible to build) would -at least in principle- be able to do it in a few years time...

Now, this is still a long time but remember that in MOST cases much shorter keys are used; usually something like 72-168 bits for secure communication over the web; the same quantum computer would crack that code in seconds...

There is a reason why so much of the funding for research into quantum computing comes from organizations like NSA

 

[peter0302]

Why would a quantum computer be able to solve a encryption with a very long length. Surely if it was long enough it wouldn't be able to. My understand ing of quantum computers is limted to the fact that a qubit can exsist in more than one state and not just 0 and 1.

Because the quantum algorithm can crack an encryption key of complexity "n" in log(n) time. Double the complexity and you get a very modest increase in time to solve.

So ok yes, a gigabit key would indeed take longer to solve than a 512-bit key but the computing power of the quantum computer - one would expect - would grow just as consistently as the computing power of a classical computer. So, again, if the classical computer is processing gigabit keys, the quantum computer will probably have no difficulty with them.

Well, if you use a key which is as long as the message: No, a quantum computer won't be able to break that code; this is known as "blanket encryption" and is impossible to crack.

Why would the size of the key versus the size of the message matter?

BTW, anyone see the movie Sneakers? They didn't use a quantum computer to break the codes, but it was the same idea.

 

[Phrak]

NMR computers are bit limited.

 

[ktoz]

Why would the size of the key versus the size of the message matter?

I'm no expert, but this explanation of http://en.wikipedia.org/wiki/One-time_pad" describes why, if the key and message are the same length, the resulting encryption is uncrackable. This is apparently only true though if the key isn't reused. It has to be random and unique for each message.

 

[f95toli]

Why would the size of the key versus the size of the message matter?

Sorry, I should have been clearer.
For RSA it doesn't matter since you are in effect trying to decipher a public key (and once you have that you can decipher any message encrypted using that key). What I was referring to was "ordinary" encryption schemes (hidden key) which can be made 100% secure if the key is as long as the message.

 

[madmike159]

What are the plans for QC's. I guess wen their first invented only NASA, universities and governments would have them, and hopefully they will use them for good (maby not governments). How ever its only a matter of time before some one would be able to buy one and use it for personal gain. Not everyone will get a QC at the same time so that would creat some problems for computer security.

*Edit*
The One Time Pad method isn't completely secure. For that it needs to be truly random, which as far as I know is impossible.

 

[Dragonfall]

The one time pad method is truly secure. And true random sources exist in a lot of places (radioactive decay, microwave background radiation, get a qubit and do Hadamard->measure->Hadamard->measure, etc). In most cases pseudorandom numbers are good enough.

 

[madmike159]

I though that it was impossible. There is another thread discussing if its posible to predict the future if we know everything about a system and all the laws of physics governing it. We can't predict radioactive decay because we don't know everything about the weak force and W and Z bosons (I think...).

 

[peter0302]

The one time pad method is truly secure. And true random sources exist in a lot of places (radioactive decay, microwave background radiation, get a qubit and do Hadamard->measure->Hadamard->measure, etc). In most cases pseudorandom numbers are good enough.

Oh, I see what you're saying. It's not "crackable" in the normal sense because there's no public key to crack.

Even that can be cracked by brute force though. Communications with entanglement, on the other hand, would be totally uncrackable.

 

[f95toli]

Even that can be cracked by brute force though. Communications with entanglement, on the other hand, would be totally uncrackable.

No, brute force won't help. The only reason why you can crack an ordinary (short key) code is because there is some extra information; i.e. key "fits" (gives a sensible answer) when applied to many different positions in the encoded message.
If the key is as long as the message this won't work; it is a bit like trying to solve a system of equations with three unknowns and only two equations; there is an inifinte number of solutions and now way to tell which is the correct one.

Now, quantum encryption is of course not an ideal solution either; it requires perfect equipment (perfect single photon sources, repeaters etc) to be 100% secure and THAT equipment must be secured as well. About a year ago someone published a paper where they "cracked" a code by simply hooking up an oscilloscope to the mains outside the rooms where they kept the transmitting laser; everytime the laser fired the voltage dropped somewhat; this extra information was enough to break the code. I don't know if the same thing could be done with a quantum repeater (presumably not) but it is worth keeping in mind.

 

[madmike159]

Some thing some one pointed out to me confused me. They said that although QC's could brut force an encryption faster than a normal computer, how would you know you got it right? Say I encrypted the word 'run' you could brute force it until you get a 3 letter word like 'one', but you wouldn't know its wrong until you see that the message doesn't make sence. Am I missing something important here?

 

[Dragonfall]

If you mean RSA, then QC's can "brute force" by factoring the public key, which tells you EXACTLY how to decrypt the message. So the ciphertext "run" can be decrypted in only one way, so there's no ambiguity.

What QC (and any computer) can not do is "brute force" a one-time-pad. Because if the key is truly random, then a ciphertext can be decrypted to every text of equal length with equal probability, and you wouldn't know which is the right one.

 

[peter0302]

Correct. You'd have to know something about the contents of the message to know if you got it right.

f95toli's right though. If the key is longer than the message it's impossible to break it. This is because there are more possible keys than there are possible messages. You literally would cycle through all possible messages before you found the right one and you wouldn't know if you found the right one. For example, say you're trying to intercept a message from President Bush, and you search for "Bush" to know if your right. But there are still untold trillions of possible messages that could contain "Bush" in them.

Make sense?

So yeah, if the key is larger than the message, it's always a no-go. But, the whole idea of making a key larger than a message is silly. Such a large key would itself have to be transmitted somehow. If you could intercept the message you could just intercept the key too.

 

[Dragonfall]

Yes, but it's possible that you have opportunity for unconditionally secure channels for brief periods of time, during which you can exchange large amounts of key which are stored for later use

For example, you can transmit large amounts of keys through a diplomatic bag (which is expensive), stored for later use.

 

[ktoz]

So yeah, if the key is larger than the message, it's always a no-go. But, the whole idea of making a key larger than a message is silly. Such a large key would itself have to be transmitted somehow. If you could intercept the message you could just intercept the key too.

Not if the key was never transmitted.

A dedicated, password protected usb stick or something even more innocuous, with gigabytes of random bits, could be distributed to those who need them and used to encrypt many messages by physically destroying already read sectors. The person using the stick could be captured and tortured but if you build in a simple self destruct, at the first sign of danger, the person could just press a button to melt the chip.

 

[peter0302]

LOL. Ok fine, M.

Whatever. RSA encryption is still the best we've got. It will be many years, maybe decades, before a quantum computer is build that can crack a complex RSA key and by then we will have extremely secure entanglement-based communication.

 

[madmike159]

Not if the key was never transmitted.

A dedicated, password protected usb stick or something even more innocuous, with gigabytes of random bits, could be distributed to those who need them and used to encrypt many messages by physically destroying already read sectors. The person using the stick could be captured and tortured but if you build in a simple self destruct, at the first sign of danger, the person could just press a button to melt the chip.

Thats getting a bit James Bond though:tongue2:

 

[f95toli]

Thats getting a bit James Bond though:tongue2:

But it is how it is done in the real world(well, maybe not with a self-destruct although it wouldn't surprise me, such devices DO after all exist).
The system is very simple: measure "noise" from a suitable source (e.g. thermal noise from a resistor should work), burn the recorded signal on a couple of CDs/DVDs. Keep one set and send the other with courier to e.g. an embassy.
There is nothing "James Bond" about it, this has been routine for a very long time (although before digital media code books were used) but is of course only used for very sensitive information.

 

[madmike159]

Yea the self-destruct bit is what I was on about. I suppose they had to get their ideas from somewere.

 

[ktoz]

Thats getting a bit James Bond though:tongue2:

Not in my line of work. I'm Jason Bourne...

 

[ichihollow]

"but if you build in a simple self destruct, at the first sign of danger, the person could just press a button to melt the chip."

being a physics forum and all, anyone know how much force it takes to brake a thumb drive? (chance of breaking THE rom chip?)(chance of being in a situation requiring such tactics?)(chance of having time to push said button, being that if they're going to torture you hopefully they're smart enough to immobilize you before you know they're there?)

other thing to think about, why melt the chip, shorting it should render it useless provided it's still plugged into a USB power source. place button to apply metal square around pins of rom chip, again provided it has/maintains power source, which really isn't difficult to do.

 

[madmike159]

Yes, but it's possible that you have opportunity for unconditionally secure channels for brief periods of time, during which you can exchange large amounts of key which are stored for later use

For example, you can transmit large amounts of keys through a diplomatic bag (which is expensive), stored for later use.

This took a long time for me to get my head round, but I think I know how it would be done now.
QC use QM effects, so you could send you one time pad "key" and the other person could then say they recived it. However if someone intercepts the key it will change, because the uncertainty principal says obsrevation will change the properties (momentum or position). If this happens the key could be sent via a different rout, since the internet is a sparsh mesh.