[Accompanying notes for Physsoc (University of Canterbury) seminar on 2/8/2013]
Cryptography consists of making and breaking methods to communicate information without third parties which are able to intercept communications being able to gain knowledge of this information.
1. Cryptography before Quantum Mechanics
In the traditional example Alice and Bob wish to communicate privately despite Eve (who wishes to know what Alice and Bob are communicating) being able to intercept their communications. However in reality the situations in which cryptography has been used is for spies when letters are being intercepted, for the military — especially after the invention of radio, and today on the internet when we access online bank accounts and complete other online transactions.
In order to do this Alice and Bob could try to disguise their message (for example invisible ink or microdots), or they can employ a cipher scheme. The problem with a disguised message is that if a third party discovers the method of hiding the message they can immediately read all following messages. A cipher can be seen as an invertible function mapping the plain text to the enciphered text. The recipient can then apply the inverse function to discover this message. (Note: Strictly speaking does not have to be a function, needs to be a function so it gives a unique message that was sent however the enciphering process can give multiple possible encrypted messages from which one can be randomly chosen.)
However this seems to have the same disadvantage — as soon as the inverse function is discovered messages can immediately be read, so in general we use a function of both the message and a key. Thus even if the function in question is known, without the key which can be regularly changed it may still be possible to maintain security. However as the next example will show security of the key is not sufficient as this may be derivable from the message.
Example 1: Substitution Cipher
Alice and Bob map each letter of the alphabet to another letter. As there are such bijective mappings this is too many for Eve to go through in any reasonable time. However in the English alphabet not all letters are used in equal frequencies in normal text. Hence if we look at the statistical distribution of the various letters in a large section of cipher text, we can identify this with the statistical distribution of letters in normal English, thus allowing us to find the key (the specific bijection used). Also the frequency of combinations of two or more letters in consecutive order can be used. The English language (or any other natural language) only uses a tiny proportion of all possible sequences of characters, the unique properties of the subspace of character sequences can be used in breaking several encryption schemes.
So we also need a function such that there is no such method to determine the key that is implementable in a the length of time we require the message to be secure for given the computing power at the disposal of Eve.
Example 2: One Time Pad
For simplicity we write the message as a string of zeros and ones. As a key we have a random string of zeros and ones of equal length which we only use for this message and never reuse. Then we apply the AND operation (addition modulo 2) to the nth digits of the key and the message to give the nth digit of the encrypted message. The reason this is unbreakable is that given an encrypted message there is a key such that any message of the correct length could be encrypted to give this message. As the key is random and never reused we can not use the keys that would correspond to given messages to determine which is the actual key used, and hence the actual message sent.
The problem is this requires Alice and Bob to have met before in secret and have exchanged an equal amount of data to that which they will in the future wish to communicate, not to mention the added complexity of generating random numbers — which by definition can not be done algorithmically — all random number generators on computers without specific hardware that uses electronic noise or other physical phenomena to generate random numbers, are only using some algorithm to generate pseudorandom numbers. For application such as internet banking this is clearly not highly feasible.
However in the last century there was a revolution in cryptography — public key cryptography. There are two approaches to this. In this Alice and Bob both create a secret number, transmit partial information about this and use this to create a key known to both parties which can’t be created from the partial information.
Examples 3 & 4: Mixing paint and the Diffie–Hellman key exchange
An extremely non-mathematical example of this would be if Alice and Bob wanted to agree on a colour of paint, they could each select their own colour, then send a litre of it mixed with a litre of blue paint to each other, on receipt they can add a litre of their own colour of paint. Eve who intercepts the two paint colours exchanged can not create the mixture of of each of the Alice’s colour, Bob’s colour and the colour Blue.
A more mathematical example is the Diffie–Hellman key exchange. Alice and Bob agree on two numbers and ( prime) in a non-private communication, that could thus potentially have been intercepted by Eve. Alice and Bob create their own secret numbers and . Alice sends bob , while Bob sends Alice (again via unencrypted and interceptible communication, which is henceforth described as a ‘non-private communication’). Alice and Bob can then both create their secret key . Inverting the exponentiation in the multiplicative group is more computationally intensive than the exponentiation done in the group that Alice and Bob do. Because of this by choosing sufficiently large values of , and it can be made so that it is to computationally intensive for Eve to work out the secret key.
In the second you have an enciphering function that is computationally hard to invert, we call this a one-way function. So you then give everyone the enciphering function while keeping its inverse secret. This of course begs the question: how does one invert the function if it has been chosen to be sufficiently computationally hard to invert that people with larger amounts of computing power can’t. The answer is to use a trapdoor one-way function: one that is possible to invert with a bit more knowledge about the function.
Example 5: RSA
An example is RSA: here the encrypting function is , where is the message, is the encrypted message and is the public key where is the product of two primes. \Inverting this function requires additional information about multiplication in the group of invertible elements of the monoid . This information is given by the factorisation of into the primes and . Specifically by Euler’s theorem, (a special case of Lagrange’s theorem in group theory) for being Euler’s totient function — giving the number of integers coprime to and between 1 and . Then . We then solve the congruence for . The solution of this gives the decrypting function as .
The trick to this example is the computational intensity of factorising is far greater than that of multiplying together and , and knowledge of and allows the function to be inverted in a less computationally intensive way.
This discussion of how ‘hard it is for a computer to perform certain tasks requires us to define what we mean by computationally hard.
Generally rather than individual problems (such as factoring 432) which will have some exact number of operations required to solve, we look at the same problem for different ‘sizes of input’, for example factor a number which requires digits to write out (It doesn’t really matter which base we use here). We then look at how the number of operations required to solve this problem relates to . Rather than looking for an exact function we look at various classes of functions. For example multiplying and together is a polynomial time algorithm, roughly speaking; as the number of processor operations (or the number of operations a turing maching would require) is bounded above by a polynomial in . However there is no known algorithm to factor in polynomial time (though we haven’t proven that none exists — in fact such a proof would prove ). The best algorithms for factoring are exponential, so for large enough and we can make the computing power required to factorise arbitrarily larger than that we need to multiply together and .
2. Enter Quantum Mechanics
However quantum mechanics changes this situation in two ways; quantum computers and quantum cryptography.
A quantum computer is one that takes advantages of quantum effects, rather than using classical bits (a two state system – each can either be 0 or 1), a quantum computer uses qubits (which can be in some superposition of 0 and 1: for ). We can not measure the exact state the qubit is in, rather measuring a qubit will return the state 0 with probability and 1 with probability (hence the condition on and ), furthermore the measurement will cause the collapse of the superposition, the state of the qubit will be reduced from the superposition of 0 and 1, to the result of the measurement. An obvious question is why can’t we copy a qubit lots of times and use this to gain measurements of and to arbitrary precision. The answer is that it is impossible to duplicate the state of a qubit – this is known as the no – cloning theorem.
Clearly this means that there is a larger possible number of states for the system – while bits only have possible states, qubits can be in any position of the unit sphere in a space of complex dimensions if the qubits are entangled. In some cases we can utilise this larger phase space to solve problems quicker.
Any classically computable function can be done using circuits formed using the logic gates (see Wikipedia for truth tables) NOT, AND, OR, XOR, NAND, and NOR, however it would be possible to build it using only the NAND gates. We hence call the NAND gate universal. For quantum computers a gate is a linear operator on the phase space and hence corresponds to a unitary matrix – this is because we can see the phase space for the qubits is the unit sphere of a normed vector space, with the basis vectors being an orthonormal basis of allowed classical states. There are hence infinitely many gates, however a universal set is given by the CNOT gate and the single qubit gates. Note that the correspondence to unitary gates means that all quantum gates are invertible.
The CNOT gate does the operation: . This maps the basis vectors , where .
Everything a quantum computer does can be simulated by a classical computer but a quantum computer allows some processes to be done in less operations. The class of computationally ‘easy’ problems – those done in polynomial time is now BQP – those which can be done on a quantum computer with the number of operations being of the order of a polynomial of some parameter . Relevant to cryptography the problem of factoring is in BQP, as is the discrete logarithm problem (the logarithm problem in a finite group). Thus quantum computers can break RSA and the Diffie-Hellman key exchange – if we can build quantum computers with sufficiently many qubits.
Sketch of Shor’s algorithm for finding the prime factorisation of a number
We start with two registers, the first in a superposition of all possible basis states, the second in the state 0:
We then compute for a randomly chosen , in the second register, to gain the superposition
Note tha if is periodic with a period then probably has a factor in common with , which can then be rapidly found using the Euclidean algorithm.
We then find the period of . Firstly we measure the second register to collapse the state to:
where is the measured value of .
If is an integer the following steps are slightly simplified so we assume this.
We then apply the Fourier transform
to gain the state (in the first register):
where if and only if is a multiple of . We now measure the register to gain , from this we can calculate if and have no common factors, it turns out that this is the case with a sufficiently high probability for this algorithm to be an efficient quantum algorithm for calculating the prime factorisation of a number. Note that we have to repeat this multiple times to gain all prime factors. Note also that to prove this properly we would have to show that all the above operations are possible using a polynomial bounded number of quantum gates and that the claimed link between the period and factors actually holds.
Thus when large scale quantum computers are built we will have to only use public key ciphers if which utilise one way functions that are still one way if one happens to own a quantum computer. There are some possible approaches for this such as lattice-based cryptography.
However quantum mechanics also makes the unbreakable cipher mentioned earlier feasible in that it gives a way in which Alice and Bob can exchange a key without physically meeting in secret and passing over stacks of one-time pads (keys for the cipher).
Quantum key distribution – the BB84 protocol
We use qubits (probably realised as photons of different polarisations) in the states , ,
, using a physical system such that all of these states can be outcomes of measurements (that is to say corresponds to a real state as well as being a superposition of the states and ).
Alice then sends a sequence of qubits randomly chosen from the above options to Bob. If we are to ignore noise (this can be compensated for) then Bob receives these qubits and randomly decides to measure them against the basis or against the basis . Alice then tells Bob (in a non-private communication) whether each qubit was in or in . For the ones where the qubit was one of the elements of the basis elements Bob gets the correct result when he measures the qubit, and hence both Alice and Bob know what the qubit is. The information from the rest of the qubits is discarded. However the question is has Eve measured these qubits also – this can however be detected from the resulting disturbance to the state of the qubits. Eve’s measurements if with respect of the basis not containing the qubits state would change the state of the qubit – and this would occur roughly half the time. Then of these half would be measured by Bob with respect to the basis that the qubit was originally a member of. In half these cases the second measurement will cause collapse into the opposite state to which Alice sent it in. Thus if Eve has measured all qubits we expect one quarter to be measured by Bob to have the opposite value to that measured by Eve. For example a qubit could collapse to the state if Eve measures it against the basis , then when Bob measures it in the basis it could collapse to the state . Hence after this point Alice can randomly choose a certain number of qubits and tell their states to Bob (in a non-private communication), if these are not what Bob measured then this has allowed Alice and Bob to detect Eve eavesdropping on the line, and the procedure can be restarted (for a noisy line the number of qubits such that Bob gets a different result from Alice can be used to give a probability of Eve eavesdropping). Once this has been done without detected disturbance, the qubits Alice told Bob the state of can be discarded, and the remaining qubits can be used as the key for one-time pads, thus giving Alice and Bob complete security – if the above protocol is implemented correctly. We can move from the sequence of qubits to a sequence of bits by replacing and by 1, and replacing and by 0.
Where does this leave code-breakers: This scheme if implemented properly is unbreakable, however what this really means on a practical level is that Eve needs to prevent Alice and Bob from using quantum cryptography. Clearly possibilities include cutting fibre optic cables, or interfering with all qubits sent between Alice and Bob. However best of all for applications where the two parties have not met previously (such as your computer and the banks server) a third party Eve could claim to Alice to be Bob
Simon Singh. The code book: the science of secrecy from ancient Egypt to quantum cryptography. Anchor Books 2000.
– This is an excellent (popular) introduction to the subject, and was I think where I first came across cryptography.
Kahn, D. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet. Scribner 1996.
– This is a very in depth history of cryptography.
Michael A. Nielsen, Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press 2000.
– This is a in depth book on quantum computers and quantum information. The first chapter provides a very nice introduction to the topic, and is a great place to find out a bit more about the second part of this talk.