Slashdot Mirror
Time Running Out for Public Key Encryption
holy_calamity writes "Two research teams have independently made quantum computers that run the prime-number-factorising Shor's algorithm — a significant step towards breaking public key cryptography. Most of the article is sadly behind a pay-wall, but a blog post at the New Scientist site nicely explains how the algorithm works. From the blurb: 'The advent of quantum computers that can run a routine called Shor's algorithm could have profound consequences. It means the most dangerous threat posed by quantum computing - the ability to break the codes that protect our banking, business and e-commerce data - is now a step nearer reality. Adding to the worry is the fact that this feat has been performed by not one but two research groups, independently of each other. One team is led by Andrew White at the University of Queensland in Brisbane, Australia, and the other by Chao-Yang Lu of the University of Science and Technology of China, in Hefei.'"
More like the Chinese government wants to break the encryption so they can more easily hack other governments data. They just post it under "Research".
I have developed an algorithm to efficiently decrypt ROT-26. You will need to use it to read this encrypted message.
See my journal for slashdot ID's by year. Mine created in 2005. http://slashdot.org/journal/289875/slashdot-ids-by-year
Wouldn't making the keys bigger solve that problem?
The two factors are 1 and the number itself. Now prime number FACTORIZATION.... that's hard for large numbers that have only a couple of factors.
File under 'M' for 'Manic ranting'
Well-funded governments or criminal organizations could take advantage of this, but I guarantee you that J-random-cracker in his basement is NOT going to be able to build a quantum computer.
This poses a big threat to governments, and possibly financial institutions, but not individuals. Nobody is going to spend millions of dollars to build a working quantum computer just so they can steal your credit card number. If I had a quantum computer I would use it to blackmail entire governments, not harass the little folk.
It doesn't necessarily mean the end of public key cryptography, it just means we'll have to come up with something other than prime factoring to compute the keys.
What this does mean is that there's going to be a lot of money to be made replacing public-key cryptograhy in custom code ala Y2K.
My blog
it's a bit like nuclear weapons, in that you can pretty much "know" how a bomb works, but even if you had detailed plans, it's pretty much only governments who can build them.
of course, it's not such a good thing for governments to have unfettered access to all communications and banking details, but in general it won't be like your neighbours can spy on all of your banking transactions?
http://www.huliq.com/34160/qubits-poised-to-reveal-our-secrets seems to be a copypasta of the article.
Yeah, but who filed the patent first. That's all that matters.
Who is John Galt?
Hmmm, guess I'd better start using a 1024 septendecillion or larger bit key.
"I bow to no man" - Riddick
The quantum computer referenced in the summary managed the immense feat of finding the factors of the number 15. While it is true that factoring numbers of the magnitude used in cryptography is now a "matter of engineering", there are profound difficulties involved in scaling quantum computing. The fundamental problem is called "decoherence" and describes the tendency of quantum systems to become entangled with their environment, and the consequent loss of pure quantum states. The issues involved in quantum computation connect to deep issues of thermodynamics and entropy, and research on quantum computation has potentially great significance for fundamental physics. Cryptography may have to develop and implement new, extended standards as computational techniques evolve, but the encryption sky is not yet falling.
The first article linked to in the summary requires a subscription to read anything more than the synopsis.
File under 'M' for 'Manic ranting'
"PQCrypto 2006: International Workshop on Post-Quantum Cryptography"
http://postquantum.cr.yp.to/
From The link:
Elliptic curve public crypto does not rely on the difficulty of factorization, so this specific attack wouldn't affect it, but I don't know if there are applicable quantum computing attacks. Too bad software patents are such an issue for it in the US.
This means that people will come up with new encryption methods that I couldn't possibly imagine (not much of a stretch). Based off these newly powerful methods people will find new impregnable methods. Sort of like how when people came up with the idea of wooden shields, someone came up with a way to pierce them so someone came up with metallic armor and then someone came up with the idea of a combustion-powered missile (gun) and someone came up with Kevlar and so on...
Is to just use quantum encryption whenever transmitting encrypted data... supposedly, that's unbreakable (or at least not breakable without alerting the sender or receiver that you broke it), right?
File under 'M' for 'Manic ranting'
Encryption/decryption grows linearly in the length of the key, and cracking is [considered] exponential in the length of the key. the problem is that shor's algorithm on a quantum computer is also (IMHO) linear in the length of the key. Hell, even if it was a decent order polynomial in the length of the key you could never be "faster" (in the tractable vs. intractable sense). so, no, you can't even do it for now
BSD is for people who love UNIX. Linux is for those who hate Microsoft.
The Magic Words are Squeamish Ossifrage
RSA uses primes. This leaves the ones that don't: HFE, NTRU, ECC, XTR, Paillier, ElGamal, ....
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
The general handshaking mechanism itself is not in danger. It is the prime factor-based RSA algorithm. There might be other key algorithms in danger as well, but this doesn't reflect on the PK framework.
that it will be a really long time before QC are cheaper in terms of factorizing numbers than the equivalent classical machine. If they work at all. The common beliefs about the different QC other implementations in the field usually are said to be
-NMR: Most advanced no decoherence, but severe scalability problems. Nobody knows if they can ever put more than 10 qubits (
-Quantum Dots: Nice but Semiconductors have a hell of excitaions and decoherence
-Spintronics: Interesting, but it will take a time until it is under control
-Ions: well advanced, good control, some scalability problem (not necessarily IMHO)
-Atoms: advancing (-> Atom Chip), could be fine
-Superconducting qubits: Right now decoherence problems, which may be solved.
...and quantum physics taketh away. Looks like it'll be a race between quantum computing and quantum cryptography to see whether we're all left with a gap where everyone's vulnerable...
"A great democracy must be progressive or it will soon cease to be a great democracy." --Theodore Roosevelt
Let me share a quote that my Complexity Theory professor at Carnegie Mellon said about this back in 1999:
"Quantum computing has the potential to change everything, no doubt about it. However, I won't get excited about it until they can factor a number larger than, oh, let's say, FIFTEEN. Until then, everything in this class about turing machines, P, NP, etc is still the world we live in."
That's the quote as best as I can remember it, and the number he said was really close to 15 if I recall. Bottom line, what he said is still true--this is fascinating, fascinating stuff, but we really need to see it happen for larger numbers!
-Jaro
Very interesting to know there are other algorithms which might resist quantum computing attacks.
It's also very good that the cutting edge of this technology is (presumably) being done and reported on publicly, so people will know if and when they can no longer protect their communications using certain methods.
Kythe
So what you're saying is...
Necessity is the mother of invention.
Right?
I think we all already knew this.
Shors algorithm make use of probability functions that come from quantum mechanics, along with some other useful features such as the massive parallel processing you can get from qbits http://en.wikipedia.org/wiki/Qubit( you will see the probability functions in how they define qbits). Example you can't tell exacting where an electron around an atom is really at but you can say the statement like "80% probability that the electron is there." Shors algorithm makes use of probability functions such that incorrect answers tend to cancel themselves out without you doing a bunch of computations. You can't think of Shors algorithm in the traditional sense that f(x)=y, it is a probability function like the dirac equation http://en.wikipedia.org/wiki/Dirac_equation.
I finally went and figured out gpg just this week and it's already about to be obsoleted...
This sounds like some serious breathless bullshit to me.
There have been quite a few different methods of quantum computing developed that take advantage of several types of quantum processes in nature. I worked on bulk-spin-resonance QC as a research assistant at MIT.
To the best of my knowledge, every method so far developed runs into coherence and noise limitations that make it very difficult to scale them up. It's usually not too hard to build a 3- or 4- qubit quantum computer, but scaling up the size seems to itself have an exponential characteristic to the problem. Basically, it's very hard to build a practical quantum computer that works on the scale necessary to factor even modest sized numbers. The engineering challenges to make any of these methods at all practical are bafflingly hard - the underlying science and math are pretty straightforward on the other hand, and the algorithms are undoubtedly cool as hell.
I understand these days the interesting work is on trapped-ion approaches and semi-conductor approaches.
Anyway, Shor's algorithm has been around for years. The theory behind QCs is fairly well understood, the experimental difficulties are huge.
Basically, unless this represents a real breakthrough, i.e. a technique that is not just scalable in theory but can be demonstrated practically to be linearly more difficult to scale up the number of qubits, then it's not a breakthrough that anybody needs to worry about yet.
Without seeing this article's full text though, it's hard to really know, but I gather optical approaches have been tried before and haven't gotten any further than anybody else has.
Read about this in a book. Wouldn't this be a solution? They say it's fundamentally unbreakable, even WITH quantum computing. An idle boast? Or the solution we've finally been looking for?
To moderators who marked this offtopic, you may wish to read the linked article first.
Scott Aaronson has a wonderful explanation of how it works (including why it's so much faster with quantum) at http://scottaaronson.com/blog/?p=208.
So can I guess an American university has not been able to do this because they would be put in jail (DMCA). "I'm sorry we can't cure your cancer because the technology used to do this could circumvent digital property rights and encryption algorithms."
How much do you want to bet that this is pure bullshit and that nothing will ever come out of it? This is just another plea for funding. Quantum computing is the biggest scientific hoax/bullshit in the history of science. Physicists have no clue as to why nature is probabilistic and yet, they feel qualified to claim (without any evidence to back it up) that certain quantum states are superposed. What they are are claiming is that states are suppoerposed but you can never observe supperposition because, as soon as you do, it causes a collapese of the wave fucntion and the superposition disappears. This reminds me of a kid who insisted that he could jump as high as a mountain but only when nobody was looking. Yeah, sure. Whatever happened to empiricism? Voodoo physics is all this crap is.
So yeah, go ahead and mark me as a troll but I am right, goddamnit! It's all bullshit.
Can quantum computers be used to create encryption keys that other quantum computers cannot solve in linear time? Perhaps computers will someday each include a QPU (quantum processing unit) that would be dedicated to performing such tasks.
Are Robert Redford and Sidney Poitier somehow involved in this?
*sigh*
This doesn't break "public-key cryptography". Even if you could build a Shor-factorization machine big enough to use against real-world keys (and that's a *big* if), it's only good against RSA. Elliptic-curve cryptosystems, for example, would be entirely unaffected. In general, the question of whether general-purpose quantum computers would break all public-key cryptography is a really hard one. It's equivalent to whether there are any trapdoor one-way functions which are in P but with inverses not in BQP. Even the existence of non-trapdoor one-way functions is still an open question; they would have to have inverses in , and proving that would also imply P != NP. All the existence of Shor's algorithm really shows about that problem is that there is at least one problem, integer factorization, which is in BQP but (probably) not in P.
Anyway, it's a long way from running Shor's algorithm to factor 15 to being able to factor a 4096-bit RSA key. Remember that because of the no-cloning theorem you can't build a flip-flop for qubits, so quantum circuits are all combinatorial logic. Applying Shor's algorithm to real-world RSA keys would require building a complete modular exponentiator combinatorially out of quantum logic gates, wide enough to deal with the biggest key sizes practical for anyone to use (and the cost of RSA encryption/decryption only scales linearly with the key size). We couldn't even build that out of regular non-quantum logic.
See "Rubber Hose Cryptography".
Can we get a "-1 Wrong" moderation option?
If this algorithm can be used to find the private corresponding key given a public key, someone would just need to get the private key for a certification authority (say, VeriSign), and they would then be able to create fake certificates at will. Of course the key would be revoked when the compromise is discovered, but a lot of interesting stuff could be done in the meantime. It would be very handy for creating phishing sites, among other uses.
I'm going to use my brain's Alzheimer disease algorithm to encrypt everything since in a few years I won't able to remember anything and therefore no one would be able to get it, ever. Now where the heck I put my car keys at...
"It doesn't necessarily mean the end of public key cryptography, it just means we'll have to come up with something other than prime factoring to compute the keys."'
There's more to it than that. What one takes away, it can also restore. Quantum hardware and the corresponding algorithms will be the basis for future encryption. It's called an arms race for a reason.
Pretty soon, even if I make sure the cute little lock (ah! there it is!) is on on my browser, someone will be able to klaJADf llkqjwer wlkertuidf hjaidf adfy ajsdf yadsfhjm, werl sdfi iughj ajkajhsdfdk ?
Thssag!
"Win treats sysadmins better than users. Mac treats users better than sysadmins. Linux treats everyone like sysadmins."
That's not what I am saying, what I am saying is (in a polite fashion) that this isn't really news like the article thinks it is. So what if an old accepted method is dying, the write of the article doesn't seem to understand what you said. If people continue to point out the obvious like the article then we have a chicken little "the sky is falling" issue that never seems to go a way.
:)
So thank you for reiterating the obvious
How the quantum computer solves the public key encryption:
1. Put box on computer
2. Let it randomly generate and test primes
In this state the computer virtually exists in an infinite number of states of which some will have randomly generated the secret primes.
The problem however lies within the observer;
3. Take off the box and the infinite number of states collapse in only one observed state; which is very unlikely to be the computer-state that hit the secret primes
The solution to this problem is found to be one of the category 'I would have though of that'.
4. Once an instance of the computer has found the primes it will bump off the box.
The box moves, and the states-timeline collapses to the only possible state and instantly the computer that found the primes will always have been in there.
If you mod this up, your slashdot background will turn into a beautiful sunset!
So the encryption technique which is built on top of the fact that prime numbers products are difficult to factor is supposedly going to be beaten. This encryption technique relies on the fact that as we scale the prime number product up in size linearly, the difficulty to factor it goes up exponentially (ie, factoring 6773461 (1489*4549) is (much) more than twice as difficult as factoring 3391079 (2003*1693) even through 6773461/3391079 ~= 2.) Next up, there exists a quantum algorithm (and has for some time now) that can perform this factoring in O((log n)^3) time. Quantum computers are now capable of running this algorithm.
At this point most people would panic and begin buying up all the gold bricks; however, what we have failed to mention is that producing a quantum computer capable of dealing with larger and larger numbers is an exponentially difficult problem in itself. Currently we have quantum computers that can run this algorithm on the number 15 (5*3) but it will be over twice as difficult to build a quantum computer that can run this algorithm on 35 (5*7). We need not worry until quantum computer manufacturing/engineering gets to a point where they can be scaled up linearly as well. I don't doubt that this day will come, but I do doubt that it will come before we have figured out a good quantum replacement that doesn't scale well even on quantum computers.
If there had just been a single research group involved, this would have been serious. But if there are two competing research groups, it is a bull race: whose bull arrives first, wins.
I don't think our current economy would do well if it had to go several centuries before finding a new method of encryption. Fortunately for us, there are several well-known encryption schemes that do not rely on the difficulty of product-of-large-primes factorization.
Any sufficiently simple magic can be passed off as mere advanced technology.
Yes, but the quantum encrypted keys are trivially easy to decrypt on grandma's clamshell iBook.
If you don't know what AltaVista is (was), get off my lawn.
Not all PKK is based on prime numbers. Take for example ElGamal, which is proovablu hard to break. Also these demo "quantum computers" may just not scale up far enough to break any real keys based on prime numbers. In fact that is quite likely.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
I'm back in 1999 again... oy.
Has anyone seen anything beyond factoring 15 (which happened in 2001)? Sounds like these new groups are just verifying the research done by IBM. The problem is that from the article blurb it sounds like they are still using NMR, which has been old for a while.
Unfortunately many of the new, more scalable QC methods (think dwave etc) are not able to run shor. I think the big holy grail now is building a machine that can scale AND run shor, or to partition shors algorithm so you don't need thousands of qbits to all be entangled with eachother at the same time (dwave can only entangle adjacent qbits on the board last I heard).
Also keep in mind that there is more to QC than just shor. There is a ton we can learn from molecular simulations ranging from weather patterns to new genres of plastic.
Know how many keys there are out there in use? Unless they have a method that can break keys in real time while messages are being sent they're screwed.
Take this example. Person A sends a message to person B. Every tenth character person A switches to a new key. Person B, who knows what keys are in use, but not the order for today, collects the message, and runs their key 'recipes' on it until one makes sense of the first ten blocks, being enough to identify which sequence of keys is in use. Person B then decrypts the whole message.
Anyone snooping on that may have to crack thousands of keys just to extract one coherent message. Good luck on that one.
Quantum computers can factor numbers in something like sqrt() or log() of the time needed by a normal computer.
ie. a quantum computer cracks a 2048 bit key as easily as a normal computer cracks a 1024 bit key.
So...all we need is longer keys.
Safe again! Phew!!
No sig today...
NSA?
While it might be easier to hijack packets being flung back and forth and decrypt them while they are still relevant, there are lots of ways to throw tons of junk decoys in the authentication process. Lots of decoys + time limited authentication and red flagging/locking out someone sending a suspect number of invalid logins at least makes the problem manageable.
There seems to me some (a lot?) of FUD mixed up in this article. (surprise surprise...)
:-) i'm down with that.
It starts out with the fact that public key encryption relies on the existence of one trapdoor one-way functions. Now in practice we mainly instantiate these functions with the RSA function (f_e(x):=x^e mod n with trapdoor p,q such that pq=n). But there is no reason to believe this is the only possible example of trapdoor OWF! Admitedly in the 80s when this concept was first being explored there were quite a few failures when trying to base implementations on NP-Complete and/or NP-Hard problems (think knapsack for example). But since we already had RSA with all it's nice properties (efficiency, elegance and simplicity) the research community was not overly motivated to find others.
There have been and to this day still are other lines of research. Take Ajtai and Dwork's work in the direction of basing PKE on worst-case hardness of the shortest vector problem (SVP) or Micciancio's work on generalizing the knapsack problem such that average-case hardness of approximating the answer can be reduced to worst-case hardness of certain lattice based problems.
Another general direction has been to come up with groups and fields over which solving the DLP is difficult. (For example torus-based crypto and generalized Jacobian groups). AFAIK for most of these candidates there are no (known efficient) reductions from the DLP problem over Z_p or elliptic curves to the DLP in these new groups. Thus it is not immediately clear how or if Schorr's algorithm would break such systems.
In any case there is reason to believe that there can not be (or that we can't find) good candidates for trapdoor OWFs in the quantum computational model. After all there is such a thing as Quantum P and Quantum NP. Though the inequality of these set's of problems doesn't directly imply the existence of quantum trapdoor OWFs it is a good indication there of.
So basically the message is : Relax! The PKE world is by no means on the brink of an apocalypse. At most (and best in my opinion) we're in for a bout of some serious foundations research. to me that just sounds like more funding for applied mathematicians and complexity theorists from various corners and a WHOLE bunch of new candidates and interesting results.
Cheap storage will eventually destroy any kind of crypto/anti-crypto technology.
What are the new DVD formats getting? 50GB of data RW? Will options up to 250GB or so of RW storage?
How much information do you really, really need to hide, anyway? Maybe a couple of megabytes of financial-related data per day? A one-time pad on a DVD should provide you with centuries of totally secure communications.
So you sign up for your bank account. The bank snail mails you a 10GB random noise memory stick. You add it to your 10TB secure random storage system and you and the bank can talk for the rest of your life without anybody else being able to listen in.
They are named Ching Chong Chowmein.
1 . . . plus . . . 1 . . . plus . . . 2 . . . plus . . . 1 . . . .?
One of my favorite papers is a neat one about analog computer by Vergis, Steiglitz and Dickerson:
http://www.cs.princeton.edu/~ken/MCS86.pdf
It shows how to bolt together car differentials to solve all NP complete problems. They only need a linear number of differntials (2x the variables in 3SAT). Sounds awesome, right? The problem is that the differntials need to be machined with a level of precision that increases expoentially. And precision costs cash.
Is it possible that the quantum computers require the same steeply increasing level of precision? Enquiring minds want to know?
Pretty much any encryption system can be broken given the guy who did the encrypting and a pair of needle nosed pliers. And someone with a complete lack of morals to apply the later to the former until the encryption is broken. We know we have plenty of people in our military and intelligence communities who are fine with using this method of decryption and it doesn't seem to offend the public particularly, so why wait? We can use this fast and effective decryption method today! Welcome to the World of Tomorrow!
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
I don't know if you've noticed, but our friends at the Storm BOTNet are already years ahead of you; with 50,000,000 computers (or more) to direct towards such a problem, you can have supercomputing evil TODAY!
I wish I was joking.
--- For a good time mail uce@ftc.gov
Why? Why not just use one time pads?
One time pads are impossible to crack. Sure it's possible to crack hardware/software encryption algorithms but if this is true people will simply move back to the low tech one time pads.
Maybe the one time pad will be generated differently but the same concept.
DES 56 has been broken, brute forced. It uses a single 56 bit key to encrypt data.
You get the key, you get the data.
3DES 168 encryption is still, in my opinion, unbreakable. The people who laugh at that statement need to read this.
3DES uses TWO Separate 56 bit DES keys. The first key is used to encrypt the data, just like standard DES. Then the second key is used to re-encrypt the data. Finally the first key is used again to encrypt the data yet a third time. As you can see, it isn't simply using a 168 bit key.
You now have your data triple-encrypted, thereby giving you 168bit encryption.
Brute forcing a key is simply trying every possible numeric combination until you land upon the key that unlocks your data. Even if you guessed correctly the first DES56 key on the very first try, you wouldn't know it because the data you're looking at is still encrypted garbage. With 3DES, you need to guess the first key, then after every single guess, brute force the second key, then try the first key AGAIN and see if you come back with readable data.
And to further confound things, the DES 168 bit standard does not specify whether the second key is used to encrypt or decrypt the data on the second pass. If you have data, encrypt it once, and look at it, you have unreadable garbage. If you then decrypt it using the wrong key, you will end up with different-looking garbage. So, the DES 168 standard only states that you have two keys, and they be used to Encrypt, Encrypt, Encrypt - OR - to Encrypt, Decrypt, Encrypt, but it leaves that choice up to the vendor.
SO, to summarize, you can have:
DES 168 EEE
DES 168 EDE
Now, back to my brute forcing, after I guess the first key, then immediately try to guess the second key. And with that 2nd key, do I try encrypting the data again or decrypting it before I try the first key again to see if I wind up with readable data?
This EEE vs. EDE was infuriating as an administrator, as the VPN vendors would each implement their own method of EDE, or EEE, or DED, or DDD, and this is why you could have a Cisco VPN concentrator using 100% standards compliant DES168 encryption, but you could NOT connect to it using the Nortel VPN client, or the Microsoft client, or any other client besides Cisco's client.
It was the LOOSE standards that obsoleted DES168, not its relative key-length weakness.
I seriously doubt that DES168 could ever be broken.
Good security is based upon reality and common sense. Common sense is a function of having common knowledge.
Here's the easy way to do it. You pick a random key. Attempt to use it. If it works, you profit. If it doesn't, you destroy the universe.
Therefore all surviving timelines are ones in which you guessed right.
This makes all problems O(1).
I don't know why anyone bothers with any of these wimpy 4 bit systems when you can use all of space time as your computer.
Using unique Random number can solve many of these encryption problems and are inherently uncrackable.
It is also know as one time pads, but some some reason everyone wants to go with prime numbers, not only can quantum computers attack them, but large scale cell processor are very good at cracking them.
I guess one time pads and unique Random number lack the "really cool" factor of an I-Phone but they work and no amount of computing power will ever be able to weaken them.
I filed a patent for Electronic cash based on them.
(WO/2005/048082) http://www.wipo.int/pctdb/en/wo.jsp?wo=2005048082
The most state lotteries use it, the Vegas Casino use it, the Auto-tote system use at Race tracks use it. All three have a lot of money as stake and trust unique random numbers. I don't count credit cards, since once the numbers exposed it's worthless, making credit cards very unbelievably exposed.
It's also good for Electronic Voting, and many other applications.
I am always doing that which I can not do, in order that I may learn how to do it. - Pablo Picasso
... in 2001, it was demonstrated by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.They factored a four bit number. Quantum computers on this scale have been demonstrated before, but not much progress has been made in the number of qubits people can build. When someone demonstrates something that can factor even a 32 bit number, I'll be much more impressed. I bet it will be some years before they can even handle a 10 bit number -- and they'll need to hit 2048 bit numbers before any of this is of practical importance.
This is why I read /.
In theory, there's no difference between theory and practice; in practice there is.
I'll bet when the Australian team implemented the algorithm, the Chinese team instantaneously, without waiting for light to reach it, implemented it too.
I call entanglement!
Something is just a "matter of engineering" as though that means it is easy is kidding themselves. After all, one could say that about fusion reactors. We know how to create a fusion reaction, we have bombs that do that, all the science surrounding the whole thing is well understood. Heck we've even got (somewhat) controlled fusion reactions to happen in laboratory reactors. Great, so now it's just a "matter of engineering" to build a working, sustainable one with a net power gain right? Ya, about that, you call me back when you've actually engineered one ok? I won't hold my breath.
The engineering of a working device is often the really hard part. All the requisite theories are math are well understood, but that doesn't mean that building the device is all of a sudden an easy task.
As far as I know, all algorithms based on factorization or the discrete logarithm problem are in danger. The includes Diffie-Hellman, ElGamal, and RSA. All of the elliptic curve algorithms are also affected as these algorithms are mathematical transforms of existing problems.
I don't know of any other algorithms that are currently used for public key encryption or signing. If all the algorithms that can be used to implement the basic idea are broken by quantum computing, the basic idea itself is effectively broken.
As a somewhat unlreated aside... I see a lot of really stupid and misinformed people always commenting on the cryptography stuff. And few people know enough for the right information to float to the top. I think maybe Slashdot needs to post an article linking to a cryptography FAQ or primer or something so people at least have the basic ideas right.
For example, many people I know think that all cryptography is just a contest between the code makers and the code breakers and that all encryption algorithms are fundamentally flawed and the idea is unworkable. And that's not really true at all. It's quite likely that there exists a strong symmetric encryption algorithm that's nearly as hard to break as it is to brute force the key. In fact, as far as anybody knows today, AES is just such an algorithm.
And that's just one example. There are so many people who think they understand this field and so few people who actually do. It's scary. I think that fact is the biggest source of security risks in modern cryptography.
Need a Python, C++, Unix, Linux develop
This from here.
In today's New Scientist there is an article, Quantum threat to our secret data, prompted in part by our recent arXiv paper, Experimental demonstration of Shor's algorithm with quantum entanglement. It's probably far too soon to talk about threats! What's interesting is that our experiment demonstrated every stage of Shor's algorithm. It is not scalable in itself, but there is a in-principle path to scalability which we and our colleagues are investigating to see if and when that's going to be feasible.
Could this not be prevented on web sites if, say, an IP address was prevented from logging in after 3 attempts, or by using a captcha? A quantum computer would not even be able to communicate a (non-quantum) web server the countless times it would take to crack a password in a practical amount of time... This may affect quantum web servers, but if checks like I mentioned were implemented, how is this a problem?
There are a few cases where the payware is worth it!
Dead Tree Edition is nice too.
Smart/AI PKI processes could keep ahead of any clock. Assured authentication eKeys are for initiating a transaction or session when communication/transfer is active a preset-set of eKey interleaving could secure the session. The users always remain the security weak-point. Content/data sharing between eKey synchronous repositories with time-lock-worms in a way that would require any spoof/cracker... know the specific clock cycle used to decrypt, could help some.
....
Consistency in architecture for networks, hardware, software, eKey/algorithms/processes is no longer a security strategy. When anyone can crack-in with time, then time is one half the eKey, so always/frequently change clock.
Secure content/data according to transient-importance, permanent-significance
There will always ways in, ways to slow the cracker down, but no way to prevent anything for sure. Social engineering can even get you past very good air-gap security systems.
Unaccountable leaders are masters, and unrepresented people are slaves. How do US and EU fare?
I am a professional research cryptographer. There are many misstatements in the comments so far (what else should one expect, it's Slashdot.....)
Here are some facts to fix the clutter:
1. Shor's algorithm works on quantum computers and can factor integers in polynomial time. This breaks all public-key systems that depend on the hardness of factoring, including RSA, Rabin, Paillier, and XTR.
2. A different version of Shor's algorithm also computes discrete logarithms (again, in poly time). This breaks all public-key systems that depend on the hardness of discrete log, over *any* cyclic group. This includes ElGamal, even over "exotic" groups like those associated with elliptic curves.
3. Nevertheless, factoring and discrete log are different beasts and are not known to be equivalent to each other. Still, Shor's algorithm (in different versions) solves them both.
4. Shor's algorithm does not yet break all known public-key cryptosystems. Systems based on lattices, for example, do not appear to be affected as of yet. These include Ajtai-Dwork and a couple systems by Regev. NTRU is based on lattices, but is based on some not-so-natural assumptions (i.e, the assumption that "NTRU is secure").
5. Public key encryption is (probably) *not* equivalent to trapdoor permutations (or even trapdoor one-way functions). TDPs are a much stronger notion and are not strictly needed to do secure public-key encryption. For example, ElGamal and lattice-based systems are not based on trapdoor primitives per se.
QUBITS?! What's a qubit?!
--
Toro
(If you don't get the joke, as someone about Cosby's "Noah's Ark" sketch)
See Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
I find it interesting that so much Web2.0 innovation, most of which is commercial, comes out of the US yet these and other important technological developments are coming from elsewhere. Perhaps the US is too focused on capitalism.
You want fun, go home and buy a monkey!
will use the quantum computers to break through teh pay-walls!
Sorry but it is a simple design of a circuit which "could in principle" do it. Problem is to keep the atoms entangled and so on. FUD as of yet. Pedro.
Why not just use a cookie to do the same thing? Or even better, a floppy disk, cdrom, etc combined with the cookie.
The article mentioned was written in 2002. If this were valid, don't you think we would have heard more about this by now?
Its not really news that the encryption will eventually be broken. All encryption is really a matter of creating an algorithm that is too time / processor intensive to be practical to crack given current technology. The data that an organization encrypted 10 years ago and archived offsite is probably completely unprotected at this point if they haven't re-encrypted it. With these advances in computing power, I would hope that organizations with truly sensitive / confidential information- governments, financial entities, etc.- are monitoring progress and working on their plan for how to stay ahead of the curve. We don't want to have a Y2K-like scramble to protect data once today's algorithms are outdated.
Tony Bradley, Microsoft MVP
http://www.tonybradley.com
Huh?
You can't get a one-time pad as a cookie. You can't send the OTP via the same channel of communication that the encrypted data is going to go down; if you do that, you might as well send plaintext.
The nature of OTPs requires a secure channel of communication from one party to the other by which you can send the 'pad. E.g., when we wanted to talk to our Embassy in the USSR, we'd send some guy over with tapes filled with millions of random digits, handcuffed to his wrist, or in the diplomatic pouch. Without that secure channel, it doesn't work.
So if you wanted to get your Gmail securely, via a OTP, either Google would have to make up a DVD of random information and send it to you (securely, somehow), or you'd have to do the same and send it to them. And then you'd have to have that disc in your computer all the time (or copied onto your hard drive) so that you could XOR the incoming bits with the ones on the disc. (Or alternately, to preserve the OTP at a small security cost, you could just use 2048-bit chunks of the OTP as keys to a symmetric session cipher.)
It's not a practical solution on the large scale. It's fine for some special-purpose applications, for for secure communication where you're not going to plan ahead in advance, it's quite impractical.
"Ladies and gentlemen, my killbot features Lotus Notes and a machine gun. It is the finest available."
Has the time run out for me to even comment on this?
"Two things are infinite: the universe and human stupidity; and I'm not sure about the universe."