Security, insecurity, paranoia and quantum mechanics

Preamble

Nearly all of you will carry an ATM card and use it to access your money via a bank autoteller machine. To get at your money you require the card and a “secret” PIN (personal identification number) which is usually four digits long. This PIN protects the machine, in that it establishes your identity. The machine, of course, only gives you money. It is sobering to realise that ATM fraud netts thieves in excess of £100 million each year in the UK alone. Some of you attending this lecture will have been victims of this.

We are all familiar with the concept of computer hacking, whereby individuals use the internet to obtain unauthorised access to computers. It may be some comfort to discover that even the greatest are not immune. The following excerpts are from an article by Damian Whitforth in The Times, February 16^th 2000:

President Clinton had an astonishing confession to make. “Personally” he said, “I would like to see more porn on the internet”. Mr Clinton had given his first live online interview to CNN, which was confident that it had the technology to stop interference with its website for the duration. Instead, pranksters had a field day, posting ribald remarks that were attributed to Mr Clinton and asking impertinent questions.

 

Secure communications

At the heart of information security is the communications problem. If we can live without communications then we can greatly increase security by physical isolation. On the other hand, if we can communicate securely then we can spend our (electronic) money and exchange information safely.

The simplest and oldest method of secure communication is single key cryptography. The concept is to lock away our message in a strong box (too strong to break) and to send the box to our intended recipient. If they have a copy of the key used to lock the box then they can open it and retrieve the message. This is a good moment to introduce our cast of characters: the person transmitting a message is universally called “Alice” and her intended recipient is called “Bob”. The third character, whom we’ll meet shortly, is “Eve” the eavesdropper. The secrecy of single key cryptography relies crucially on the secrecy of the key, the only copies of which must be held by Alice and Bob and, of course, these two keys need to be identical.

In practice there is no box but rather the message is enciphered using a secret key in the form of a piece of information. In the digital world, all messages are just a string of zeros and ones (… 00010010100100010001011 …) and so can be thought of simply as a (large) number. The key will be another number and the cipher text is produced by a mathematical operation on these two numbers. The vital question, of course: “is it secure?”.

Perfect security can be achieved using the Vernam cipher, or one-time pad. For this to work we require Alice and Bob to share a secret key in the form of a random number that is the same length (has the same number of binary digits or bits) as the message they wish to share. The cryptogram, or ciphertext, is generated by bit-wise addition modulo 2, which we denote ?. This means that for each digit if the message and key bits are the same (both 0 or both 1) then the ciphertext is 0, but if they are different then it is 1. A simple example may clarify the point:

message	011010001 …
key	101001001 … ?
ciphertext
	110011000 …

 

All that Bob needs to do is to repeat the operation with his copy of the key:

ciphertext	110011000	…
key	101001001	… ?
message
	011010001	…

 

The method is completely secure if the key is truly secret and, crucially, is used only once. This secrecy is a consequence of the fact that the key is a random number and it necessarily follows, therefore, that the ciphertext is also a random number.

There are two difficulties with the one-time pad: first we need to establish a secret key with our (distant) correspondent and second that we need to use large numbers of very long keys for even the most straightforward secure communications. Maybe there is a simpler way? Let us return to the locked-box concept and suppose that the box has not one lock but two, one of which fits a key held only by Alice and the other that fits a key held only by Bob. Alice can put the message in the box, secure her lock and send the box to Bob who secures his lock and returns the box (now double-locked). Alice can undo her lock and return the box to Bob who can unlock it and retrieve the message (M). The box makes three journeys and is always closed, so surely it is secure? Let us see what happens if Alice and Bob each used their own key ( K_A and K_B ) in an arrangement similar to the one-time pad.

 

Alice locks the case	M ?KA =C1
Bob locks the case	C1?KB = M ?KA ?KB =C2
Alice unlocks the case
	C2 ?KA = M ?KA ?KB ?KA =C3
Bob unlocks the case	C3?KB=M

 

At first sight these seems to be secure, as Eve has access only to the three random ciphertexts C₁ , C₂ and C₃ . The modulo 2 sum of these three ciphertexts, however, reveals the original message without difficulty:

• • C₁?C₂ ?C₃ = M

And so Eve, who has access to the transmitted ciphertexts, can retrieve the message. The underlying problem with this scheme is the simplicity of the operation corresponding to modulo addition. A protocol, due to Diffie and Hellman, does indeed work with multiple exchanges in the way suggested but relies, for its security, on the subtleties of modulo arithmetic. We shall not discuss it here, but note that it is closely related to the RSA public key cryptosystem, which we shall discuss shortly.

The second difficulty associated with the one-time pad was the large number of very long keys needed to achieve perfect security. What we need is a method for achieving practical security; something that is good enough. A published and officially approved method is the data encryption standard or DES (or better, the advanced encryption standard – AES). This combines our message and a very much shorter key, usually 56 or 128 bits, in a sequence of mathematical operations to produce a ciphertext. Bob can easily convert the ciphertext back into the original message by Bob, using his copy of the key. The DES scheme is not perfectly secure can be broken by a determined Eve with access to lots of computer power. The question then is “how long will this take?”. We might try to break it using an exhaustive key search; try every possible key until we find a meaningful message. If we had a 40 bit key then the number of possible keys is 2⁴⁰ ? 10¹². If we had a machine capable of a million decryption operations a second then this would take about 6 days. Better algorithms exist, however, and security agencies have admitted to being able to crack 40 bit DES in under one hour. If we increase the length of the key then we greatly increase the number of possible keys. If we use a 128 bit key then the number of possible keys jumps to 2¹²⁸ = 10³⁸. An exhaustive search on the machine described above would then take about 10²⁴ years. But better algorithms do exist so…

A radically different idea is public-key cryptography, in which no pre-arranged secret key is required. We can understand the principle by considering again the analogy of a locked box. In public key cryptography the box has only one lock but the keys required to lock and unlock it are different. Alice can distribute as many locking keys as she likes as long as she keeps safe the only unlocking key. The simplest and most important method for achieving this is the RSA scheme, named after Rivest Shamir and Adleman, who were the first to publish it (it later transpired that a researcher at GCHQ had got there first, but that this had been kept secret.) The RSA scheme relies on the properties of large numbers and of prime numbers in particular. The required inputs are the message, which is the number x, and two very large prime numbers p and q. The first task is to calculate the product of the prime numbers:

• • N = pq.

This is an easy task for even a simple computer. Next we find two numbers e and d such that

• • ed = 1mod( p ?1)(q ?1),

where “mod” means divide by ( p ?1)(q ?1) and keep the remainder. Finding e and d is also easy, if we know p and q, in that an efficient computer algorithm exists for this task. Bob’s public key, which is freely published, consists of the two numbers N and e. His private key is the number d. Alice can encipher her message to Bob using his public key to generate the ciphertext

• • C = x^e mod N .

Bob can equally easily decode the message because he has the private key (we require N to be larger than x so that the decryption process gives a unique text):

• • C^d mod N = (x^e )^d mod N = x.

The private key is mathematically related to the public key but no efficient method is known for finding it from N and e. The difficulty is thought to originate in the problem of factoring N into its component primes, p and q. Numbers up to about 10⁹⁰ can be factored in less than a day so much bigger numbers are needed. If you would like to win $30,000 then you might try the smallest current RSA challenge and factor into its two component primes the 176 (decimal) digit number

RSA-704 =

74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359.

Public key cryptography is computationally intensive and rather slow, while secret key cryptography is very fast. For this reason public key cryptography is generally used for distributing secret keys and for financial transactions (digital signatures). The first of these ideas is simply to use RSA to distribute secret keys for use in DES, AES or a one-time pad. The security of the secret key then relies on the security of the public-key communication. Digital signatures are used as a way to prove to a correspondent that you are who you say you are so that your instructions can safely be acted upon. They are used, for example, for financial transactions. If Bob wishes to prove to Alice that he is indeed Bob, then he encrypts his instruction using his private key. Alice can confirm that this was indeed prepared by Bob, simply by deciphering it using his published public key. Naturally, any one else can also read the message, but the idea here is that no one else could have written it.

At the heart of modern secure communications, information security and indeed our financial system lies secure communications based on public-key cryptography. This, in turn, relies simply on the difficulty of factoring a large number into its component primes. A realistic method for performing this difficult mathematical task would present a real challenge to our banking system, even to the very existence of money!

 

Some quantum physics: polarised photons

For readers with a background in physics, it might be comforting to have the following aside. (Other readers may safely pass over it.)

Aside:

In quantum theory observables are represented by Hermitian operators, which act on a Hilbert space of states. These operators have eigenvalues and eigenstates related to the operator (A ) by the equation

• • A|?_n ? = ?_n|?_n ?

Here the set of eigenvalues {?_n } represents the possible results of a measurement of our observable. If the system has been prepared in the eigenstate |?_n ? then the result of the measurement will be ?_n . It is also possible, however, to prepare superposition states of the system of the general form

• • |? ? = ?_n a_n|?_n ?

For states of this form there is a fundamental uncertainty and we can only give a probability for the measurement result to be ?_n :

• • P (? _n )= |a_n|² .

It is this unpredictability that we rely on for security in quantum key distribution.

End of aside.

 

Light has a polarisation, corresponding to the direction, in the plane perpendicular to the direction of propagation, in which the electric field oscillates. We can associate two distinct states of the polarisation (that is, eigenstates of linear polarisation) with the horizontal and vertical directions. All other possible polarisations can then be written as superpositions of these (see Fig. 1).

States of photon polarisation

 

If we have only one photon (single quantum or “particle” of light) then we can perform only one measurement and this does not allow us to determine the polarisation. We can chose to measure horizontal polarisation (to discriminate between the top two states in Fig. 1) or circular polarisation to distinguish between the bottom two, but we cannot do both. If we measure linear polarisation for a circularly polarised photon then we will get a probabilistic result as depicted in Fig. 2.

A single photon only gives one “click”

 

You can measure one component of polarisation but CANNOT determine an unknown state of polarisation.

It is impossible to determine in which of the six polarisation states, depicted in Fig. 1, our photon has been prepared. This information is known only to the person who prepared the photon. The secrecy of quantum cryptography, or quantum key distribution, is based on this fundamental physical principle.

 

Quantum key distribution

The challenge in quantum key distribution is for Alice and Bob to prepare a secret key for use in DES, AES or a one-time pad. They must do so by communications that may have to take place in the presence of an eavesdropper. Quantum key distribution provides a method to determine whether or not Eve has been listening to the key exchange. If she hasn’t then the key produced may safely be used and if she has then Alice and Bob know to discard the key and to try again.

A quantum key is generated by means of an agreed sequence of operations to be performed by Alice and Bob. There are a number of such sequences or protocols that have been demonstrated, but there is time here only to discuss the earliest and perhaps simplest of these. This protocol was suggested by Bennett and Brassard in 1984 (and hence is universally known as BB84); it formed the basis for much of our theoretical and experimental work and, indeed, for that of the quantum information community. The first step in the BB84 protocol is for Alice to generate a random sequence of 0 and 1s. For each of these she randomly chooses to prepare a linearly polarised photon or a circularly polarised one (see Fig. 3) and sends this to Bob.

 

Quantum cryptography Š quantum key distribution

 

The problem for Eve is that she cannot determine which of the four polarisations was prepared but rather can only measure either linear or circular polarisation. If she measures linear polarisation on a circularly polarised photon then she will get a random answer. If she then uses this information to prepare a corresponding linearly polarised photon to send on to Bob then his measurement will give a result that is not correlated with Alice’s. In other words an error will appear in the Bob’s bit sequence. This idea is summarised in Fig. 4.

The protocol has to be designed in such a way as to make the appearance of such errors inevitable if an eavesdropper has been monitoring the communication between Alice and Bob. It is easiest to follow, first, what happens when there is no eavesdropper activity. For this purpose, a short example of the protocol is given in Fig. 5. In each of the 14 time slots, Alice prepares a photon in one of four polarisation states as described above and transmits this to Bob.

 

 

Eavesdropping (Intercept & resend)

 

 

Bob does not know, of course, the polarisation of each photon and so can only measure either its linear or its circular polarisation. The measurement will give a result and he can then use the scheme in Fig. 3 to turn these results back into 0s and 1s. There then follows a public discussion (not secret) between Alice and Bob in which Bob tells Alice for each time slot whether he measured circular or linear polarisation but not, of course, his measurement result. Alice then tells Bob which measurements are good, in the sense of matching the type of polarisation that she prepared, and which are bad. For example, in time slot 1 Alice prepared a circularly polarised photon and Bob measured linear polarisation so this is a bad measurement, but in time slot 2 Alice prepared a linearly polarised photon and Bob measured linear polarisation so that is a good measurement. Alice and Bob discard the results of the bad measurements and any other time slots (such as 4 and 10) in which Bob failed to find a photon. The resulting shorter sequence of bits (at the bottom of the figure) is a shared random sequence and can form the basis for a secret key known only to Alice and to Bob.

It remains to see what effect Eve has on the protocol. Like Bob, Eve can only make a choice of measuring one property of each photon, linear or circular polarisation. In doing her measurement, however, the photon is absorbed and she needs to prepare a replacement. The only information available for this preparation is her measurement result and this may be incorrect. A sample sequence of events is given in Fig. 6. In each time slot, Eve measures one of the polarisation properties of the photon and prepares a corresponding replacement for sending on to Bob. Alice and Bob, who are not aware of the presence of Eve, follow the protocol as outlined above and generate a shared bit string formed, in the example given in the figure, from time slots 2, 5, 6, 7, 8, 11, 12 and 14. At this stage, Alice and Bob need to check to see if there has been any eavesdropper activity. They do this by selecting a subset of the agreed string and publicly comparing their bit values. Any errors detected are indicative of the presence of an eavesdropper and the communication is regarded as unsafe. In our example, errors occur in time slots 2, 8 and 14. The probability that an eavesdropper has been listening in and is not detected in this way is (3 ₄ )^k where k is the number of bits tested. By making N large, we can make this probability as small as we like. Naturally, the bits used in the test are now publicly known and must be discarded. If no errors are detected, then the remaining (private) bits may be used by Alice and Bob as a secret key.

 

Real systems are a bit more complicated that suggested above, in that noise is always present and we have to be able to prepare a secret key even in the presence of some errors. This rather technical problem has been solved and practical schemes and devices do exist. The first quantum key distribution experiment was performed using free-space transmission over a distance of 30cm. Very quickly, however, optical fibre based systems were developed, with workers at BT being the early pioneers. These have reached a high degree of technical sophistication and one such system exists here in Scotland, in the Laboratory of my colleague Prof. Buller at Heriot-Watt University. Optical fibre is exceptionally transparent but, nevertheless, after several kilometres of propagation there will be little light left, especially when starting at single-photon light levels. For this reason fibre-based quantum key distribution is only realistic for local communications, such as between the financial institutions within the city of London. For longer-range communications satellite-based systems are under development. The idea here is that you exchange a key with a satellite while it is above you and the satellite can then exchange the same key with an intended recipient, somewhere else in the world, when the satellite is above them. The scheme will be secure as long as nobody can break into the satellite or monitor its internal workings.

 

Quantum computers

I trust that readers without a physics background will forgive a second unnecessary aside for the benefit of specialists.

Aside:

A quantum computer works by first replacing each input bit by a two-state quantum system (or “qubit”) such as a polarised photon. For example the binary number 101101001 = 361 becomes

• • 101101001 ? |1?|0?|1?|1?|0?|0?|1?

The computational step is achieved by allowing this state to evolve within a “quantum processor” under the influence of a suitably tailored interaction. Finally, the output is obtained simply by measuring each system to determine whether it is in the state 0 or the state 1 . In general, our quantum processor will also require additional qubits in order to evaluate the most general of functions.

The big advantage of a quantum processor derives directly from the superposition principle. This means that we do not have to give our single quantum processor one n-bit number to work on but rather we can give it a superposition of all possible numbers between 1 and 2ⁿ at the same time by preparing our input in the state

• • 2^?n/2 (|0?+|1?) (|0?+|1?) (|0?+|1?)…

 

It is this, plus judicious exploitation of quantum interference, that underlies the dramatically enhanced (potential) performance of quantum computers.

End of aside.

 

The superposition principle, which allows us to make photons with polarisations other than horizontal and vertical, means that we can replace each bit from a classical computer (0 or 1) with a superposition of both values (0 and 1). A single processor with a string of n input bits can then work on all the numbers between 1 and 2ⁿ at the same time. For n = 100, for example, our single processor is effectively calculating in excess of a million, million output numbers at the same time. There is the potential here for a dramatic even revolutionary enhancement in our computational abilities if we can build and run a quantum computer. The set is realistically solvable problems depicted in Fig. 7. The smallest grouping is the set of all possible problems that can be solved by a conventional computer. Surprisingly, adding a bit of randomness to the operation of the computer can make it more powerful and the set of problems that can be solved on such a machine includes the larger set. Bigger still is the set of problems that have been shown to be solvable on a quantum computer.

 

Solvability can be given a precise meaning by considering the way in which the required resources, for example computing time and memory, scale with the size of the numbers being calculated. To this end let us suppose that our number of interest, N, can be written in binary as n digits ( N ~ 2ⁿ ). An important example problem is finding the period of a function (how far we have to go before it repeats itself). Classically, this requires a time that is proportional to N, but a quantum algorthim requires only a time proportional to log² N = n² . To appreciate the difference, we might note that for n = 100, the quantum value is 10,000 but the classical value is approximately 1,000,000,000,000.

The most dramatic boost for quantum computer science came with the publication of Shor’s algorithm for the efficient factoring of the product of two large primes. This exploits the speed up in the period-finding problem, mentioned above, to dramatically reduce the time taken to find the two prime factors, p and q, of any selected product, N. The in-principle time required for factoring in this way is

Naïve classical trial:	T ~ N1/ 2 = 2n / 2
Best known classical:	T ~ 23 n log2 n
Shor’s algorithm:	T ~ polynomial(log N) = polynomial(n)

 

The complicated form of the behaviour of the best known (published) algorithm is indicative of the amount of effort that has gone into studying this problem. The change to polynomial scaling amounts to making factoring a solvable problem on a quantum computer.

But if factoring is a solvable problem on a quantum computer and if we rely on the difficulty of factoring for our information and financial security, then what happens to money when quantum computers come along?

 

 

Conclusions

It is natural to conclude this lecture by referring back to its title.

 

Security:

In the modern world, money is a number stored in a computer file and it is spent by electronic communications. The security of all of this relies, ultimately, on the difficulty of certain mathematical operations (notably factoring).

 

Insecurity:

The more we communicate, the more we are under threat. Identity theft, ATM and internet fraud are becoming part of modern life.

 

Paranoia:

Even if we can plug the gaps in current systems, quantum computers (when they become available) will render all current “secure” protocols insecure. Money will be worthless!

 

Quantum mechanics:

Quantum key distribution offers a radically different approach in which security is assured by the laws of quantum physics. It is the only current candidate for security in a world with quantum computers.

A prototype for quantum ATM transactions was announced by researchers at Bristol University late in 2007.