Quantum Cryptography : Secure Key Exchange??

How can we communicate secret messages and be sure that they are not read by an undesirable third person? Cryptography is the discipline that tries to answer this question.

In traditional cryptography, only the Vernam cipher permits the establishment of an unconditionally secure channel between a sender (Alice) and a receiver (Bob). This method requires Alice and Bob both to agree on a secret key, which is determined beforehand. Alice encodes the message using this key, and the encoded message cannot then be decoded, except by using the same key, i.e., by Bob. The rule for encoding is simple. Suppose that Alice wants to transmit one bit of information. For this she uses one bit of the key, performing an ”exclusive-or” operation with the bit to be transmitted. Bob, on his part, can redo the same operation, which cancels out the first ”exclusive-or”, to decode the transmitted bit.

Unfortunately, the Vernam cipher suffers from a major inconvenience. For the method to remain unbreakable, the key must consist of as many secret bits as the message to be transmitted, since the key can only be used once. Using a key more than once causes the Vernam cipher to lose its property of being unbreakable and allows a fairly easy cryptanalysis after successive transmissions.

Strictly speaking, the secret key must originally be exchanged from hand to hand by Alice and Bob. This means that if one wants to transmit a gigabit of secret information, Alice and Bob must meet to exchange, forexample, a CD-ROM containing a billion random bits. This procedure is not practical because it imposes that Alice and Bob must meet, even if they then want to communicate at a distance of 10.000 km.

Mathematicians have therefore developed other cryp-tographic methods, looking to rectify these difficulties.The first difference between the Vernam cipher and current methods of encoding consists in replacing the simple ”exclusive-or” operation by a much more com-plicated operation between the key and the plaintext message.Using these methods,it is practically infeasible to recover the plaintext from the encoded message, or even to recover the key from the plaintext together with corresponding encoded message,even if the key is much smaller than the message to be sent. This is the case, for example, with the DES block cipher, or the more recent Belgian Rijndael algorithm, chosen to be the new AES standard.

Thanks to these algorithms, Alice and Bob can now exchange a small key, which is useful for encoding big messages. The price to be paid for this advantage is that absolute security is lost, and an assumption must be adopted. In theory, it is now possible to recover the plaintext message from the encoded message, but doing this is sufficiently difficult that we can suppose that the enemy does not have the computational resources to do it.

In practice, this assumption is realistic. A hacker will find it much easier, in general, to exploit the weaknesses of an information processing system itself than to perform the necessary calculations to break the algorithm, even if in possession of todays most powerful computers. Nevertheless, nothing says that in the long term, developments in mathematics or information theory willnot make feasible the extraction of the plaintext message from the encoded message.

The second improvement of modern cryptography is the introduction of public key cryptography, allowing Alice and Bob to exchange secret messages without meeting beforehand to exchange a key.

In public key cryptosystems, widely used these days, each correspondant possesses two keys. One key is pub-lic and known to all (for example, it may be published in a directory) and only permits the encoding of a message, not the decoding. The second key, on the other hand, is private, and only permits decoding. To send a message from Alice to Bob, the procedure is as follows. If she hasnt alreadydonethis, Alice procures Bob ‘s public key (from a public database, or perhaps she simply asks Bob for it). Then, Alice uses Bobs public key to encode her confidential message and sends the encoded information to Bob. Bob is the only person in possession of the corresponding private key, and thus the only person able to decode the message which Alice has just sent him.

In this scheme, the essential idea is that encoding is public, in the sense that anyone can send an encrypted message to Bob, but that decoding requires knowledge of the private key.

Again, the practical advantages of public key cryptography should be weighed against the loss of security that is introduced (compared with the Vernam cipher). A connection exists between the public key and the corresponding private key, and it is therefore possible in theory to recover the one from the other. Nevertheless, it is fortunately very difficult to carry out this operation within the limits of current mathematical knowledge and the power of contemporary computers.

In order to demonstrate these ideas, let us take the example of the Rivest-Shamir-Adleman (RSA) algorithm, which can be used as the basis of a public key cryptosystem. In this system, the private key can be deduced from the public key if one is able to factorise numbers larger than a certain number of digits, which is currently very difficult. In fact, while it is easy to multiply two large prime numbers together, recovering them from the product is much more difficult. Unfortunately, advances in factorisation always raise the bar for cryptographers, who must use keys, and thus numbers to factorise, that are larger and larger. In addition, if a mathematician one day discovers an algorithm enabling the rapid factorisation of large numbers, he will be able to decode all messages encoded with RSA without anyone knowing it, since he has access to all the public keys.

This danger is all the greater since physicists have devised a new method of doing calculations, using a quantum computer. This new generation of computers, still at an essentially theoretical stage, has the property of being able to solve rapidly certain problems that are believed to be difficult with traditional information theoretic techniques. Thus Peter Shor has discovered a quantum algorithm (that is an algorithm that runs on a quantum computer) allowing the factorisation of large numbers in a reasonable time. It seems, therefore, that many dangers are present for the long term security of current cryptographic techniques. Classical cryptography, while popular and currently offering a level of security that is largely sufficient, gives no long term guarantee of the messages it is used to protect. This is why we want to present here an alternative manner of securing the confidentiality of a message, without relying on technological assumptions, or complexity assumptions (i.e., assumptions about the speed with which a certain mathematical operation can be carried out using the computers of today).

Are we then condemned to exchange, by hand and in advance, megabits of secret keys in order to guarantee absolute security? From the point of view of the most fundamental laws of physics known today, there is another possibility. Quantum physics, describing the individual dynamics of each elementary particle (photons, electrons,...) that makes up our universe can offset this difficulty and allows the construction of communication protocols with no security weaknesses. This is the aim of quantum cryptography.

Quantum cryptography was born around 20 years ago when two researchers, Charles Bennett and Gilles Brassard, had the idea of using quantum physics or transmitting confidential messages. The transmission s achieved using individual photons (”quanta” of light) sent from a sender (Alice) to a receiver (Bob) via an optic fibre.

A theorem known as the ”no-cloning theorem” prevents a third party (Eve) from being able to decode the information transmitted. Indeed it can be shown that if one does not have in advance a precise characterization of the quantum state describing the light, and in particular of the state of the photon, then it is impossible to reproduce the state, that is to make a clone. In fact, the simple act of observing a photon, in order to determine its state, disturbs it in such a way that afterwards, one cannot return it to itsinitial state,or produce a clone. The no-cloning theorem is bad news for anyone wanting to determine completely the quantum state of a photon. On the other hand, it can be seen as positive from the point of view of cryptography. Eve, who wants to read the secret information without being detected, needs to copy the quantum state of the photon. Since this is impossible, she must at least determine the quantum state of the photon. But by attempting to do this, she introduces disturbances, and can therefore be detected by Alice and Bob.

The essential goal, then, is for Alice and Bob to exchange a secret key with the assurance that any attempt at eavesdropping by a third party will be detected. If this secret key is correctly transmitted, then Alice and Bob can use it with the Vernam cipher method described above, thus obtaining a cryptosystem that is unconditionally secure even at a distance.

Beginning with the idea of no-cloning, researchers have described a communication protocol that uses the polarisation of photons to encode the bits that will be the secret key. Photons possess two states of polarization that can be distinguished using a polarising filter (such as a calcite crystal, for example). Like this, vertically polarised light will pass through a filter oriented in the same sense, while horizontally polarised light will not pass, but will be abosorbed by the filter. If now the light is diagonally polarised at 45 , only half of the light intensity will pass. What happens if we only allow a single photon at a time, diagonally polarised, to impinge upon the filter? Clearly the photon cannot be divided into two, since it is the indivisible building block of light.

Experiment shows that, as predicted by quantum theory, half of the time the photon will pass through the filter, and half of the time it will be absorbed.