Communicating freely


Archive for the ‘encryption’ Category

Quantum encryption for real people

Tuesday, July 11th, 2006

I’m going to be attending a security round-table at Birmingham University this Thursday and I’ve been trying to create a short, simple introduction to quantum encryption for real people.  That’s more difficult than it sounds…

The work in progress is below…

Quantum encryption is a very young field.  The first public research into quantum encryption was conducted by Stephen Wiesner at Columbia University in New York during the early 1970s.  His paper ‘Conjugate Coding’ was published in 1983 in SIGACT News.  Wiesner’s paper had previously been rejected by IEEE Information Theory.  This is indicative of the unusual nature of the field; Einstein referred to quantum entanglement – a principle used in quantum encryption – as "spooky action at a distance."  The normal laws of physics do not apply in quantum relationships.

Quantum encryption is focused on finding a solution to the key distribution problem.  This is a problem with ensuring that two users who wish to communicate secretly will use a genuinely secret key for their communication.  In many communication situations it is impossible to do this in advance.  This means users have to agree a secret key at the time of communication.  A problem arises in trying to agree this key without revealing it to eavesdroppers.

At the moment secret keys are shared using systems like Diffie-Hellman key exchange.  Diffie-Hellman uses very large prime numbers to agree a secret key and assumes that analysis of the exchange is very difficult.  While this is true of today’s computers it may not be true of those deployed tomorrow.  It will certainly not be true when quantum computers enter production.  They will be able to factor large integers instantly.

Quantum encryption uses Quantum Key Distribution (QKD).  This is a method of generating a verifiable secret key that can be transmitted between two people but cannot be altered in transit without the alterations being detected.  Two different aspects of quantum physics can be employed to accomplish this; one is the Heisenberg uncertainty principle and the other is quantum entanglement.  Both methods are generally accomplished through the transmission of photons.

The uncertainty principle is applied to quantum encryption through the polarisation of photons.  In observing the state of a photon a secret key can be obtained.  An example is that vertical photon polarisation can constitute the binary "0" and horizontal polarisation the binary "1".   The strength of photon polarisation is that it is possible to observe photons in different ways: rectilinear, circular, and diagonal.  When you observe a photon in one way you alter the conjugates that could be obtained by observing it in another way.  Unless you know how you should be looking at the photon you cannot obtain useful information about it.  It is also impossible to intercept a polarised stream of  photons.  It is virtually impossible to read the stream without degrading it to a detectable extent.

Quantum entanglement is applied to quantum encryption through the entanglement of individual photons.  This is a genuinely “spooky action” that results in the two photons having a mutual relationship that does not rely on time or space.  If one photon is altered than the other will also change state.  The result of measurements of photon states are random but shared.  It is virtually impossible to either predict or intercept this form of communication.  There is some degree of discrepancy possible between Alice and Bob’s measurements of the changed states but an attempt at eavesdropping would noticeably degrade the data stream.

As those already familiar with encryption will have guessed both the uncertainty principle and quantum entanglement offer methods of exchanging secret keys that are highly resistant to man-in-the-middle attacks.  It is very difficult to intercept photon communication streams.  The Observer Effect is one of the primary reasons for this; the very act of observing the photons results in altering their states.  This will both reduce the coherency of the message being transmitted and ensure that both Alice and Bob will know their stream is being intercepted.  The difficulty of interception is compounded with quantum entanglement.  The only way to reliably intercept an entangled stream would be through introducing a third entangled photon.  However, this would weaken each photon to such a degree that it would be easily detectable.

There are two possible ways to intercept quantum encrypted communication streams.  One is where an attacker (Eve) manages to pretend to be Bob when talking to Alice and to pretend to be Alice when talking to Bob.  If Eve assumed these identities it would be possible to act as a silent observer of the data stream.  The second interception method would involve sending large pulses of light towards either Alice or Bob’s transmission equipment between the legitimate communication pulses.  The reflection of the massive light pulse could indicate the polarisation of Alice or Bob’s equipment.  This is potentially useful on encryption relying on the uncertainty principle.

A limit to quantum encryption based on the uncertainty principle is deniability.  The act of intercepting a polarised photon stream will place some data in Eve’s hands.  If Alice and Bob detect the interception and switch keys during their conversation they will not have ensured they can deny that the conversation took place.  Eve will have partial data of the conversation.  If the the data Alice and Bob changed with the switch of their keys is already partially known to Eve, Eve has proof that the conversation took place.

One method of strengthening quantum encryption is privacy amplification.  Privacy amplification is where Alice and Bob use the initial strength of quantum encryption to establish a secret key.  This secret key is used to make further secret keys that Eve will have no information about.  Privacy amplification provides additional protection but does not reduce the probability of eavesdropping to zero.  It is important to bear in mind that there is no such thing as a ‘completely secret’ communication method.

Sources:

Quantum cryptography, http://en.wikipedia.org/wiki/Quantum_key_distribution

Quantum Cryptography Tutorial, http://www.cs.dartmouth.edu/~jford/crypto.html

Quantum Encryption progresses, http://tonytalkstech.com/2004/05/04/quantum-encryption-progresses/