Quantum computers can break many of today’s modern public key cryptosystems. Hence there are lots of three and four letter agencies in governments around the world who are very interested in getting a quantum computer built. (If we put our paranoid hats on, we can ask: are there any countries that are pursuing a secret project for quantum computing? Is it beyond possibility that China, for example, has a secret quantum computing project, and that they will beat the rest of the world to building a quantum computer? Could this be the next Sputnik? OK, enough paranoid mode!) What will the sensitive nature of quantum computers current killer application, breaking public key cryptosystems, mean for researchers in quantum computation? Will it mean that the first large scale quantum computers, when they are built, will have restricted access? Will all hell break loose once quantum computers which can break today’s public key cryptosystems? I’m not just thinking about spy versus spy schemes, but instead, I’m thinking about financial transactions, online use of credit cards, and the whole of the electronic economy. Sometimes it feels like it is a shame that the main attention grabbing algorithm for quantum computers is factoring. Other times, I think about the above line of reasoning, as it scares the bejesus out of me.
How will we make the transition from a world where public key cryptosystems are no longer secure? Will we use the unbroken cryptosystems (lattice based, and linear decoding based?) which have drawbacks which are fairly severe? Will we install quantum key distribution into our networks? And will this transition be gradual, or will it hit like a shockwave, as serious size quantum computers get built over a short span of time?
Interestingly, I don’t think the quantum computing community has had a serious dialogue about these issues. At least not that I know of. Sure we talk about these things over lunches in quantum groups around the world, but is there any consensus over how the public quantum computing community should deal with these issues?
O brave new quantum world!
Ok, you are paranoid ;), but I think that you are right, the quantum computer will be equal to which it was the classic computer in his beginnings: a secret and military weapon :s
Hi Dave,
Similar concerns arise with the possibility of finding an efficient classical algorithm for factoring, which could really happen any day, and in any country. What should you do if you find such an algorithm? I don’t think posting it on the web is such a good idea. To avoid chaos, you should just publicly announce the discovery of the algorithm without revealing it. Then you’re very likely to simply be perceived as a crackpot (which is probably your best option). But if people take you seriously, then you should be concerned with your personal security for obvious reasons…
I don’t think China will built quantum computer before all other countries. Yes, there are many chinese doing research in quantum computation. But the best of them, for example, L.M Duan and J.W Pan, are living in abroad. To built quantum computer, chinese government should get the best scientists in this field. But now the best guy are not in China.
I think that the factoring implications of quantum computers are mostly socially negative.
1) For a long time, QC’s will be extremely expensive and high-tech devices, so only a few governments will be able to afford them. As with nuclear weapons, the government will probably restrict the private sector from building QCs as long as possible (perhaps the supply of some key components could be easily controlled), though there’s always the possibility that cheap QC’s will make this impossible.
2) I imagine these being used mainly against private citizens. Organized crime, terrorists and foreign militaries will be able to communicate via one-time-pads (which go well with their personal authentication schemes, I think), but it’s mainly widespread use of PGP that will be prevented by gov’t QC’s.
3) Eventually there will be cheap QC’s and everyone will use QKD (but also maybe still 3DES?). The result will be we’re back where we started in terms of unbreakable security being widely available, except everything will be more expensive.
And in response to David Poulin, if you have a factoring algorithm, it’s easy to prove this without giving details of the algorithm. So the crackpot thing isn’t a big deal – kidnapping however is of course another story.
Hey Dave, um, I started to write a comment on this but it turned into an article on my blog…. it’s basically me talking smack though, nothing that serious. I do think that people should be seriously talking about all of these issues though… I don’t even know how we can to begin to have such a discussion.
The impact of efficient factoring would be greatly reduced if technology has progressed to the stage where every PC has a small “quantum” unit capable of doing few qubit tasks, such as quantum cryptography, before a full scale quantum computer is built. This is possible, since the technology is already available and we just have to wait for it to become cheaper. Then the transition to quantum cryptography would be much more smooth because every PC would already have the hardware for it.
Of course, for this to become a reality we have to provide a reason for people to want such a unit on their PCs in a world where full-scale QCs do not exist yet, since the average user is not as paranoid as a 3/4 letter agency. The onus on us is to come up with really useful (or really fun) tasks that can be accomplished with a few qubits, so that consumers will buy into quantum technology in the absence of a security threat. Currently, I don’t know of any result in quantum information that might lead to this.
It is interesting to think about what a classical efficient factoring algorithm would mean, but it’s also interesting to ask why wasn’t the quantum algorithm acted upon by government intelligence agencies. Certainly part of this was that Peter Shor was working in the private sector. If he had been working, say, for the NSA, would 1994 have been the watershed year that it was for quantum computing? And for that matter, we know that RSA and Diffie-Hellman were actually discovered a few years earlier than the public announcements of these algorithms by the british intelligence community. Ever wonder if someone actually beat Shor to the punch? I suspect not (mostly because quantum computation was such an obscure subject), but it is interesting to ponder.
Of course, I think the answer as to why the quantum algorithm did not create an uproar is that quantum computers were not around. And so the idea seemed very far fetched. I’ve also been told that one of the reasons quantum cryptography was not taken very seriously by the three and four letter agencies was that it seemed technologically very difficult. Funny, today it is still difficult, but, as companies like Magiq are proving, definitely not impossible.
I doubt even the sudden appearance of quantum computers would be as catastrophic as you suggest, for a few reasons. For one thing, a lot of people continue to use old cryptosystems after they are no longer secure anyway (e.g., RSA with too short a key length). Also, and more importantly, there are a lot of other vulnerabilities in computer networks, and it’s not really qualitatively different if someone steals your credit card number by breaking your encrypted transaction or by breaking into the company’s customer records.
Still, if it happened suddenly (which for the spread of quantum computers would still probably mean over a period of a few years), it would be a serious blow to network security. It’s almost impossible to say what kind of system would replace it, though, because the answer depends in large part on a number of technical questions whose answers we don’t know: Are there good classical public-key systems that remain secure against quantum attacks? Can we make cheap, fast, reliable, long-range QKD systems? What other things can quantum crypto techniques do, and with what efficiency?
QKD doesn’t fix what Shor broke.
The primary use of public-key cryptosystems is distributed authentication. The primary use of QKD will be key generation/exchange. They serve very different roles in the Internet.
Your Internet Explorer, Mozilla, or Firefox comes with Verisign’s public key built in. This allows you to check that yes, indeed, Verisign signed the key that says it came from Amazon.com, and therefore you can believe that you are truly connected to Amazon.
After this authentication step, you must create a shared, secret key to continue the communication. That key exchange is often done via Diffie-Hellman key exchange, which allows parts of the communication to be done in the open (unencrypted). The complexity of Diffie-Hellman is, I believe, founded on the difficulty of the discrete logarithm problem, and hence is vulnerable to Shor. HOWEVER, that is not the only classical method of doing key exchange. If you already have a shared secret, it is easy to negotiate a key without D-H. I used to work for a startup that did IPSEC gateways (though I am FAR FAR from an expert on this), and I believe most of our customers did their authentication via shared secret key. Though the IKE (Internet Key Exchange) built on that secret key authentication does use D-H, that can be fixed.
Shor breaks public-key crypto. Without it, our key management headaches get worse, but there is (almost?) nothing we can do with public key we can’t do with private key. The scalability of authentication servers is problematic and the number of keys you keep around on your systems grow, but in practice probably not nearly as much as people fear, since most people really only connect securely to a few places, anyway.
QKD still requires a classically-authenticated channel; that is, it still requires the functionality that Shor broke — it doesn’t fix Shor!
QKD’s place is for the truly, truly paranoid: people who believe that classical, symmetric crypto (3DES, AES) will fall to either mathematical advances or some further quantum computing advance sometime in the distant future, and don’t want their traffic from TODAY read by somebody half a century from now. And, in that case, your only operational choice is to use the QKD-generated key as a one-time pad, and discard; if you’re really paranoid enough to want the QKD, don’t use it to just generate keys for use with a symmetric crypto protocol.
Wikipedia is not a bad place to start looking for more info on this…
Readers interested in this issue may want to attend PQCrypto 2006, the International Workshop on Post-Quantum Cryptography:
“Will large quantum computers be built? If so, what will they do to the cryptographic landscape?
“Anyone who can build a large quantum computer can break today’s most popular public-key cryptosystems: e.g., RSA, DSA, and ECDSA. But there are several other cryptosystems that are conjectured to resist quantum computers: e.g., the Diffie-Lamport-Merkle signature system, the NTRU encryption system, the McEliece encryption system, and the HFE signature system. Exactly which of these systems are secure? How efficient are they, in theory and in practice?
“PQCrypto 2006, the International Workshop on Post-Quantum Cryptography, will look ahead to a possible future of quantum computers, and will begin preparing the cryptographic world for that future.”
What strikes me is the idea that someone could be collecting transmitted credit card details and encrypted messages BEFORE quantum computing becomes available, and then when it is available they could go back to all their collected data and decrypt it.