Ever since writing has existed, people have wanted to send secret messages to one another--and others have wanted to intercept and read them. This is the fourth installment of a blog series taking you through the history of cryptography, its present, and future possibilities of unbreakable codes. Follow the links to read the first, second, and third parts of the series.
In the last post I talked about Public Key Cryptography, a system that derives its security from "hard" math problems like finding the factors of large numbers. But increases in computing power have made once-impenetrable codes solvable in just a few months. Keeping ahead of technological development by increasing the length of the secret number used to encode information--the key--is always an option, but there is still a chance that someone will find a tricky way to calculate your private key, letting them read all your messages.
One of those tricks could be quantum computing. Scientists have shown that a quantum computer could use some clever properties of quantum mechanics to help codebreakers solve many of the math problems at the heart of public key cryptography.
How? A quantum computer encodes "bits" of information in the properties of subatomic particles. And here is where things get strange: Because unobserved particles--according to quantum mechanics--exist in a combination of all possible states, a quantum computer is able to store and operate on multiple numbers at once. Suddenly, "impossible" tasks like factoring large numbers can be done in the same time it would take to multiply them.
Although quantum computers are still in their infancy--nothing with enough complexity to run that sort of program can be built yet--codemakers can see the demise of public key cryptography on the horizon. It's not like everyone would have a quantum computer, but chances are that someday in the future, if the government or a big business wants to read your encrypted mail, they'll have access to a computer that can do so.
But in 1984, Charles Bennett and Gilles Brassard found a way to transmit a key that is provably secure, even in the face of quantum computers. Their method, which is still used today, uses properties of quantum mechanics to transmit a random key--and any eavesdropping party would not only get useless information, but would even alert the sender and receiver to an attack. Pretty cool stuff.
Here's how it works: The One-Time Pad, which I discussed in a previous article, basically encodes data by using a randomly-generated key as long as the intended message. It's impossible to break the code and read the message without the key.
Bennett and Brassard's quantum key distribution protocol, called BB84, acts as a sort of high-tech One-Time Pad: A random key is generated using quantum mechanics and shared securely between two people, who can then use it to encode and send unbreakable messages however they want. It eliminates the problem of transferring a key securely. The process of generating the key takes advantage of the quantum mechanical property that measuring something can change it.
Here are the basics: photons are sent from one person to another, measured at both ends. The measurements that match up will be used as the basis for a randomized key.
The sender and receiver each have two kinds of polarized filters: one that only lets in horizontal or vertically oriented photons, and one that only lets in the diagonals. They agree that photons that are vertically or diagonal-forward polarized will represent binary 1, and photons that are horizontal or diagonal-backward will be 0.
The two possible filters
The sender generates a photon and prepares it with one of the two random filters before sending it along an optical cable to the receiver. Once it's there, the receiver measures the photon with his own randomly chosen filter.
Sender and receiver both choose a horizontal/vertical filter, both measure 0.
Here's the tricky part. If the receiver measures the photon with the same filter as the sender, he'll get the same result. But if he uses the wrong filter, there's no such guarantee: If he's been sent a vertically polarized photon and he measures it with a diagonal filter, he has a 50% chance of getting each of the diagonals as his result.
Sender randomly chooses horizontal/vertical, but receiver randomly chooses diagonal. Chaos ensues!
The sender and receiver go through a long string of photons in this way, recording the bit values and which filter they used for each. Afterwards the receiver uses another line of communication--it doesn't have to be secret--to tell the sender which filters he used for each (without giving away the results of each measurement). The sender reveals which filters she used, and they agree to only count the photons where they used the same filters. That way, they know that they've measured each photon the same way, so they'll have the same values.
In this way they build up a secret, random string of numbers using the photons that they both measured in the same way. This string of numbers will be their key.
Now imagine that you are an eavesdropper. If you are able to intercept a photon between the users, you won't know how the sender prepared it, so you have a 50% chance of using the wrong filter. That means that, not only might you get the wrong answer, you might also mess up the value for the receiver because of that quantum mechanical property I mentioned where measuring the photon can change its value. In fact, if the sender and receiver compare the values of a few of their photons and find any disagreements, they can tell that somebody's been trying to read their photons and discard the suspect values from the key.
Eavesdropper tries to measure photon but uses different filter than the sender and receiver, messing up measurements.
Oh, and by the way: Once the sender and receiver start revealing the filters they used, it's far too late for you to use those filters yourself. The photons are long gone.
There are a few commercial systems that implement quantum key distribution today, including ID Quantique, a spinoff from a University of Geneva experimental physics group. The technology has already been used in highly secure transmissions, from Swiss ballots to World Bank transactions.
But quantum key distribution hasn't become mainstream quite yet, mostly due to a few basic issues. For one, the machines are all handmade by physicists, so they are expensive and inconvenient to commission. Another issue is that the system requires dedicated optical cables to send the photons, whereas almost all currently existing fiber-optic infrastructure, although fairly widespread, relies on sending multiple signals on the same cables. And finally, there's the issue of scalability. Right now quantum key communications must be cabled directly from one user to another--like from a bank to a single high-powered client--but a vast new infrastructure would be needed to connect a large network of users.
Richard Hughes, a quantum researcher at Los Alamos National Laboratory, is working on answers to these design problems. In the future, he expects quantum cryptography to be used in smart grid applications and to eventually extend to everything from smartphone and tablet security to securing data in the virtual cloud. He says that quantum cryptography is much further along than we realize: The technology that exists today can already be used reliably in optical fiber networks for systems of medium scale, and experiments suggest that through line-of-sight delivery of secure keys--that is, sending the photons through open air--it could be possible to generate keys with satellites in orbit.
Although the key creation is perfectly secure, there still may be ways to outwit the system. For instance, in April 2010 researchers at the Norwegian University of Science and Technology found a way to trick a commercial system into revealing its secrets by shining a laser into the receiver's filter, blinding it while they read the photons themselves. The team was kind enough to warn companies using quantum technology before publishing their results so the security hole could be fixed.
Certainly this won't be the only flaw that researchers--and hackers--discover. After all, you can have the strongest, most well-secured door in the world, but the room's only safe for the time it takes to blast through the wall. As time goes on, security flaws will be found and repaired, approaching the perfectly secure system promised by quantum physics, and maybe even revealing more about how our universe works.
The fight between codemakers and codebreakers has driven technological and mathematical advances through history--from frequency analysis to mechanical bombes during World War II to computers to quantum programs. Quantum key distribution promises an unbreakable one-time cipher that companies, governments, and even individuals will be able to use to send information with perfect security and store private data with an unbeatable cipher. So--at least for now--the secret keepers have won. What will we do with that power?