# Encryption v.s. quantum computers

1. Sep 11, 2008

### 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?

Last edited: Sep 11, 2008
2. Sep 11, 2008

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

3. Sep 11, 2008

### ktoz

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.

4. Sep 13, 2008

### Oberst Villa

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

5. Sep 13, 2008

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.

6. Sep 13, 2008

### 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

7. Sep 13, 2008

### peter0302

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.

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.

8. Sep 13, 2008

### Phrak

NMR computers are bit limited.

9. Sep 14, 2008

### ktoz

I'm no expert, but this explanation of one time pads 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.

10. Sep 14, 2008

### f95toli

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 refering to was "ordinary" encryption schemes (hidden key) which can be made 100% secure if the key is as long as the message.

11. Sep 14, 2008

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.

Last edited: Sep 14, 2008
12. Sep 14, 2008

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

13. Sep 16, 2008

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

14. Sep 16, 2008

### peter0302

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.

15. Sep 16, 2008

### f95toli

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.

16. Sep 17, 2008

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 untill you get a 3 letter word like 'one', but you wouldn't know its wrong untill you see that the message doesn't make sence. Am I missing something important here?

17. Sep 17, 2008

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

18. Sep 17, 2008

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

19. Sep 17, 2008

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

20. Sep 20, 2008

### ktoz

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.