Monday 10 February 2014

Introduction to Quantum Cryptography

Imagine you want to send some message to your friend and you don't want others to peek on your message. So you lock your message in a box using a key and send the box to your friend and your friend also have a key to unlock the box so he can easily unlock  the box and read the message. In general this is the technique used by any cryptographic algorithm. Locking up the message in  the box is called Encryption and Unlocking is called Decryption. Before message being sent to the receiver the data is encrypted using an encryption algorithm and a secret key. On the receiver side the encrypted data is decrypted using the reverse encryption algorithm. Classical cryptographic algorithms mostly rely on mathematical approaches to secure key transmission. The security  they offer is based upon unproven assumptions and depends on the technology available to an eavesdropper. But rapidly growing parallel technology and Quantum technology may be a threat to these classical cryptography in near future. One of the solutions of these threats is Quantum Cryptography. Now what is Quantum Cryptography? Quantum cryptography is a complex topic because it brings in to play something most people find hard to understand -- quantum mechanics. Now lets focus on some basic quantum physics that we must know to understand this article.



Simple Quantum Physics:
 Quantum, in physics is discrete natural unit, or packet of energy, charge, angular momentum, or other physical property. Light for example, appearing in some respect as a continuous electromagnetic wave, but on the submicroscopic level it is emitted and absorbed in discrete amounts or quanta. These particle like packets (quanta) of light are called photons, a term, also applicable to quanta of other forms of electromagnetic energy such as X rays and gamma rays. One speciality about quantum is that they can exist in all of their possible states at once. This also applies for photon. This means that whatever direction a photon can  spin in say diagonally, vertically and horizontally, it does all at once. Quantum of lights in this state is called unpolarized photons. This is like someone moving in north, south, east, west, up and down all at the same time. This property is called Superposition. One thing that we should keep in mind is that measuring something that is in its superposition causes it to collapse into a definite state (one of the all possible states) . Superposition can be described well by the following diagram.



                                                                      Necker Cubes

Looking at the diagram you can identify one of four possibilities: Either both squares are protruding forward or both backwards or one forward and the other backwards. Each time you look at the diagram only one possibility comes true. In a sense all four options exist together but when you look at the diagram it collapses into just one. This is the essence of quantum superposition. Through the use of polarization filters, we can force the photon to take one of its states or technically polarize it. If we use a vertical polarizing filter some photons will be absorbed and some will emerge on the other side of the filter. Those photons that
aren't absorbed will emerge on the other side with a vertical spin. Thus we can polarize the photons to our required orientation using suitable filters.

                                                                Polarizing Photons

The foundation of quantum physics is the unpredictability factor. This unpredictability is pretty much defined by Heisenberg's Uncertainty Principle.This principle says, Certain pairs of physical properties are related in such a way that measuring one property prevents the observer from knowing the value of the other. But when dealing with photons for encryption Heisenberg's Principle can be used to our advantage. When measuring the polarization of a photon, the choice of what direction to measure affects all subsequent measurements. The thing about photons is that once they are 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.



                                                Effect of various Basis on polarized photons

In this diagram we have used wrong basis for the last two cases and we can see that we have changed the polarization of two photons.

Quantum Information: 
The bit is the fundamental concept of classical computation and classical information. Quantum computation and quantum  information are built upon an analogous concept, the quantum bit or qbit for short. Just as a classical bit has a state  either 0 or 1, a qbit is like a bit but it is in superposition between 0 and 1. Two possible states for a qbit are the  states "|0 >" and "|1 >" . This notation is called Dirac notation. A qbit can be fully expressed as: a|0 > +b|1 > with a2 + b2= 1. When we measure a qbit we get a 0 with  probability a2  and 1 with b2 . Now consider a quantum computer with two qbits. There are four possible states : |00 >, |01 >, |10 >, |11 > and its superposition is:  a|00>+b|01>+c|10>+d|11> where a2, b2,c2,d2 are the probabilities of finding two qbits in any of the four states. In a quantum computer the two bits are in all possible state at a time. So it is possible to add a number to the two bits which means we can add the number to 00,01,10,11 and compute the result at the same time. This ability to operate on all state at a time makes it so powerful.  Here number of parallel operations  depends on the number of qbits used. If N number of qbits are used then 2N operations can be done parallely and this inherently parallelism makes quantum computer so fast. But question is how will we encode a photon as a qbit? We know photon  has its own spin along all possible direction. As in certain digital system we consider +5 volts as 1 and 0 volt as 0, we can use spin property of photon to encode photon as a qbit. We can use photon's spin about a particular direction as 1 and  spin about other direction as 0 say photon with vertical spin will be considered as 1 and photon with angular spin as 0.



                                                     Encoding polarized photon as binary values


Quantum Cryptography:
  Before starting to describe what is quantum cryptography we must know about three names we will use throughout the article. They are Alice, Bob and Eve. Alice is sending the message and Bob is receiving the message and Eve is in between them and  trying to intercept their message. What Eve does is somehow collects the secret key of the message and decrypts it. Now if   Alice can somehow send the key of the message to Bob without any interception then she can send the message without  interception. Here we will discuss the BB84 protocol. It is on the name of the inventors Charles Bennet and Gilles Brassard  and it was invented on the year 1984. Quantum Cryptography follows two steps first one is sending the secret key and the second step is sending the message. Here Alice and Bob will make use of two fundamentally different communication channel, a classical channel and a quantum channel. Classical channel is something that we use in internet to transfer data. In classical channel Eve can observe the bit-stream  without affecting the data. But quantum channel is something different. It is capable of sending information in terms of quantum and Eve can't observe data without affecting the data. In BB84 protocol secret key is sent through the quantum channel but message is sent through ordinary channel but encrypted by the secret key. The first step is called Quantum Key Distribution(QKD). In this step Alice and Bob uses the quantum  channel for communication. First we will consider there is no Eve between Alice and Bob. Let us assume Alice is using two type of polarizer one is diagonal polarizer (X)and Rectilinear polarizer (+). In rectilinear basis a photon with spin "|" (i.e up to down ) is considered as 1 and "-" (i.e left to right) is 0 and in diagonal basis a photon with spin "/" is considered as 1 and "\" is 0. The below diagram will help  you to understand the way we will represent photon as binary values:


                                                   Binary encoding of photon in our examples


Now Alice have a key and for each bit he will select a random basis (either diagonal or rectilinear in our discussion) to encode the bit to send. Nobody not even Bob knows what basis Alice is using. Bob will receive the encoded qbits and Bob will use random basis to decode the qbits. If he uses the same basis then he will get the exact bit that the Alice sent otherwise there is a 50% chance that he will get a wrong bit.  For example if Alice uses diagonal basis to encode 1 and Bob also uses diagonal basis to decode that then he will get a 1, if he uses a rectilinear basis then there is 50% chance that he will get a 1 and 50% chance of
getting 0. As Bob is also using random basis he will use 50% right basis (i.e he will use the basis that Alice used) and will decode 50% qbits exact and for the 50% wrong basis he will decode 25% of qbits exact, that means Bob will decode 75% qbits exact. Now Alice and Bob will exchange their basis they used for each bit using normal channel without revealing their bits. Now they  can check for which bits they both used the same basis and those bits will be used as the secret key. Consider the below example where Alice is sending the secret key 100101.

+---------------+---------------------+---------------------------+
|         |     Alice           |        Bob                |
+---------------+---------------------+---------------------------+
| Basis used    | +,X,+,+,X,X         |+,+,+,X,+,X                |
+---------------+---------------------+---------------------------+ 

In this case Bob will decode the key as 1,0/1,0,0/1,0/1,1. As Bob have used some wrong basis to measure the qbits, he may get a  0 or 1 randomly on those cases. Then they will exchange their basis with others and they will find that in position 2,4,5 Bob have used wrong basis. So they will use the rest bit (1st,3rd,6th bit) string as secret key i.e 101. Rest part is simple just encrypt the message using that key and send it, that's it. Now the situation gets critical when Eve's comes into action. As we connect using public channel then it is quite possible that Eve will intercept our communication. In this case as previous case Alice encodes the bit information using any of its basis and sends it to Bob but Eve intercepts the qbits. Like Bob, Eve also has decoder of the qbit. But even Eve also doesn't know the basis Alice is using, so like Bob he also randomly use basis to decode the qbits. There is 50% chance that Eve will use right basis and 50% wrong basis. For the right 50%, photon's spin's direction will not be affected but for the wrong 50%, spin direction of photons will be changed. For the 50% qbits for which Eve used right basis Bob will use 25% right basis and 25% wrong basis and for the right 25% qbits he will get 25% right qbit and   for the wrong 25% basis Bob used he will get 12.5% qbits correct just by probability, that means from the first 50% for which Eve used right basis Bob will get 37.5% right qbits. For the rest 50% again Bob will use 25%right and 25% wrong basis.  From  this Bob will get 12.5% and 12.5% both just by probability that means he will get 25% right qbits.  So when Eve is between Bob  will get 37.5+25=62.5% accuracy. We can visualize this calculation as below:




                                                    Accuracy calculation of Bob when Eve is intercepting


In this diagram node with "**" like C** represents the nodes where Bob decoded the qbits correctly and node with "*" like F* representing the nodes where Bob decodes the qbits wrong. One question that may arise is why Bob will get a 12.5% of accuracy where(in E,L) he have used wrong basis? Here we should remember that when we will use a wrong basis to decode a qbit then there is a 50% chance that we will get a 0 and 1 with 50% chance. By this logic Bob will get 12.5% accuracy from D. Similarly in case of I where Bob have used correct basis (with respect to Alice's basis) but Eve has already changed the polarization of the qbits using a wrong basis, Bob have 50% chance of being right and 50% false. So overall Bob gets 12.5% right qbit in I  and 12.5% wrong qbit in J. Now they will match the basis they used for each qbit and they will use the bits where Bob used the correct basis and they will throw out the bits for which Bob used wrong basis. Now they need to check whether Eve is listening  or not.For that purpose they will use a subset of the matched key (after throwing the bits for which Bob used wrong basis) and compare with others using normal channel. Bob will get a 100% accuracy if Eve is not there otherwise Bob will get 75% accuracy in Basis comparison. If accuracy is 100% then they will discard the set of bits they used for matching and rest bit string will  be used as the key to encrypt the message. If 100% accuracy is not observed then they will try again to get a key using QKD.  In the below example Alice is sending a key of "01101011" to Bob and she is using two types of polarizer as stated above.

+-------------------+----+----+----+----+----+----+----+----+
|  Alice's basis    | +  | X  | +  | +  | X  | X  | X  | X  |
+-------------------+----+----+----+----+----+----+----+----+
|  Alice's Data     | 0  | 1  | 1  | 0  | 1  | 0  | 1  | 1  |
+-------------------+----+----+----+----+----+----+----+----+
|  Eve's Basis      | +  | +  | X  | +  | X  | X  | X  | +  |
+-------------------+----+----+----+----+----+----+----+----+
|  Eve's Data       | 0  | 1  | 0  | 0  | 1  | 1  | 1  | 0  |
+-------------------+----+----+----+----+----+----+----+----+
|  Bob's basis      | +  | +  | +  | X  | +  | X  | X  | X  |
+-------------------+----+----+----+----+----+----+----+----+
|  Bob's Data       | 0  | 0  | 0  | 0  | 0  | 1  | 1  | 1  |
+-------------------+----+----+----+----+----+----+----+----+ 

Now Alice and Bob will compare their basis and they will find that Bob has guessed the 1st, 3rd ,7th,and 8th basis correctly. So they will throw the bits of remaining position i.e 2nd, 4th, 5th, and 6th . Now key is "0011". Let them choose the first two bits for matching and then they will find that their second bit in the key is different, that means Eve is between them. Then  they will repeat the same procedure again until they gets a 100% key match. When they get a key then they can easily encrypt the message using the key and send it via the public network.

Limitations:
[1] In practical quantum channel will also be affected by noise and it will be hard to distinguish noise and eavesdropping.

[2] If Eve wants he can intercept the quantum channel just not to allow Alice and Bob communicate.

[3] No amplifiers are used on the optical fiber carrying the quantum signal. Such devices would perturb the communication in the
 same way an eaves- dropper does. This implies in turn that the range of QKD is limited.

[4] Following no-cloning theorem, QKD only can provide 1 : 1 connection. So the number of links will increase N(N − 1)/2 as  N represents the number of nodes.

Research work:
Researchers have been developing such systems for more than a decade. DARPA Quantum Network, which became fully operational  in BBN’s laboratory in October 2003, and has been continuously running in 6 nodes operating through telecommunications fiber  between Harvard University, Boston University, and BBN since June 2004. The DARPA Quantum Network is the world’s first quantum  cryptography network, and perhaps also the first QKD systems providing continuous operation across a metropolitan area. [7]

NIST performs core research on the creation, transmission, processing and measurement of optical qubits. They demonstrated  highspeed QKD systems that generate secure keys for encryption and decryption of information using a one-time pad cipher, and extended them into a 3-node quantum communications network. [8]

Toshiba's Quantum Key Distribution System delivers digital keys for cryptographic applications on fiber optic based computer networks. Based on quantum cryptography.In particular, it allows key distribution over standard telecom fiber links exceeding 100 km in length and bit rates sufficient to generate 1 Megabit per second of key material over a distance of 50 km — sufficiently long for metropolitan coverage. [9]

Current status of quantum cryptography in Japan includes an inter-city QKD test bed based on DPS-QKD, a field test of one-way BB84 system over 97km with noise-free WDM clock synchronization, and so on. [10]

The 973 Program and 863 program of China have funded to support the QKD research.[11]

In Europe SEcure COmmunication based on Quantum Cryptography (SECOQC) (2004–2008) project was funded for the same reason.[12]

In 2004, ID Quantique was the first in the world to bring a quantum key distribution system to a commercial market. ID Quantique’s QKD product was used in conjunction with layer 2 Ethernet encryption to secure elections in Geneva.Other companies like MagicQ,QinetiQ,NEC are also working in this field. Companies claim to offer or to be developing QKD products, but limited information is publicly available. It is however likely that the situation will evolve in the near future. [13]

References:

1. W. Chen, H.-W. Li, S. Wang, Z.-Q. Yin, Z. Zhou, Y.-H. Li, Z.-F. Han and G.C. Guo (2012). Quantum Cryptography,  Applied Cryptography and Network Security, Dr. Jaydip Sen (Ed.), ISBN: 978-953-51-0218-2, InTech, Available from: http://www.intechopen.com/books/applied-cryptography-and-network-security/quantum-cryptography.

2. http://news.sciencemag.org/sciencenow/2010/04/quantum-cryptography-hits-the-fa.html

3. http://www.peterrohde.org/2012/06/29/do-we-need-quantum-cryptography/

4. http://www.linux-mag.com/id/8753/

5. http://thefutureofthings.com/column/5/what-is-a-quantum-computer.html

6. "Quantum Computation and Quantum Information" by Michael A. Nielsen & Isaac L. Chuang.

7. "Current status of the DARPA Quantum Network" by Chip Elliott , Alexander Colvin, David Pearson, Oleksiy Pikalo,
John Schlafer, Henry Yeh.

8. http://w3.antd.nist.gov/qin/index.shtml

9. https://www.toshiba-europe.com/research/crl/qig/quantumkeyserver.html

10. "Toward New Generation Quantum Cryptography -- Japanese strategy " by Nukuikita, Koganei.

11. Post-Quantum Cryptography: Third International Workshop, Pqcrypto 2010, Darmstadt, Germany, May 25-28, 2010,
Proceedings 1st Edition.

12. http://vcq.quantum.at/publications/all-publications/details/643.html

13. http://swissquantum.idquantique.com/?-Quantum-Cryptography-#

** This article was first published in Linux Journal January2013.

No comments:

Post a Comment