Tuesday, December 11, 2007

Quantum Cryptology

The idea that a vote cast by a person remains the same after he submitted it is taken very seriously in any democracy. Voting is the right of the citizen, and it's how we choose the people who make important decisions on our behalf. When the security of the ballot is compromised, so, too, is the individual's right to choose his leaders.
Quantum Suicide Image Gallery

Fabrice Coffrini/AFP/Getty Images
Votes cast in the Swiss canton of Geneva were protected for the first time by quantum cryptography. See quantum suicide images.

There are plentiful examples of vote tampering throughout history in the United States and in other countries. Votes get lost, the dead manage to show up on the poll results, and sometimes votes are even changed when they're tallied.
But, hopefully, the days when paper ballots get lost on the back roads of Florida en route to be counted will soon be gone, and the hanging chad will become an obscure joke on sitcom reruns from the early 21st century. In other words, it's possible that the votes we cast will soon become much more secure.
One of the ways to safeguard votes is to limit access to them when they're being transferred from precincts to central polling stations where they're tallied. And this is just what the Swiss are looking into. The nation best known for its neutrality is on the cutting edge of research into quantum cryptography. But unlike traditional cryptology methods -- encoding and decoding information or messages -- quantum cryptology depends on physics, not mathematics.
Video Gallery: Wrangling Photons
Researchers at the University of Bath are pioneering the development of photonic crystal fibers. These fibers can transmit data through light, changing the way we use everyday tools from medical equipment to grocery store scanners.
U¬sing a machine developed by Swiss manufacturer Id Quantique, votes cast in the Swiss canton of Geneva during the October 2007 parliamentary elections were transmitted using a secure encryption encoded by a key generated using photons -- tiny, massless packets of light. Since this method uses physics instead of math to create the key used to encrypt the data, there's little chance it can be cracked using mathematics. In other words, the votes cast by citizens in Geneva are more protected than ever.
Id Quantiques' quantum encryption is the first public use of such a technique. What's more, it has catapulted the little-known world of quantum cryptology onto the world stage. So how does it work? Since it's based on quantum physics -- the smallest level of matter science has been able to detect -- it can seem a little confusing. But don't worry, even quantum physicists find quantum physics incredibly perplexing.
In this article, we'll get to the bottom of how quantum encryption works, and how it differs from modern cryptology. But first, we'll look at the uses and the limitations of traditional cryptology methods.
Traditional Cryptology

Photo courtesy NSA
A German Enigma machine
Privacy is paramount when communicating sensitive information, and humans have invented some unusual ways to encode their conversations. In World War II, for example, the Nazis created a bulky machine called the Enigma that resembles a typewriter on steroids. This machine created one of the most difficult ciphers (encoded messages) of the pre-computer age.
Even after Polish resistance fighters made knockoffs of the machines -- complete with instructions on how the Enigma worked -- decoding messages was still a constant struggle for the Allies [source: Cambridge University]. As the codes were deciphered, however, the secrets yielded by the Enigma machine were so helpful that many historians have credited the code breaking as a important factor in the Allies' victory in the war.
What the Enigma machine was used for is called cryptology. This is the process of encoding (cryptography) and decoding (cryptoanalysis) information or messages (called plaintext). All of these processes combined are cryptology. Until the 1990s, cryptology was based on algorithms -- a mathematical process or procedure. These algorithms are used in conjunction with a key, a collection of bits (usually numbers). Without the proper key, it's virtually impossible to decipher an encoded message, even if you know what algorithm to use.
There are limitless possibilities for keys used in cryptology. But there are only two widely used methods of employing keys: public-key cryptology and secret-key cryptology. In both of these methods (and in all cryptology), the sender (point A) is referred to as Alice. Point B is known as Bob.
In the public-key cryptology (PKC) method, a user chooses two interrelated keys. He lets anyone who wants to send him a message know how to encode it using one key. He makes this key public. The other key he keeps to himself. In this manner, anyone can send the user an encoded message, but only the recipient of the encoded message knows how to decode it. Even the person sending the message doesn't know what code the user employs to decode it.
PKC is often compared to a mailbox that uses two keys. One unlocks the front of the mailbox, allowing anyone with a key to deposit mail. But only the recipient holds the key that unlocks the back of the mailbox, allowing only him to retrieve the messages.
The other usual method of traditional cryptology is secret-key cryptology (SKC). In this method, only one key is used by both Bob and Alice. The same key is used to both encode and decode the plaintext. Even the algorithm used in the encoding and decoding process can be announced over an unsecured channel. The code will remain uncracked as long as the key used remains secret.
SKC is similar to feeding a message into a special mailbox that grinds it together with the key. Anyone can reach inside and grab the cipher, but without the key, he won't be able to decipher it. The same key used to encode the message is also the only one that can decode it, separating the key from the message.
Traditional cryptology is certainly clever, but as with all encoding methods in code-breaking history, it's being phased out. Find out why on the next page.
Both the secret-key and public-key methods of cryptology have unique flaws. Oddly enough, quantum physics can be used to either solve or expand these flaws.

Henkster/SXC
The keys used to encode messages are so long that it would take a trillion years to crack one using conventional computers.
The problem with public-key cryptology is that it's based on the staggering size of the numbers created by the combination of the key and the algorithm used to encode the message. These numbers can reach unbelievable proportions. What's more, they can be made so that in order to understand each bit of output data, you have to also understand every other bit as well. This means that to crack a 128-bit key, the possible numbers used can reach upward to the 1038 power [source: Dartmouth College]. That's a lot of possible numbers for the correct combination to the key.
The keys used in modern cryptography are so large, in fact, that a billion computers working in conjunction with each processing a billion calculations per second would still take a trillion years to definitively crack a key [source: Dartmouth College]. This isn't a problem now, but it soon will be. Current computers will be replaced in the near future with quantum computers, which exploit the properties of physics on the immensely small quantum scale. Since they can operate on the quantum level, these computers are expected to be able to perform calculations and operate at speeds no computer in use now could possibly achieve. So the codes that would take a trillion years to break with conventional computers could possibly be cracked in much less time with quantum computers. This means that secret-key cryptology (SKC) looks to be the preferred method of transferring ciphers in the future.
But SKC has its problems as well. The chief problem with SKC is how the two users agree on what secret key to use. If you live next door to the person with whom you exchange secret information, this isn't a problem. All you have to do is meet in person and agree on a key. But what if you live in another country? Sure, you could still meet, but if your key was ever compromised, then you would have to meet again and again.
It's possible to send a message concerning which key a user would like to use, but shouldn't that message be encoded, too? And how do the users agree on what secret key to use to encode the message about what secret key to use for the original message? The problem with secret-key cryptology is that there's almost always a place for an unwanted third party to listen in and gain information the users don't want that person to have. This is known in cryptology as the key distribution problem.
It's one of the great challenges of cryptology: To keep unwanted parties -- or eavesdroppers -- from learning of sensitive information. After all, if it was OK for just anyone to hear, there would be no need to encrypt a message.
Quantum physics has provided a way around this problem. By harnessing the unpredictable nature of matter at the quantum level, physicists have figured out a way to exchange information on secret keys. Coming up, we'll find out how quantum physics has revolutionized cryptology. But first, a bit on photons.
Photon Properties
Photons are some pretty amazing particles. They have no mass, they're the smallest measure of light, and they can exist in all of their possible states at once, called the wave function. This means that whatever direction a photon can spin in -- say, diagonally, vertically and horizontally -- it does all at once. Light in this state is called unpolarized. This is exactly the same as if you constantly moved east, west, north, south, and up-and-down at the same time. Mind-boggling? You bet. But don't let this throw you off; even quantum physicists are grappling with the implications of the wave function.


The foundation of quantum physics is the unpredictability factor. This unpredictability is pretty much defined by Heisenberg's Uncertainty Principle. This principle says, essentially, that it's impossible to know both an object's position and velocity -- at the same time.
But when dealing with photons for encryption, Heisenberg's principle can be used to our advantage. To create a photon, quantum cryptographers use LEDs -- light emitting diodes, a source of unpolarized light. LEDs are capable of creating just one photon at a time, which is how a string of photons can be created, rather than a wild burst. Through the use of polarization filters, we can force the photon to take one state or another -- or polarize it. If we use a vertical polarizing filter situated beyond a LED, we can polarize the photons that emerge: The photons that aren't absorbed will emerge on the other side with a vertical spin ( ).
The thing about photons is that once they're polarized, they can't be accurately measured again, except by a filter like the one that initially produced their current spin. So if a photon with a vertical spin is measured through a diagonal filter, either the photon won't pass through the filter or the filter will affect the photon's behavior, causing it to take a diagonal spin. In this sense, the information on the photon's original polarization is lost, and so, too, is any information attached to the photon's spin.
So how do you attach information to a photon's spin? That's the essence of quantum cryptography. Read the next page to find out how quantum cryptography works.
Using Quantum Cryptology
Quantum cryptography uses photons to transmit a key. Once the key is transmitted, coding and encoding using the normal secret-key method can take place. But how does a photon become a key? How do you attach information to a photon's spin?


This is where binary code comes into play. Each type of a photon's spin represents one piece of information -- usually a 1 or a 0, for binary code. This code uses strings of 1s and 0s to create a coherent message. For example, 11100100110 could correspond with h-e-l-l-o. So a binary code can be assigned to each photon -- for example, a photon that has a vertical spin ( ) can be assigned a 1. Alice can send her photons through randomly chosen filters and record the polarization of each photon. She will then know what photon polarizations Bob should receive.
When Alice sends Bob her photons using an LED, she'll randomly polarize them through either the X or the + filters, so that each polarized photon has one of four possible states: (), (--), (/) or ( ) [source: Vittorio]. As Bob receives these photons, he decides whether to measure each with either his + or X filter -- he can't use both filters together. Keep in mind, Bob has no idea what filter to use for each photon, he's guessing for each one. After the entire transmission, Bob and Alice have a non-encrypted discussion about the transmission.
The reason this conversation can be public is because of the way it's carried out. Bob calls Alice and tells her which filter he used for each photon, and she tells him whether it was the correct or incorrect filter to use. Their conversation may sound a little like this:
• Bob: Plus
Alice: Correct
• Bob: Plus
Alice: Incorrect
• Bob: X
Alice: Correct
Since Bob isn't saying what his measurements are -- only the type of filter he used -- a third party listening in on their conversation can't determine what the actual photon sequence is.
Here's an example. Say Alice sent one photon as a ( / ) and Bob says he used a + filter to measure it. Alice will say "incorrect" to Bob. But if Bob says he used an X filter to measure that particular photon, Alice will say "correct." A person listening will only know that that particular photon could be either a ( / ) or a ( ), but not which one definitively. Bob will know that his measurements are correct, because a (--) photon traveling through a + filter will remain polarized as a (--) photon after it passes through the filter.
After their odd conversation, Alice and Bob both throw out the results from Bob's incorrect guesses. This leaves Alice and Bob with identical strings of polarized protons. It my look a little like this: -- / / -- -- -- / … and so on. To Alice and Bob, this is a meaningless string of photons. But once binary code is applied, the photons become a message. Bob and Alice can agree on binary assignments, say 1 for photons polarized as ( ) and ( -- ) and 0 for photons polarized like ( / ) and ( ).
This means that their string of photons now looks like this: 11110000011110001010. Which can in turn be translated into English, Spanish, Navajo, prime numbers or anything else the Bob and Alice use as codes for the keys used in their encryption.
Introducing Eve
The goal of quantum cryptology is to thwart attempts by a third party to eavesdrop on the encrypted message. In cryptology, an eavesdropper is referred to as Eve.


In modern cryptology, Eve (E) can passively intercept Alice and Bob's encrypted message -- she can get her hands on the encrypted message and work to decode it without Bob and Alice knowing she has their message. Eve can accomplish this in different ways, such as wiretapping Bob or Alice's phone or reading their secure e-mails.
Quantum cryptology is the first cryptology that safeguards against passive interception. Since we can't measure a photon without affecting its behavior, Heisenberg's Uncertainty Principle emerges when Eve makes her own eavesdrop measurements.
Here's an example. If Alice sends Bob a series of polarized photons, and Eve has set up a filter of her own to intercept the photons, Eve is in the same boat as Bob: Neither has any idea what the polarizations of the photons Alice sent are. Like Bob, Eve can only guess which filter orientation (for example an X filter or a + filter) she should use to measure the photons.
After Eve has measured the photons by randomly selecting filters to determine their spin, she will pass them down the line to Bob using her own LED with a filter set to the alignment she chose to measure the original photon. She does to cover up her presence and the fact that she intercepted the photon message. But due to the Heisenberg Uncertainty Principle, Eve's presence will be detected. By measuring the photons, Eve inevitably altered some of them.
Say Alice sent to Bob one photon polarized to a ( -- ) spin, and Eve intercepts the photon. But Eve has incorrectly chosen to use an X filter to measure the photon. If Bob randomly (and correctly) chooses to use a + filter to measure the original photon, he will find it's polarized in either a ( / ) or ( ) position. Bob will believe he chose incorrectly until he has his conversation with Alice about the filter choice.
After all of the photons are received by Bob, and he and Alice have their conversation about the filters used to determine the polarizations, discrepancies will emerge if Eve has intercepted the message. In the example of the ( -- ) photon that Alice sent, Bob will tell her that he used a + filter. Alice will tell him this is correct, but Bob will know that the photon he received didn't measure as ( -- ) or ( ). Due to this discrepancy, Bob and Alice will know that their photon has been measured by a third party, who inadvertently altered it.
Alice and Bob can further protect their transmission by discussing some of the exact correct results after they've discarded the incorrect measurements. This is called a parity check. If the chosen examples of Bob's measurements are all correct -- meaning the pairs of Alice's transmitted photons and Bob's received photons all match up -- then their message is secure.
Bob and Alice can then discard these discussed measurements and use the remaining secret measurements as their key. If discrepancies are found, they should occur in 50 percent of the parity checks. Since Eve will have altered about 25 percent of the photons through her measurements, Bob and Alice can reduce the likelihood that Eve has the remaining correct information down to a one-in-a-million chance by conducting 20 parity checks [source: Vittorio].
In the next section, we'll look at some of the problems of quantum cryptology.
Quantum Cryptology Problems
Despite all of the security it offers, quantum cryptology also has a few fundamental flaws. Chief among these flaws is the length under which the system will work: It’s too short.


The original quantum cryptography system, built in 1989 by Charles Bennett, Gilles Brassard and John Smolin, sent a key over a distance of 36 centimeters [source: Scientific American]. Since then, newer models have reached a distance of 150 kilometers (about 93 miles). But this is still far short of the distance requirements needed to transmit information with modern computer and telecommunication systems.
The reason why the length of quantum cryptology capability is so short is because of interference. A photon’s spin can be changed when it bounces off other particles, and so when it's received, it may no longer be polarized the way it was originally intended to be. This means that a 1 may come through as a 0 -- this is the probability factor at work in quantum physics. As the distance a photon must travel to carry its binary message is increased, so, too, is the chance that it will meet other particles and be influenced by them.
One group of Austrian researchers may have solved this problem. This team used what Albert Einstein called “spooky action at a distance.” This observation of quantum physics is based on the entanglement of photons. At the quantum level, photons can come to depend on one another after undergoing some particle reactions, and their states become entangled. This entanglement doesn’t mean that the two photons are physically connected, but they become connected in a way that physicists still don't understand. In entangled pairs, each photon has the opposite spin of the other -- for example, ( / ) and ( ). If the spin of one is measured, the spin of the other can be deduced. What’s strange (or “spooky”) about the entangled pairs is that they remain entangled, even when they’re separated at a distance.
The Austrian team put a photon from an entangled pair at each end of a fiber optic cable. When one photon was measured in one polarization, its entangled counterpart took the opposite polarization, meaning the polarization the other photon would take could be predicted. It transmitted its information to its entangled partner. This could solve the distance problem of quantum cryptography, since there is now a method to help predict the actions of entangled photons.
Even though it’s existed just a few years so far, quantum cryptography may have already been cracked. A group of researchers from Massachusetts Institute of Technology took advantage of another property of entanglement. In this form, two states of a single photon become related, rather than the properties of two separate photons. By entangling the photons the team intercepted, they were able to measure one property of the photon and make an educated guess of what the measurement of another property -- like its spin -- would be. By not measuring the photon’s spin, they were able to identify its direction without affecting it. So the photon traveled down the line to its intended recipient none the wiser.
The MIT researchers admit that their eavesdropping method may not hold up to other systems, but that with a little more research, it could be perfected. Hopefully, quantum cryptology will be able to stay one step ahead as decoding methods continue to advance.
Source:www.howstuffworks.com

2 comments:

Anonymous said...

Gostei muito desse post e seu blog é muito interessante, vou passar por aqui sempre =) Depois dá uma passada lá no meu site, que é sobre o CresceNet, espero que goste. O endereço dele é http://www.provedorcrescenet.com . Um abraço.

Abhinav said...

Graças CresceNet e desculpe pela resposta extremamente tarde :P