×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Quantum Computing Not an Imminent Threat To Public Encryption

Soulskill posted more than 6 years ago | from the in-search-of-schrodinger's-catastrophe dept.

Encryption 119

Bruce Schneier's latest blog entry points out an interesting analysis of how quantum computing will affect public encryption. The author takes a look at some of the mathematics involved with using a quantum computer to run a factoring algorithm, and makes some reasonable assumptions about the technological constraints faced by the developers of the technology. He concludes that while quantum computing could be a threat to modern encryption, it is not the dire emergency some researchers suggest.

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

119 comments

So how do you encript ..... (-1, Offtopic)

3seas (184403) | more than 6 years ago | (#22836336)

..first post?

Re:So how do you encript ..... (0)

Anonymous Coward | more than 6 years ago | (#22836378)

loser....

And the answer is ..Re:So how do you encript ..... (2, Funny)

3seas (184403) | more than 6 years ago | (#22836548)

you disconnect it. First posts are encrypted by mod down, taken out of sight.

The best encryption is disconnection. Its unbreakable even by quantum computers to the nth power.

the next best is perhaps a sequence of seemingly unrelated actions followed by a false positive... or other such use of seemingly unrelated data/actions.

A few might remember the seemingly different things you could do to cause a developer hidden message to come up on the Amiga.

   

Re:And the answer is ..Re:So how do you encript .. (1)

bh_doc (930270) | more than 6 years ago | (#22840900)

The best encryption is disconnection. Its unbreakable even by quantum computers to the nth power.
Unless someone has entangled all your bits with their own, and reads them at a distance.

(No need to point out technicalities. I'm joking.)

Schneier knows his stuff (3, Informative)

CRCulver (715279) | more than 6 years ago | (#22836360)

While I'm critical of Schneier's work in general security consulting, he is still a god in the cryptography world. His book Practical Cryptography [amazon.com] is a friendly guide to encryption that doesn't assume too much knowledge of the heady math involved. Plus, the man invented Blowfish, one of the most popular and fast algorithms around.

Re:Schneier knows his stuff (5, Informative)

CRCulver (715279) | more than 6 years ago | (#22836376)

Uff, I meant Applied Cryptography [amazon.com] . Practical Cryptography is a bit too basic an overview written with a co-author.

Re:Schneier knows his stuff (0)

smilindog2000 (907665) | more than 6 years ago | (#22836656)

I love that book. It's an absolutely great read, and just reading this one book, you get to join the elite club of people who aren't completely ignorant about cryptography (but you still don't get to actually be considered knowledgeable about it).

Quantum computers being able to factor big numbers is the best proof I've seen that factoring is not NP complete. If it were, we could just use these futuristic quantum computers (I'm talking far-future, many thousands or even millions of qbits) to solve just about anything. The darned things would be like oracles, just ask them any super hard question, like how to prove Fermat's Last Theorem, and they'd just spit out the answer. The things would be like talking directly to God. Is that even remotely possible? I don't think so. Factoring numbers is just not as hard as any NP complete problem.

Re:Schneier knows his stuff (4, Insightful)

gomiam (587421) | more than 6 years ago | (#22837264)

Perhaps you would like to read again what NP-complete [wikipedia.org] means: being able to quickly check (read: in polynomial time) whether a solution is right or not by using a deterministic algorithm. Quantum computers are non-deterministic, and that's why they can be used to factor large integers. "Check all periods of r so a^r=1 (mod N) at the same time" certainly isn't deterministic.

The darned things would be like oracles, just ask them any super hard question, like how to prove Fermat's Last Theorem, and they'd just spit out the answer. The things would be like talking directly to God. Is that even remotely possible? I don't think so. Factoring numbers is just not as hard as any NP complete problem.

You might as well conclude that grass is purple, for all the sense that paragraph makes.

Re:Schneier knows his stuff (1)

cnettel (836611) | more than 6 years ago | (#22837544)

If you can check a single solution in polynomial time (i.e. the problem is NP-complete), and have a computing device performing the equivalent of testing all (the exponential number of) combinations at the same time, then you can solve an NP-complete problem. It is "just" a matter of encoding the process of checking an individual solution in a manner that is compatible with the quantum realization used.

Re:Schneier knows his stuff (2, Informative)

smilindog2000 (907665) | more than 6 years ago | (#22837724)

Actually, quantum computers don't work quite like that. The result of a quantum computer computation is the superposition of all the possible results. At the end, you have to collapse the wave function, and you wind up with a specific result, randomly from all the possible results. To factor large integers, you have to rotate the cubits 90 degrees after doing the computation, and somehow that's similar to doing an FFT. If you run the computation many times, statistically you get results bunched into clumps, and the distance between clumps tells you what the factor is.

There's no evidence to date that a quantum computer can be used to solve NP complete problems, and most people seem to think factoring is in a class in between P and NP-complete [scottaaronson.com] .

Re:Schneier knows his stuff (2, Interesting)

CreateWindowEx (630955) | more than 6 years ago | (#22838240)

I think the other posters don't seem to understand the difference between NP and NP-complete. NP complete means that in addition to the answer being verifiable in polynomial time, solving *any* NP-complete problem in polynomial time would provide a polynomial-time solution to all other NP-complete problems. Factoring is in NP, but nobody has yet proven that it is NP-complete. Thus, traveling salesmen and knapsack packers won't be putting quantum computers on their wish lists...


While solving NP-complete in P time with a quantum computer sounds insane, I still find even the factoring thing pretty creepy. I suppose it is really just bringing in all the crazy truths of quantum mechanics up into the human scale where we are forced to deal with their strangeness directly. I still harbor a secret hope that someone will discover that a quantum computer needs energy proportional to 2^N (N = number of qubits), thus making them no more powerful than a classical computer. I have zero evidence to back this up, though!

Re:Schneier knows his stuff (3, Informative)

Fanro (130986) | more than 6 years ago | (#22837784)

I think you are mistaken. It has been a while, but I remember NP like this:

What you described is the property "NP-hard".
For a problem to qualify as NP-complete, it is also neccessary that an algorithm that can solve this problem can also be used to solve every other NP-hard problem, with only an additional transformation of its input and output in polynomial time.

Prime factoring is not NP-complete. There is as far as I know no transformation for the input and output of a prime-factoring algorithm, that would allow it to solve other np-hard problems as well.

If prime factoring was np-complete, then since a quantum algorithm is known for it, it would be certain that a quantum computer could also solve all other np-hard problems.

As far as I know, no quantum algorithm with polynomial time has been found for any NP-complete problem. So we do not know whether a quantum computer could do this

Factoring IS NOT NP COMPLETE (2, Informative)

wurp (51446) | more than 6 years ago | (#22839202)

Parent post is absolutely correct; grandparent is absolutely wrong.

Read Scott Aaronson's blog [scottaaronson.com] to get a clue about quantum computing.

Also read about Schor's algorithm, which is the known algorithm to factor large numbers in log(n) time *if your quantum computer has enough entangled qubits to represent the number*. Again, though, remember that FACTORING IS NOT NP COMPLETE, only NP hard. Other NP hard problems are harder than factoring (for example, any NP complete problem ;-).

Also read about Grover's algorithm, which is a general algorithm to solve NP complete problems, and which HAS BEEN PROVEN TO BE THE FASTEST way to solve the NP complete problem of lookup in an unordered dictionary. Grover's algorithm finds the answer in n^1/2. Obviously if the fastest algorithm to solve a specific NP complete problem is n^1/2, you cannot have a way to solve all NP complete problems in log(n).

Look up Grover's algorithm and Schor's algorithm on Wikipedia, and you'll see that the GP is speaking beyond his knowledge.

I should say that I also made the mistake of thinking factoring was NP complete, and made a fool of myself on Scott's blog before the many, many people more knowledgeable than I about QC on that forum corrected me.

Re:Schneier knows his stuff (1)

smilindog2000 (907665) | more than 6 years ago | (#22837838)

I understand what NP-complete means... In this case it means we can use traditional computers to convert any NP-complete problem into a factoring problem in polynomial time, assuming we can prove that factoring is NP-complete (which it is almost certainly not). Then, since quantum computers can solve the factoring problem, we'd get the answer to any NP-complete problem we pose. There are problems harder than NP-complete, but many common ones, including large classes of automated theorem proving, are NP-complete. A quantum computer capable of solving MP-complete problems would be so powerful, it would seem more than intelligent. It would be able to find globally optimal solutions that humanity could never find otherwise, not with all our computers together, not for centuries. For example, consider chip design. We could pose chip design as an NP-complete optimization problem: what is the smallest chip we can build to implement a specific netlist. A quantum computer with enough qbits which is capable of solving any NP-complete problem could be used to answer this question optimally. It could literally cut tens of man-years off of some chip design projects, while yielding a far superior (in fact optimal) results. Such a computer would change the world. I consider this a contradiction... the existence of such a computer violates my sense of reality. It is far easier to believe that factoring is indeed not quite as hard as NP-complete problems.

Re:Schneier knows his stuff (1)

gomiam (587421) | more than 6 years ago | (#22838430)

I consider this a contradiction... the existence of such a computer violates my sense of reality. It is far easier to believe that factoring is indeed not quite as hard as NP-complete problems.

Got a couple of spares? Your sense of reality seems to be a bit faulty. We already have seen those cut-offs before: they happened when someone decided a computer was a good enough tool to design chips instead of using pencil and paper. Anyway, this is not a mater of something being "easier to believe": either factoring is NP-complete, it isn't, or we can't decide. There is no belief required. Deciding that, because we don't yet know whether quantum computers can factor integers in polynomial time or not, they can't and quantum computer doesn't work is ... let's say illogical. Then again, if you are happy jumping to conclusions like that...

Turning back to the debate at hand, if factoring isn't NP-complete, does that mean it is harder than NP-complete problems, easier or what?

Re:Schneier knows his stuff (1)

smallfries (601545) | more than 6 years ago | (#22838438)

Perhaps you would? You've post a link to wikipedia as an appeal to authority but you've misquoted the page and butchered your definition of NP-c. The only reason that you were modded insightful is that the average slashdotter with modpoints doesn't understand the difference.

It's not hard to follow; if I give you a candidate solution to a problem and you can check quickly if it is true or not (i.e. in poly-time) then the problem lies in NP. So all problems in P lie within NP. Some problems in NP are harder than others i.e. 3-sat. If any single one of those problems can be reduced to the problem being discussed (in poly-time) then then it is complete within NP - it is one of the hardest problems in NP.

The poster than you were replying to was pointing out (in terms that you didn't understand, I suggest you read his reply closely) to you that the difficulty of factoring is not related to the difficulty of NPc problems. He is entirely correct, not only is there no theoretical basis for relating the hardness of the problem but if you have spent any time working on NPc problems, and on factoring you would understand that they are very different.

Finally, quantum computers cannot (currently) factor large integers. It is silly for you to make that claim in a discussion about whether or not QC would ever scale to large problems at all. Also the integers that they can factor are not a direct result of their non-determinism. Don't forget that we can run non-deterministic algorithms on devices other than QCs.

Re:Schneier knows his stuff (1)

randomplanck (1069958) | more than 6 years ago | (#22839052)

I am just curious - why can't we use the new quantum computing technology to make even better encryption algorithms that are in turn hard to break with quantum computers?

Re:Schneier knows his stuff (0)

Anonymous Coward | more than 6 years ago | (#22839208)

Actually, perhaps you should try to understand a post before you dismiss it. The post you are bashing is quite correct: computer scientists consider factoring being in BQP (problems with polynomial quantum algorithms) to be good evidence that factoring is not NP-Hard.

Why? Simple. If factoring were NP-Hard that would imply that NP is in BQP. This is strongly suspected to not be the case. I could point you to a whole myriad of sources. It just happens that there is a really easy to read article on this subject in this month's Sci Am. I suggest you pick it up.

Sincerely,
An Anonymous Coward with a PhD in Quantum Computation

Re:Schneier knows his stuff (0)

Anonymous Coward | more than 6 years ago | (#22836492)

To be honest, I feel slightly smarter after reading that piece of his. I consider myself an intelligent person, but every once and a while TFA goes over my head :/

Thank goodness for laments terms.

Re:Schneier knows his stuff (2, Insightful)

insertwackynamehere (891357) | more than 6 years ago | (#22836568)

Layman's terms?

Re:Schneier knows his stuff (5, Funny)

rucs_hack (784150) | more than 6 years ago | (#22836618)

Your data is both encrypted and unencrypted at the same time, only reverting to one state or the other when you observe it and collapse the waveform. There is also, if I read this correctly, some chance that it will turn into a cat.

Hope that clears it up for you...

Re:Schneier knows his stuff (1)

gomiam (587421) | more than 6 years ago | (#22837292)

There is also, if I read this correctly, some chance that it will turn into a cat.

But you won't know if it's alive or not until you look inside the box.

Brilliant explanation... (1)

Joce640k (829181) | more than 6 years ago | (#22838492)

Now how would you explain it to magazine editors who keep writing articles on how quantum computing is the future of gaming?

Re:Schneier knows his stuff (1, Informative)

Anonymous Coward | more than 6 years ago | (#22836610)

I kinda disappoint when I read the article, specifically the part that he claim that we need 5 trillion gate to implement Shor's algorithm. Quite surprise that Mordaxus can not differentiate between a program and a hardware that run a program.

The name "quantum gate" is quite misleading, and that may be the reason why Mordakus mis-understand. It's actually means quantum operation. Shor's algorithm requires 72k^3 quantum gates, is means requites 72k^3 quantum operations. It does not means we need to build a quantum computer with 72k^3 gates. That more like you build one CPU, one piece of hardware that execute one program.

What is the technical challenge is, we need to be able to build quantum computer that big enough to hold "k" qubits, and technique that apply "quantum gate" (meaning executing quantum operation). So, the Quantum CPU may
not need 5 Trillion qubits, but much be able to apply quantum operation on k qubits. The important point is Shor's algorithm is O(k^3), a polinomail time algorithm, which is fast!

Re:Schneier knows his stuff (5, Interesting)

letsief (1053922) | more than 6 years ago | (#22836614)

Bruce didn't actually write that article. He only linked to it on his blog, which isn't particularly relevant. And, although Bruce is a brilliant cryptographer, he doesn't know squat about quantum computers, nor does the person that wrote that article. One of the most glaring errors is corrected in comment posted on the article page. Besides that, his argument isn't completely sound. The biggest problem with quantum computers isn't managing to build one with a tons of quantum gates, it's getting the error rate down on the components. If you do that, you ought to be able to build as many gates as you want with enough effort and money. The author's argument seems akin to saying we couldn't possibly build a 100-billion transistor count processor today. We could, its just going to be very expensive and you're not going to mass-produce it.

Right now a lot of people working in the field say quantum computers are about 40 years off. The scary thing though is how its likely to play out. For a few decades quantum computers will likely remain "40 years off" (in the fusion sense), but then someone is going to figure out how to get the error rates below threshold, and then quantum computers will be only 10 years away. That doesn't give us much time to stop using our favorite public key algorithms. That's too bad for nTru; (they have a public key system that is likely resistant to quantum computers), their patents will be long expired.

Re:Schneier knows his stuff (0)

Anonymous Coward | more than 6 years ago | (#22837150)

CRCulver (715279) just keeps pre-canned rants in his head that trigger when he sees a keyword. Today an eulogy for "Applied Cryptography" got triggered by the keywords "Bruce Schneier" even though Bruce isn't particularly relevant to this story as you said. Yesterday he posted a rant against light pollution [slashdot.org] that was triggered by the keyword "streetlight" even if it was just a library-of-congress-type comparison, and the story had nothing to do with outdoor lighting.

Ignore CRCulver, he's a keyword-triggered state machine that fires Amazon links without thought or judgement.

Re:Schneier knows his stuff (2, Informative)

SiliconEntity (448450) | more than 6 years ago | (#22838342)

Please mod parent up. He makes two excellent points: 1st that Schneier did not write the essay and basically has nothing to do with it. And 2nd, that the essay is completely wrong, as pointed out by the 1st comment replying on the essay page. Shor's algorithm will not take 72*k^3 qubits or gates, it takes about k qubits and then goes through O(k^3) steps to get the answer. Everything about the posting is wrong.

Re:Schneier knows his stuff (1)

wwphx (225607) | more than 6 years ago | (#22836992)

It should be noted that this is not Schneier's writing, this is just a blog post that he posted about in his blog. He may find it interesting and noteworthy, but it is not his material.

Re:Schneier knows his stuff (1)

DaleGlass (1068434) | more than 6 years ago | (#22837020)

Out of curiosity, what do you think is wrong with Schneier's work in security consulting?

Re:Schneier knows his stuff (0)

Anonymous Coward | more than 6 years ago | (#22837736)

Out of curiosity, what do you think is wrong with Schneier's work in security consulting?

If he doesn't reply it's most likely because he couldn't figure out how to work an Amazon referrer link into it.

Re:Schneier knows his stuff (1)

0ptix (649734) | more than 6 years ago | (#22839664)

actually thats not completely true. in the security world he might be highly regarded but in the crypto world things are... different. look at a list of his publications [uni-trier.de] . Most all are at security conferences. For that matter since 2005 he has published one paper. He has only ever published 2 papers at Crypto, 1 at Eurocrypt and none at TCC. (These being the most selective conferences in the crypto community.) Nor does he have any papers at PKC, CHES, RSA, SCC, Asiacrypt, CSN, and only one paper at Fincial Cryptography which are some second and third tier conferences.

The main exception are his FSE (fast software encryption) papers but here too it's since 2000 he's only produced 1 paper and that had 6 authors. However before that (in the 90s) he did have a string of relatively interesting papers related to cryptanalysis mainly together with John Kelsey who is a much more prolific cryptanalyst even in recent years. For example he has 5 papers in Eurocrypt and Crypto. As a measure of FSE vs. Crypto also for the field of cryptanalysis, the major MD4, MD5, SHA-0 and SHA-1 breaks were all published at Crypto.

Basically what i'm saying is that he is great in security and even respectable in the most practical corner of crypto. But there are many many people out there who have a much more impressive track record as far as pure crypto is concerned.

I guess the best testament to how seriously some people out there take him would be this collection of useful facts [geekz.co.uk] .

not exactly a "threat" (3, Insightful)

pedantic bore (740196) | more than 6 years ago | (#22836362)

... more like guaranteed employment for security experts everywhere!

The day PKIs that use factoring or discrete logs become easy to crack is the day when there's going to be a lot of tremendous amount of money spent on stop-gap security measures until someone figures out something new...

Re:not exactly a "threat" (1)

CRCulver (715279) | more than 6 years ago | (#22836410)

The day PKIs that use factoring or discrete logs become easy to crack is the day when there's going to be a lot of tremendous amount of money spent on stop-gap security measures until someone figures out something new...

I imagine one-time pads will come back in style.

Re:not exactly a "threat" (3, Insightful)

owlstead (636356) | more than 6 years ago | (#22836530)

The day PKIs that use factoring or discrete logs become easy to crack is the day when there's going to be a lot of tremendous amount of money spent on stop-gap security measures until someone figures out something new...

I imagine one-time pads will come back in style.

One time pads are replacements for symmetric encryption (both sides use the same key), not asymmetric encryption. You cannot authenticate a server to multiple clients using one time pads for instance. Everybody would have the one time pad, so everybody could pose as the server. Anyway, there *are* asymmetric algorithms that should be safe against crypto analysis using quantum computing. There is no need to go distributing Blu-Ray disks filled with random valued bits (one disk per application and user) just yet.

Re:not exactly a "threat" (3, Informative)

letsief (1053922) | more than 6 years ago | (#22836740)

There's certainly no reason to go back to one-time pads. Basically all of the symmetric encryption algorithms are (mostly) quantum resistant. But, you do get a square root speed-up for attacking symmetric systems by using Grover's algorithm on a quantum computer. So, if you want to make sure you're still safe, you have to double your key length. That's not so bad, and certainly much better than using one-time pads. And, as you said, there are asymmetric algorithms that should be resistant to quantum computers. McEliece is an early public key encryption algorithm (with sort of ridiculous key lengths) which is probably safe, although you can't do signatures with it in a reasonable way. Then, there's nTru's work, which is probably what we'd use if someone figured out how to build a quantum computer tomorrow. They have encryption and signing algorithms that are reasonably fast.

Re:not exactly a "threat" (1)

MMC Monster (602931) | more than 6 years ago | (#22836918)

I am crypto-tech naive. What's the problem with using one-time pads and having every "relationship" share a pad? (ie: When I open an account with my bank they give me a key-fob with my one time pad on it. When I log into the bank website it uses the pad to authenticate me.) Of course, setting up a relationship will be a bit more expensive...

Re:not exactly a "threat" (1)

kalidasa (577403) | more than 6 years ago | (#22836962)

The problem is all the legacy data drifting around out there on old machines that use crypto systems that can be trivially broken. If you can find a dump of old hard drives that weren't very carefully wiped because "all the data was encrypted," you might have a gold mine.

Re:not exactly a "threat" (2, Insightful)

owlstead (636356) | more than 6 years ago | (#22837056)

"I am crypto-tech naive. What's the problem with using one-time pads and having every "relationship" share a pad?"

Well, just think about all the SSL enabled sites out there, and remember you will now have a N * N (client * server) number of relations that need to setup a symmetric key (which is what a one time pad is, basically). Also note that you don't have a certificate infrastructure, so you cannot just go to VeriSign or any other trusted third party and buy a certificate from there. You cannot download one time pads, because you don't know who it is coming from.

Say you have 200.000.000 client computers in the US alone, and some 5.000 sites with one time pad SSL. Then you have 1.000.000.000.000 relations to set up. Not quite as much as the number of dollars wasted on the war in Iraq, but it's getting there. Of course, you won't use each and every service, but it would take a little bit too much time to exchange disks by post when you are trying to connect to a new service.

Re:not exactly a "threat" (2, Informative)

blueg3 (192743) | more than 6 years ago | (#22837546)

No, this is why you don't use secret key system like 3DES or AES. Essentially, the number of keys you need to distribute scales with the number of pairs of communicating parties. If you have N parties all wanting to communicate with each other, that's O(N^2) keys. This is fairly unlikely, though. If you have, say, S servers (banks, etc.) and C clients, it's more like O(S*C) -- though a client-server pair may separate keys for different tasks.

One-time pads cannot be reused. That's why they're called one-time. This means that the quantity of one-time pad data that needs to be securely shared between two communicating parties is equal to the quantity of data they want to exchange. Say a bank transaction involves communicating 1k of data. The bank needs to give you -- securely -- 1k of OTP data per transaction you'll want to make. Generally, this is inconvenient. Since real one-time pads are unbreakable, this just means the vector for attack is moved somewhere else -- most likely, how you communicate the OTP data. (If someone can impersonate you to a bank employee and get a few transactions' worth of pad, the security of a one-time pad is irrelevant. If you use an existing cryptographic algorithm to exchange one-time pad data, you're wasting time -- simply transmit your real data using this algorithm.) One-time pads have been used, but only in a few specific situations. In general, they're not useful.

Applying a one-time pad to data is generally done by simply XORing the pad (which consists of random bits) with the data. Reusing a one-time pad is incredibly easy to break.

Re:not exactly a "threat" (1, Informative)

TheRaven64 (641858) | more than 6 years ago | (#22837502)

One time pads are basically useless in this scenario. In order for a OTP to be useful for data transfer, you need to exchange a pad of the same size as the message via some secure mechanism. If you can exchange the key securely, then you may as well exchange the data using that mechanism instead. The only time it is useful is for things like military or diplomatic use where the sender and receiver are in the same physical location for a while (e.g. an ambassador before he goes to the embassy) and can securely exchange keys. OTPs do not give you security, they just let you move it around.

Re:not exactly a "threat" (1)

pyite (140350) | more than 6 years ago | (#22837598)

I have no idea why the parent to this post is moderated as troll. It's completely on topic and merely points out the harsh reality of trying to use a one time pad in real life.

You have to get the pads to the other person... (2, Insightful)

Joce640k (829181) | more than 6 years ago | (#22838522)

How are you going to get the pads to the other person? Encrypt them?

If you have a way of transmitting the pads securely then you could just use the same system to transmit the messages - no encryption needed!

Secure asymmetric encryption? (1)

wurp (51446) | more than 6 years ago | (#22839254)

Do you have an example of asymmetric encryption that is secure against quantum algorithm? PK is broken by Schor's algorithm (if you have a big enough quantum computer), and per Scott Aaronson [scottaaronson.com] (an algorithmic complexity professor at MIT), elliptical encryption is also demonstrated to be vulnerable. He appeared to imply in that same discussion that all asymmetric algorithms were vulnerable...

Re:not exactly a "threat" (2, Informative)

mattpalmer1086 (707360) | more than 6 years ago | (#22836696)

Public key crypto solves the main key distribution problem of symmetric crypto. One time pads have the worst key distribution issues of all crypto! So, no, one time pads won't be making any kind of come back due to this.

Re:not exactly a "threat" (1, Informative)

Anonymous Coward | more than 6 years ago | (#22836682)

If it gets easy to break because of quantum encryption, then no problem! There already exists a quantum version of public key encryption. What this means is that in ~30 years, every computer will need, at the very least, a quantum co-processor. No need to panic.
http://www.iacr.org/archive/crypto2000/18800147/18800147.pdf [iacr.org]

Well, lucky for us (1)

Watson Ladd (955755) | more than 6 years ago | (#22836436)

quantum computers fail at NP-hard problems. But no one has made a cryptosystem for which breaking is NP-hard. So the eventual transition is going to be a bit tricky.

Re:Well, lucky for us (2, Interesting)

snarkh (118018) | more than 6 years ago | (#22836726)


As far as I know, it is not known whether quantum computers can solve NP-hard problems in polynomial time. To say that they fail at NP-problems may be premature.

Re:Well, lucky for us (5, Informative)

russotto (537200) | more than 6 years ago | (#22836786)

As far as I know, it is not known whether quantum computers can solve NP-hard problems in polynomial time. To say that they fail at NP-problems may be premature.
Seeing as it hasn't even been proven that P != NP for ordinary computers, it's very premature.

Re:Well, lucky for us (1)

snarkh (118018) | more than 6 years ago | (#22837458)


Well, it is conceivable that NP is solvable using quantum computers in poly time, while pretty much everyone believes that P!=NP for ordinary computors.

Re:Well, lucky for us (1)

Yossarian45793 (617611) | more than 6 years ago | (#22837642)

Wrong. The definition of NP is the class of problems that a nondeterministic Turing machine can solve in polynomial time. P = NP if and only if a deterministic Turning machine can also solve those problems in polynomial time. A quantum computer is NOT a deterministic Turing machine, so P does not have to equal NP for quantum computers to solve NP problems fast.

Re:Well, lucky for us (1)

26199 (577806) | more than 6 years ago | (#22838006)

If quantum computers can't solve problems in NP quickly, then presumably it follows that normal computers can't either.

This would prove P != NP, which hasn't been done. Ergo, it can't have been proven that quantum computers can't solve problems in NP quickly.

Re:Well, lucky for us (0)

Anonymous Coward | more than 6 years ago | (#22837842)

Nonsense. It's quite well known that P = NP for N == 1 or P == 0.

Re:Well, lucky for us (2, Interesting)

Watson Ladd (955755) | more than 6 years ago | (#22836892)

I mispoke. No current algorithms are known for solving NP problems fast with a quantum machine, and it is suspected none exist.But no proof of the converse exists. However, using a nonlinear operator permits NP complete problems to be solved in polynomial time with small error. So it's more pessimistic then I thought.

Re:Well, lucky for us (1)

snarkh (118018) | more than 6 years ago | (#22837486)


I am not sure what you mean by a non-linear operator. Certainly there are numerous ways of approximating various NP problems with different degree of accuracy.

There's nTru (1)

letsief (1053922) | more than 6 years ago | (#22836774)

nTru has signing and encryption algorithms based on the shortest vector problem, which I believe is NP-hard. I don't know if they have a reductionist proof, or if its just based on SVP like RSA is based on factoring. But, they're probably the way to go if someone were to develop a working quantum computer tomorrow.

dongs (0)

Anonymous Coward | more than 6 years ago | (#22836466)

There's a whole class of algorithms for which quantum cryptography isn't very useful.

Those based around multivariate systems of equations (e.g. HFE), coding theory (McEliece and friends) and other esoteric stuff like lattice based systems (NTRU) are pretty much immune to quantum approaches.

It's just a matter of changing the whole infrastructure to something else, not the end of the world.

Re:dongs (2, Insightful)

CRCulver (715279) | more than 6 years ago | (#22836534)

It's just a matter of changing the whole infrastructure to something else, not the end of the world.

Yes, but what about the matters you've already encrypted? Early buzz around PGP was that it would supposedly take millions of years to decrypt even a single message. For those people who encrypted their private communications, it is a big shock that all your secrets may be read in just a few years.

the fear (1, Insightful)

Deanalator (806515) | more than 6 years ago | (#22836494)

I think the fear is that by the time we get around to having decent PKI for stuff like credit cards etc, quantum computing will bust everything wide open. PKI is the only practical method of identity management these days, and while algorithms in the PKI are being tweaked, they are all pretty much based on the same principals, which quantum computing is a real threat too.

"polynomial time" (3, Informative)

l2718 (514756) | more than 6 years ago | (#22836566)

This calculation illustrates a good point about the difference between asymptotic analysis of algorithms and real-world implementation of the same algorithsm. Computer science defines "efficient" as "bounded polynomially in terms of the input size". In practice, even if polynomial has a small degree (like a cubic) it already means that the resource rquirements are very large. Theory and practice are only the same in theory.

Re:"polynomial time" (1, Informative)

Anonymous Coward | more than 6 years ago | (#22836932)

So, you have two algorithms to perform a task. One is n^3, the other is 2^n; the first takes twice the space of the second. If the input size is n > 11, which do you probably want?

Quantum computing is no threat because... (2, Informative)

SIGFPE (97527) | more than 6 years ago | (#22836586)

...the rate of increase of power of quantum computers isn't faster than Moore's law. I've written more on this here [blogspot.com] .

Re:Quantum computing is no threat because... (2, Interesting)

letsief (1053922) | more than 6 years ago | (#22836676)

It's way too early to make predictions based on trends. Quantum computing is in its infancy. We haven't even built anything that could/should really be called a working quantum computer (yes, I know we factored 15). We're going to see revolutionary changes to the field, not just evolutionary. So, every once in a while we're going to see great leaps forward, followed by a period where people just improve upon that idea. Its going to take a lot of revolutionary ideas to get a practical quantum computer, and its nearly impossible to say how long it will take to think of them. Just look at fusion, which now I don't even think anyone bothers to say is "40 years off".

Re:Quantum computing is no threat because... (2, Informative)

ScrewMaster (602015) | more than 6 years ago | (#22837222)

I tend to agree. When promising new technologies take too long to develop, by the time they become practical they are often supplanted by something else. We will have both, since our civilization's need for both more energy and more processing power is going continue unabated for a long time.

We may never have either nuclear fusion or quantum computing, as currently envisioned. As you say, it's impossible to predict. All we can say with some assurance is that we'll probably figure out something that will achieve the same ends.

Re:Quantum computing is no threat because... (1)

SIGFPE (97527) | more than 6 years ago | (#22838864)

Oh no, I wasn't trying to extrapolate based on a trend. I was trying to predict the trend before it even happens using basic knowledge of quantum computing.

What's all this k**3 stuff? (0)

Anonymous Coward | more than 6 years ago | (#22836624)

To multiply 2 numbers together to get a k bit product takes a gate count proportional to k**2.

If you built a multiplyer out of magic logic,
      and constrained the output and enough of the input bits so that there is only one solution,
            then maybe the magic logic could figure out the rest of the multiplyer state.

I don't know if quantum logic can/will be the magic logic,
      but as long as we choose algorithms with only one solution,
            we will have to worry about it.

Encryption will move on, too (2, Interesting)

tringtring (1227356) | more than 6 years ago | (#22836692)

Well, even if it were to be true that quantum computing algos can break the existing encryption algos, I think it is being paranoid for two reasons: (1) Quantum computing is not yet mainstream and I doubt if mischief mongers (aka thieves who wish to break into financial sustems) have the wherewithal today to work with quantum computing algos, and (2) By the time QC moves to anywhere near mainstream, I have little doubt that encryption methods would have handsomely moved along too.

Re:Encryption will move on, too (1)

sempernoctis (1229258) | more than 6 years ago | (#22837192)

(1) Quantum computing is not yet mainstream and I doubt if mischief mongers (aka thieves who wish to break into financial sustems) have the wherewithal today to work with quantum computing algos
Unfortunately, as Aesop put it, "We hang the petty thieves and appoint the great ones to public office." And the highest people on that totem pole have access to the resources of organizations like the NSA, who are on the bleeding edge if not already slightly ahead of it.

Does exist any quantum computer proven to work? (1)

a_claudiu (814111) | more than 6 years ago | (#22836858)

Can somebody with physics background help me? For quantum computers to work you need entanglement and Heisenberg principle.

1. Entanglement. Is this a fact or a theory? Looking on web I found only few experiments with some possible loopholes. I found the principle hard to grok.

2. Heisenberg principle. It mainly states that observing an object you are changing the state of the object. The Heisenberg example from wikipedia is using a photon for measuring the position of an electron and the photon is changing the position of electron. What is happening if you are using a smaller particle that is not impacting the electron so much? Are you going to change the constant? Looks mostly like a limitation from a time when the atom was considered to be indivisible.

I have some background in learning physics in university but I was not very good at it. My personal opinion is that superposition is just a nice way of doing statistics using discrete values for covering the not so discrete results of experiments.

Re:Does exist any quantum computer proven to work? (1)

blueg3 (192743) | more than 6 years ago | (#22837602)

The Heisenberg uncertainty principle isn't really what you mean. Heisenburg states that if two variables (such as position and momentum) have a particular relationship, then you cannot simultaneously measure both of them to arbitrary accuracy. (It places specific limits on the accuracy to which you can measure them.)

To make a long story short, though, both quantum entanglement and the collapse of wavefunctions due to measurement are experimentally-confirmed fact, and small quantum computers have been built.

Your personal opinion sounds like the opinion of many physicists in early quantum mechanics days. It's called a hidden variable, meaning that there is a deterministic process going on that we can't get at, and that superposition is just a convenient statistical model. This was more or less summarized in the EPR paradox. The answer to this was Bell's theorem, which showed, again cutting a long story short, that whether superposition and entanglement were "real" or just hiding some deterministic hidden variable could be determined experimentally. This has been done, and superposition and entanglement are real. (Though Einstein would be happy to know that despite the apparent "spooky action-at-a-distance" of entangled particles, they cannot be used to transmit information faster than lightspeed.)

Re:Does exist any quantum computer proven to work? (4, Informative)

slew (2918) | more than 6 years ago | (#22837628)

I'm afraid you'll have to look those physics books back up.

Although QM computers do use basic entanglement for creating superpositions, understanding Shor's algorithm (the one everyone is concerned about since it's factoring in polynomial time) is mostly just understanding QM superposition. Entanglement gives generic QM computers great parallel processing power by superposition by explaining how QM probability wave combine under superposition, but Heisenberg limits the computing power of a QM computer in a non-trivial way as well because after you collapse the wave functions by measurement you give up the parallel processing enabled by Entanglement (e.g., if you peek inside the oven, it stops working, if some of the heat leaks out of the oven even with the door closed, it doesn't work as efficiently, the oven being the QM computer).

FWIW, Shor's algorithm essentially converts factoring into a sequence period finding exercise. You might imagine that that's something easy to do if you had a machine which given a bunch of superimposed waves with a certain modulo structure could tell you the period (hint the ones that don't modulo with a specific period with self interfere and measure as zero, where the one with that period with self-reinforce). With a QM computer you do this all in parallel with superimposed probability waves and when you measure it, the highest probability one you measure is the one that doesn't self-interfere (the ones that self-interfere has probability near zero). Basically this measurement is wave function collapse which doesn't actually depend on entanglement or heisenberg to understand (although it does require you to believe in QM wave functions and measurement operators).

Entanglement is really a strange artifact of QM that explains probability correlations that you see in QM experiments that can't be explained classically. It's really more of an artifact of the existance of probability amplitude waves (the QM wave function) rather than an effect that directly enables the QM computer. Of course if you didn't have QM wave functions you wouldn't have a QM computer so I guess that's a chicken and egg scenario. Entanglement is like the "carburator" function of the QM computer. The QM computer uses superposition of QM wave functions to work and when you have more than one QM wave function, they get entangled when you start superimposing wave functions and the way the waves entangle helps you compute in parallel so it's important to understand how these waves entangle.

Heisenberg's principle is a consequence of wave function collapse (measurement) which also limits the QM computer (this limiting effect is often called QM de-coherence). Heisenberg isn't required by a QM computer when it's computing, but you need to see the result somehow so when you measure the result, one of the side effects is the Heisenberg principle (although that's also a chicken-egg problem, since HP is a consequence of QM wave function collapse and w/o QM there's no superposition computing). The closest explanation I can think of is that Heisenberg's principle is the "heat" caused by friction of the QM computer. You need friction to stop the computer to read out the result, but at the same time you can't get rid of a little friction while it's running either (causing de-coherence). The side effect of this friction is heat.

You may have a personal opinion that superposition is a "nice way of doing statistics using discrete values for covering the not so discrete results of experiments", but there is experimental evidence that your personal opinions is at odds with physical reality. As QM computers that do QM computing (including IBM's NMR experiment which implemented shor's algorithm) have already been implemented it's hard to refute that something non-classical is going on.

It may be that in the end, QM is total malarky and there's some other weird unexpected thing going on, but there are mountains of evidence that whatever is going on, it isn't as simple as "hidden variables" or "continuous vs discrete".

As with most physics, Entanglement and Heisenberg' principles were originally artifacts of the new QM theory that people thought would be novel (i.e., not able to be explained with the current classical theory). They have however both been experimentally verified to some extent, but generally the verification is statistical in nature and is definitly shown to be non-classical behavior. Like I said earlier, it's possible that something weird and not QM is going on, but it's definitely something.

Today we are interpreting the experimental evidence as being consistant with QM theory which is not consistant with classical theory. Tommorrow, who knows. Science is always about new theories, but it's also a fact that the classical theory doesn't predict what we observe today, so we start with QM as the new starting point.

Don't feel bad about not being able to grok QM. Even Einstien and Feynman basically gave up trying to actually understand or find it intuitive at all and just treated QM as a mathematical theory that happened to explain experimental results.

Re:Does exist any quantum computer proven to work? (1)

a_claudiu (814111) | more than 6 years ago | (#22838434)

Thanks a lot for your response and all the other responses also. I will try to look more into books and entanglement experiments.
My main problem stays in "continuous vs discrete" problem as you mention it. I still believe that the discrete values are just "good values" in a wave equation like "Schrödinger equation" and not really discrete. The main problem as I see it is that "Schrödinger equation" is practically unsolvable using current mathematics and finding a continuous equation is like finding an inverse function of an unknown distribution.
Of course as somebody mention it I'm just a "layperson" but I'm trying to improve.
Thanks again for your responses.

Re:Does exist any quantum computer proven to work? (3, Informative)

Phroon (820247) | more than 6 years ago | (#22837690)

1. Entanglement. Is this a fact or a theory? Looking on web I found only few experiments with some possible loopholes. I found the principle hard to grok.

2. Heisenberg principle. It mainly states that observing an object you are changing the state of the object. The Heisenberg example from wikipedia is using a photon for measuring the position of an electron and the photon is changing the position of electron. What is happening if you are using a smaller particle that is not impacting the electron so much? Are you going to change the constant? Looks mostly like a limitation from a time when the atom was considered to be indivisible.
The Wikipedia entries are written from the perspective of a physicist, so they aren't going to be much use to laypeople.

1. Entanglement: It is fact. If you send a photon through a certain type of non-linear crystal, two photons will emerge that are entangled quantum mechanically. To truly understand this requires some knowledge of quantum mechanics, a basic introduction to QM and entanglement can be found here [ipod.org.uk] and here [davidjarvis.ca] if you care to learn more.

2. Heisenberg principle: You inadvertently stumbled onto the problem yourself, kinda. When trying to measure the position of the electron, you use a high energy photon and this photon. When this high energy photon interacts with the electron it alters the velocity of the electron, so you know less about the velocity of the electron. When trying to measure the velocity of the electron, you use a low energy photon. This low energy photon measures the velocity well, but it moves the electron a little bit, so you don't know its position. This issue is the essence of the Heisenberg uncertainty principle.

Re:Does exist any quantum computer proven to work? (1)

Davey McDave (926282) | more than 6 years ago | (#22837818)

1. From what I've heard, fact. They have very rudimentary quantum computers working. We're talking 4 qubits or so, nothing fancy.

2. The problem with talking about quantum physics is that you deal with principles quite unlike real life. Every particle is a wave (see de broglie). It can be represented by a wavefunction, the square of which is the probability of detecting it at any given point. Different energies represent different waves, but not every wavefunction is possible. Hence, only certain energies can exist, meaning we have discretely based quanta.

Heisenberg's principle is not a technical limitation, but an artefact of the maths.
It's impossible to seperate some properties from others. The function of momentum, for example, is linked to the function of position (if I remember correctly, it's ih d/dx). The more you narrow down the probability of one function, the other gets wider and wider. It's like playdoh - the more you squish it, the more it spreads out in every other direction. If you're mathematically inclined, the function of space is actually a fourier transform of the function of momentum, and vice versa.

- a physics student who's fed up of fourier

Re:Does exist any quantum computer proven to work? (1)

ortholattice (175065) | more than 6 years ago | (#22838034)

1. Entanglement is a fact. 2. Heisenberg's uncertainly principle is intrinsic and has nothing to do with the kinds of particles you use. Both of these things are very non-intuitive as presented by standard QM, to the point where you can't really "understand" them but just have to accept them as facts about the world that experiments confirm.

You may be interested in Bohm's interpretation of quantum mechanics, which is much more intuitive because it deals with realistic particles travelling in a "quantum field," very analogous to classical particles in say an electromagnetic field, and there is none of this mysterious "collapse" or things not existing until you observe them. Standard nonrelativistic QM falls out as the statistics of Bohm's theory. The two are mathematically equivalent. The problems with Bohm's theory are (1) there are faster than light influences (that you can't signal with, though), but I don't see that as philosophically different from the nonlocal correlations of standard QM; (2) while very intuitive, it is somewhat impractical to compute with since you have to work out the statistics of many particle trajectories whereas standard QM essentially already is the statistics; and (3) (probably the most serious) no one has figured out how to incorporate relativity in a clean way. Google: Bohm quantum mechanics [google.com] .

Shor's Algorithm (3, Interesting)

debrain (29228) | more than 6 years ago | (#22836972)

Presumably the article is alluding to Shor's Alorithm [wikipedia.org] , which is a a method to factorize integers which uses quantum computation to yield a worst-case complexity significantly better than any existing deterministic methods.

If that's the case, it's probably worthwhile to discuss Pollard's Rho algorithm [wikipedia.org] , which has a poorly understood worst-case complexity (as a Monte Carlo method), but has a potential average case complexity that is comparable to the quantum.

Re:Shor's Algorithm (1, Informative)

Anonymous Coward | more than 6 years ago | (#22837406)

Since when is O(N^(1/4) polylog(N)) comparable to O((log N)^3)?

Besides, if you believe that some method is faster in practice than what the theory says, there are some RSA challenges out there with big money prizes for you to win.

Re:Shor's Algorithm (1, Troll)

profplump (309017) | more than 6 years ago | (#22837540)

A) To the best of my knowledge is no theory that places even moderately strict bounds on the Rho method. That was the point of the original post. B) RSA has discontinued their factoring challenges.

Re:Shor's Algorithm (0)

Anonymous Coward | more than 6 years ago | (#22838966)

Presumably the article is alluding to Shor's Alorithm, which is a a method to factorize integers which uses quantum computation to yield a worst-case complexity significantly better than any existing deterministic methods.

If that's the case, it's probably worthwhile to discuss Pollard's Rho algorithm, which has a poorly understood worst-case complexity (as a Monte Carlo method), but has a potential average case complexity that is comparable to the quantum.
That is so wrong. The expected complexity of Pollard's Rho is _way worse_ than that of Shor's algorithm. If n is the length in bits of the largest prime factor of the number you are trying to factor, the average case complexity of Pollard's Rho is O(2^(n/2)) -- that is exponential in the size. The complexity of Shor's algorithm is something like O(n^3) which is polynomial.

When stuff like that gets modded +4 Interesting, you know you are reading Slashdot!

well duh (1)

ILuvRamen (1026668) | more than 6 years ago | (#22837084)

wow, this is just like my comment in the last quantum computing FUD artcile. You've still got bus speeds, cache speeds, memory speeds and capacity, and even hard drive speeds. You're not gonna crack some encryption that would take a normal computer 100 billion years but you might be able to render and encode Finding Nemo a lot faster.

Am I missing something? (1)

mark-t (151149) | more than 6 years ago | (#22837090)

What I get out of the article is that he seems to be saying that quantum encryption technology that could effectively factor numbers of the size we use for effective public key cryptography is far enough off that it isn't going to be a problem anytime soon. But isn't that reasoning just postponing, rather than actually dealing with the problem?

Incorrect interpretation? (1, Informative)

blueg3 (192743) | more than 6 years ago | (#22837130)

It appears from the first comment on the post that it's likely that this post isn't really accurate. Shor's factoring algorithm is O(k) in number of qbits and O(k^3) in number of operations. This doesn't mean that the number of gates in the quantum computer is O(k^3), it means that the time it takes to execute the algorithm is O(k^3). It appears this discrepancy may be a result of not agreeing on terminology. I haven't checked this out thoroughly, but glancing at my copy of Mermin's "Quantum Computer Science" confirms that it's k^3 in time, and only k in space.

While it's clear a quantum computer won't be breaking your RSA keys any time soon, there's a big difference between remarking that a 4096-bit key will require "billions" of qbits and the more correct claim that it will require thousands of qbits (at least 20k qbits).

Botnets are more of a threat (1)

BountyX (1227176) | more than 6 years ago | (#22837184)

Botnets folding md5 between the 8-12 character spectrum for rainbow hacking are more of an imminent threat....between the estimated 4-10 million machines you could probably crack any unsalted hashes within a month.

Use quantum computers to ENCRYPT (1)

presidenteloco (659168) | more than 6 years ago | (#22837306)

If we can use quantum computers to decrypt..
Why can't we use them to come up with an equally mind-blowing way of encrypting?

I don't mean single photon secure fibre channel stuff. That seems fairly impractical to deploy to the whole internet.

I mean, why can't some mathematical genius come up with a new encryption algorithm that you
can only implement on a quantum computer, and which produces a cipher text so random that it
can't be decrypted even by another quantum computer unless it knows the secret.

Does anyone have any ideas how such an algorithm might work?

Re:Use quantum computers to ENCRYPT (0)

Anonymous Coward | more than 6 years ago | (#22839232)

PKI is not so much about encryption as it is authentication. Proving you are who you say you are.

but yeah, you would think there is some way to do this with a quantum computer so that it can't be easily broken by a quantum computer.

Complete article (without subscription) (2, Informative)

Muhammar (659468) | more than 6 years ago | (#22837308)

Since the Sci Am article is subscription-only, you may want to check the complete draft-version of Scott Aaronsons article for Scientific American (before editors changes) here:

http://www.scottaaronson.com/writings/limitsqc-draft.pdf [scottaaronson.com]

Scott posted it on his blog on 2/18, see http://www.scottaaronson.com/blog/ [scottaaronson.com]

(The blog is often quite technical as you can expect but funny and worth following just for its non-techical bits. Circumcision and Australian models are also discussed on frequent basis.)

Part of a long lineage of naysayers (2)

cleduc (146288) | more than 6 years ago | (#22837332)

Heavier-than-air flight is impossible; a train will never go faster than a person can run or the passengers will asphyxiate; there is no reason why anyone would want a computer in the home; etc. [wilk4.com]

It's a bad idea to discount future technological advances wholesale.

In what ways is this a problem? (1)

failedlogic (627314) | more than 6 years ago | (#22837430)

In what ways is this a problem? I'm not knowledgeable about cryptography. My only knowledge and understanding (due to complex math involved) is Simon Singh's Code Book.

I would consider that if Quantum computers exist, it would pose a serious threat to security and military applications as your enemy would always be listening. I don't know if E-Commerce would grind to a halt, since governments would initially be the only ones to afford it. I would think that instead of hitting e-commerce the better thing to go after -for a government- would be banks and securities exchanges, military and state secrets.

Personally speaking, I don't have a great deal of information that needs unbreakable encryption (neglecting the computer were stolen, etc). Were it financial data, I would keep it on a PC off-line. Of course, if banks are vulnerable, that's another consideration altogether. If I lived in a communist state or a dictatorship, I think the issue would change yet again. There would be information you would want to keep away from the government such as attempts for a coup or rebellion. Or plans to destroy the Death Star!

There is a problem with this (4, Interesting)

damburger (981828) | more than 6 years ago | (#22837584)

He makes an extremely cogent argument, but it is hampered by the lack of information we have about the state of the art in quantum computers.

Domestic spying is massively popular with western governments right now, and if you think that the NSA and GCHQ aren't doing secret research into quantum computers you are out of your mind. Furthermore, it is a commandment of signals intelligence that you do not let the enemy know you have broken his code - and in this case the enemy is us. We have no idea how far along they are. We have no idea what the generational length is for the quantum computers that are certainly being developed in secret.

Basically, this essay could be published and make just as much sense either before or after a critical breakthrough had been made by one of the aforementioned agencies and they hadn't told anyone. Thus, we have no way of knowing if we are already past that point or not.

Given that it has already been shown that quantum computers are not infallible, would it not make sense now to start working on encryption methods designed to flummox them?

Re:There is a problem with this (1)

BountyX (1227176) | more than 6 years ago | (#22837732)

The way I see it is encryption was never really effective in the first place. It was always easy to attack the source at which decryption occurs. You could combine multiple encryption algorithms MANY MANY times and force the cracker to guess the pattern of decryption used? A complex pattern of encryption algorithms would form a hidden key and its obscruity would make it increasingly difficult to decrypt. Again, this wouldn't protect against attacking the source of decryption.

Re:There is a problem with this (1)

Gazzonyx (982402) | more than 6 years ago | (#22838452)

FWIW, I've heard the rule of thumb on the government (The US... I assume European governments are roughly in the same ballpark where economy allows) is about 5 years ahead of the private sector when it comes to any given technology.

That is, so far as research goes. I think implementation lags the private sector by several years due to bureaucracy.

Re:There is a problem with this (1)

damburger (981828) | more than 6 years ago | (#22838728)

Yeah, but who do you think made up the rule of thumb ;)

Seriously though, you can't really make that kind of prediction with such a new field of technology. It would be like trying to guess how far along the Manhattan project was as a civilian in 1942.

Whilst interesting, this guys piece is the crypto equivalent of the Drake equation; sound maths, but it doesn't tell us anything because we have no way of knowing any of the variables.

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...