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.'"
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
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
Well Students of colleges (Perhaps undgrads, or people pretending to be an actual student) can have access to such systems. 10-20 years down the line when such systems become obsolete they get in the hands of the public. Or engineering Quantum Computers becomes more feasable then everyone may have one.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
http://www.huliq.com/34160/qubits-poised-to-reveal-our-secrets seems to be a copypasta of the article.
"In other news, man with quantum computer reported missing...."
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.
I'm actually somewhat surprised that governments haven't passed laws banning the construction of quantum computers except under very tightly controlled circumstances. Kind of like how the ciphers themselves used to be classified as "munitions" in the United States.
Yeah, the Chinese government is the only government that would like to do that.
I don't care why you're posting AC
not really. they can still use the same algorithm, it'll just take longer. it might work for a while, but it's not a long term solution.
plus, cryptography is very resource-intensive, growing exponentially with key size. there comes a point when it's just not practical to use a key that large, as it will take too long to encrypt/decrypt/generate the key.
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.
...His velocity, however, is known precisely.
Can you be Even More Awesome?!
"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...
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
This poses a big threat to governments, and possibly financial institutions, but not individuals.
As an individual, I consider threats to governments and financial institutions "a big deal".
AccountKiller
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)
Depends on the observer.
Well, it has never been successfully tested.
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.
The thing I worry about, is, regardless of which government or group is working on it is this, if this is what they're releasing to the public, how much farther ahead are they behind closed doors.
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.
They mention this is a threat to public key cryptography, but what about private key (aka symmetric) encryption? How is that affected by quantum computers, and these algorithms?
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
Chinese secret services are so secret they don't even have a name. Actually, they don't even need one.
Karma cannot be described by words alone.
It is illegal. You just aren't allowed to see the law because the government has classified it "secret." If people were allowed to read the law, the justice department believes it would provide insight to enemies of the state on a possible exploitable vulnerability.
by the way, I'm just making this up, but I bet you believed me. Sad state of affairs we're in.
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.
No, the problem is that Shor's algorithm can factor in polynomial time. To make keys big enough to be impractical to factor with it, they'd also have to be too big to practically use. Public-key cryptosystems depend on the ratio of the time to break the key to the time to use it scaling exponentially with key size.
To moderators who marked this offtopic, you may wish to read the linked article first.
Governments still use one-time pads for the really sensitive stuff.
See http://en.wikipedia.org/wiki/Numbers_station
The one-time pad is in no danger of being broken by quantum computers or anything else because it's provably unbreakable. (Unless there is operator error, and sometimes that's the case)
The Good Guys(tm) want to have this so that they know what The Bad Guys(tm) might have, and that way they can change their systems before they are cracked. I could imagine some crime syndicate paying the millions for a working quantum computer and the PhD talent to run it so that they could break into international banking systems.
On the flip side, pressing exactly two HD-DVDs with random data, and distributing these to your bankings sites for the most sensitive information is getting more and more cost effective.
All ideas^H^H^H^H^Hprocesses in this post are Patent Pending. (as well as the process of patenting all postings)
>>> ""In other news, man with quantum computer reported missing....""
From the account of witnesses, Police believe the man may be traveling inside a box and there is a possibility he is now dead, and alive.
Does anyone know the name of the Chinese equivalent of the CIA, KGB and MI6?
Jet Li.
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."
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.
Right! Well, them and a former college age hacker turned Mob IT manager turned world saviour.
Think of it Marty. No more rich people, no more poor people, everybody's the same
*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.
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...
The whole point of a One time Pad is that there is no such thing as an algorithm to crack it without quite some information in addition to the ciphertext. The beauty of a One Time Pad is that you can crank through every possible key, but that doesn't get you anything. Sure, you may wind up with some keys that take the ciphertext and make perfectly intelligible English out of it, but there are an enourmous number of messages of a given length, and any of them could be an equally valid. So, cracking a message properly encrypted with a OTP basically amounts to creanking through every possible bit combination the same length as the message, and then guessing arbitrarily which one is the "solution."
In practice, the only time OTP's get broken is when they are used wrong. For example, a message is enciphered with a particular pad, transmitted, and then through a beaurocratic fuckup, the same message also gets transmitted as plaintext. Then, somebody fucks up and uses the same OTP (now a TTP!) on another message. the cryptanalyst gives the old captured OTP a whirl and gets lucky. The OTP is only vulnerable to the CHF algorithm. (Cascading Human Fuckups.)
Properly applied, one-time pad encryption is not crackable. Ever. Using any amount of technology or resources.
Unless you already know the key, any message of the proper length could be the plaintext you're looking for. Even a huge quantum computer wouldn't be able to tell that the ciphertext "VPx\PztI-H&jAL" decrypts to "attack at dawn" and not "attack at dusk" or "retreating now". (or even "yay ice cream!") It might seem like this would break down with degenerate plaintext (such as signed messages), but as long as no key bits are reused and the key is not compromised, it holds up.
"If it's so perfect, why doesn't everyone use it," you ask? "Proper" OTP requires the key to be as big as (or bigger than) the message, and requires the entire key to be shared between both parties, securely, beforehand. Not exactly something eBay can roll out tomorrow.
-:sigma.SB
WARN
THERE IS ANOTHER SYSTEM
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.
There's a problem with quantum computers: decoherence - the bigger the the key, the more qubits are needed and decoherence is more likely. Of course, that's a technical issue.
For the best known classical factoring algorithms, doubling the key length will basically multiply the number of operations required to factor by itself. For Shor's algorithm, doubling the key length might multiply the time to factor by four, but given how quickly computers get faster, that's basically worthless.
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.
Normally we refer to keys used in symmetric encryption as secret keys, not as private keys. For asymmetric encryption, where two mutually dependent keys are used it's private and public keys.
Anywho, it is said that AES-256 should be strong enough to withstand attacks by quantum computing. Of course, by definition, one time pads are resistant against every attack, as long as the keys are really kept safe. The reason why they are not commonly used is the size of the keys (as long as the plain text) and key distribution & memory issues.
So symmetric encryption is still rather safe, and as long as they aren't able to build a rather large quantum computer, I presume that asymmetric encryption is still safe as well.
Hmm. I see what you mean.
I am TheRaven on Soylent News
It's been a while since I looked at Shor's algorithm, but I was under the impression that you needed a quantum computer with a number of qbits greater than or equal to the key length in order to get that kind of scalability with the algorithm. Due to entanglement problems, building a quantum computer with a sufficiently large capacity to run Shor's algorithm on keys of a useful length is still very hard. We've had quantum computers that can use it to quickly factorise trivial keys for a while now, but making bigger ones is very hard.
I am TheRaven on Soylent News
I agree, this is normally the case. But Public key had turned into a hammer and everything looks like a nail. Meaning it's over used and not the best approach for many applications. I guess it's great if your some deep pocket government with cracking machines set up for it.
Someone you need a shared secret to be passed the first time. If there is alway someone listening it will not work.
But I am assuming your moving around and no one can intercept all conversation, but more like the case of a Credit card where or SSL
where someone can intercept a a single transaction, record it and giving enough time crack it. With credit cards this time = 0 since it's in clear text 16 digits.
But once you have your shared "key" I don't like to call it a key, but pad or shared secret, and your mobile (like in wifi/bluetooth) no short term transaction interception will give away any information giving any computing power unlike SSL.
You have to read my patent, but I am using it in combination with SSL/SSH Public key encryption.
But this is just for transmission, not storage, it's also layered with onetime pad and one use numbers.
I also had an idea for public pad encryption using really really large pads, based on the premise that memory is more of a bottleneck then computing power.
I am always doing that which I can not do, in order that I may learn how to do it. - Pablo Picasso
That is very true.
I was trying to address the specific point of the parent poster (that quantum computers gave instant results), not the difficulties of using Shor's algorithm in a practical setting to break cryptography.
There seems to be a general belief that quantum computing can try an algorithm against all possible inputs and give you the best/correct input in one iteration, which is just absolutely not true.
Ancient Chinese Secret, huh?
splunge (n) -- A good idea.. but it could be lousy... and I'm not being indecisive!
China just sends out science like "Ph.D flash mobs" if they are interested.
ie. informants in the Chinese diaspora.
No need for fancy, expensive legends ect.
1000's of students reporting back around the world.
Or they get you to set up in China and clone your work down the street.
Domestic spying is now "Benign Information Gathering"
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.
See Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer