Quantum Cryptography Revolution
Are you ready for the quantum revolution in secure communications? OK, so you’re not ready. Don’t panic, it’s still a long time coming. However, it is useful to be cognizant with the latest cryptographic developments and to get a glimpse of what is coming over the horizon. These developments will change the way we do things in the future. There are some interesting issues that you will need to address to make practical use of the new cryptographic technologies. This article will give you an overview of all that.
Whilst ‘quantum cryptography’ has become a fashionable idea in the world of cyber security, not everyone understands the basic theory behind it. So, as background, here’s The Attributer’s Guide to Quantum Physics(1) for Dummies.
It is more than a hundred years since quantum physics was discovered (invented?) in the early twentieth century. The main pioneers of these theories were physicists like Niels Bohr, Ernest Rutherford, Erwin Schrodinger, Max Planck, and many more. Albert Einstein found the whole thing difficult to accept, although his work did support the quantum theories. He was the first physicist to point out that Planck’s discovery of the quantum nature of energy would require a rewriting of the laws of physics.
In 1905 Einstein proposed that electromagnetic radiation sometimes acts as a particle– a light quantum (later named a photon). Bohr disliked this particle-wave duality, and the theoretical debates and thought experiments raged on for decades (and they still do). Bohr famously said, “Anyone who is not shocked by quantum theory has not understood it.” What he meant was that quantum theory is totally counter-intuitive when considered against our existential experience of the macro-world (Isaac Newton’s world of classical mechanics). The first time you encounter these ideas they make your head spin.
But we get ahead of ourselves. It’s time to explore the theories a little. Bear in mind that the topic is by no means fully understood, that there are many paradoxes and areas of vague understanding, and that all of quantum theory is ‘just a model’ that physicists are constantly revising to get closer to the ‘truth’, whatever that may be. Don’t be surprised if they throw parts of it out in the future as they find that the theory doesn’t fit the experimental results. It’s a constant game of testing hypotheses with laboratory experiments.
The word ‘quantum’ is derived from the Latin quantus meaning ‘how large’; the same root as for the English word ‘quantity’. A physical entity that can only assume certain discrete values in one or more of its measured properties, we say is ‘quantized’. It generally applies in the world of sub-atomic particle physics, but there are many examples in the macro-physical world that help to understand the concept.
If you go the supermarket to buy baked beans you will encounter quantization of the product. Heinz Baked Beanz are packaged and sold in tins of three sizes: 150g, 200g and 415g(2). These are the possible values of the quantum number for tins of this product: measurements of the weight (mass) of beans in a given tin. There are no tins with in-between weights – you are restricted to these three quantum values. You may buy multi-packs, but only in integer multiples of the basic quanta.
An electron orbiting an atomic nucleus is held in its orbit(3) by the amount of energy that it possesses. The greater its energy level, the more distant is its orbit. These energy levels are quantized: they can only assume certain predetermined values (just like the tins on beans). Solving Schrodinger’s equation for the hydrogen atom yields four solutions (four quantum numbers): The principle quantum number (the radius of the Rutherford-Bohr orbital, also known as a ‘shell’), the orbital quantum number (the angular momentum of the electron in its orbit), the magnetic quantum number (distinguishing the available orbits within a sub-shell), and the spin quantum number (the internal angular momentum of the electron). Each of these quantum numbers can have only certain quantum values.
A set of quantum numbers defines exclusively a quantum state. No two electrons may simultaneously occupy the same quantum state within a given quantum system (in this case the atom). This last is known as the Pauli exclusion principle. Thus possible atomic configurations are limited by these rules and principles, giving rise to the periodic table of elements with its fixed structure.
Elements are characterized by their atomic number – the number of protons in the atomic nucleus. These positively charged protons keep an equal number of negatively charged electrons in orbit around the nucleus. The lower numbered elements have electrons held in orbital energy shells close to the nucleus. Within an energy shell there are a limited number of possible quantum states available, because the quantum numbers have limited values. When electrons occupy all those states, the shell is full. Extra electrons for higher numbered elements can occupy the next shell out from the nucleus. The hydrogen atom has a single shell. The heavy elements have multiple concentric shells at different distances from the nucleus. The level of the shell (its radius) is described by the principle quantum number. This is the main measure of the electron’s energy and a good approximation for its total energy. The other quantum numbers (such as ‘spin’) account for minor differences in an electron’s energy level.
You can excite an electron into a higher quantum state by feeding it a pulse of energy. Heating or electrical input will excite a valance electron(4) from its ground state into a higher quantum state called an excited state. Note the quantum nature of this excitement. The electron jumps from its ground state to its excited state in one single quantum leap. It does not pass through any intermediate energy states – they are forbidden. The excited state is unstable and will last only a short time. The electron will fall back to its ground state almost immediately and in doing so will emit a quantum of electromagnetic energy – a photon. Each element in the periodic table has a signature frequency (colour) for the photons emitted. The energy of an emitted photon is equal to the energy difference between the excited state of the electron and its ground state. The frequency of the photon is related to its energy. Hence we see the variation in colour (frequency) for each element.
If you heat a piece of copper in a flame you will see the signature green colour of that element. A streetlight produces the signature orange colour of sodium. Each element has its own frequencies at which excited atoms emit photons when returning to the ground state. The entire electromagnetic spectrum comprises all the possible frequencies for these emissions. Not all of them are in the visible region of the spectrum. When a light source is analysed into ‘spectrum lines’, the frequencies of the observed ‘lines’ give the signature of all the elements used to create that light source (a technique known as spectrometry).
In the case of the orange sodium line it was later found (with improved spectrometer equipment) that it is in fact two lines, very close together. This accounts for the difference in spin, producing two slightly different energy levels in the same electron shell. Now they can see multiple lines distributed around the main pair in the form of an interference pattern. Each individual quantum state has a spectrum line for a unique energy level. No two can be the same, but they can be coherent.
This technique is used in cosmological research to determine which elements are present in a distant light source. It is also used in laser technology to produce an intense beam of coherent(5) monochromatic light (or other electromagnetic radiation) by stimulated emission of photons from excited atoms or molecules.
Quantum Applications in Cryptography
There are many ways in which quantum states can be used to represent information in the form of quantum bits (qubits). This leads to a field of research generally called quantum information processing. There are two main applications of quantum information processing in the world of cyber security: breaking current cryptography to render it useless; and creating a key exchange protocol that is provably unbreakable. So, the universe and its laws take away something with one hand whilst giving something even better with the other hand. Or does it? We shall see.
Today’s computers based on transistor architecture have limits on computational power: heat dissipation, packing density in 2- and 3-dimensional structures and clock speed. If the cryptographic key space is large enough, data is secure against brute force attacks, (but beware, there are other attack methods and encryption does not solve all security problems).
The Noble prize winning theoretical physicist and mathematician, Richard Feynman, first floated the idea of a quantum computer in around 1982. Quantum computer architecture avoids these conventional transistor limitations by providing massive parallelism at the physical level. This depends on the application of a quantum principle called superposition. When two or more quantum states are combined (overlaid) they produce another quantum state representing the addition of the component states. This combined state is a simultaneous representation of all the components.
As an example consider the interference pattern of peaks and troughs produced when two waves interact. You can observe it when the tide is high and waves are hitting the sea wall from several directions and being reflected back again. The pattern is complex but is the result of the combined wave amplitudes and frequencies, and is a quantum state pattern in its own right. The significance for quantum computing is that all solutions to the computation are simultaneously available. There is no ‘linear search’ required as with conventional digital computers, even with parallel processing.
Another principle of quantum theory that is being applied to the building of quantum computers is that of quantum entanglement. Two quantum particles separated by large distance can be entangled in such a way that they have correlated quantum state properties. Take for example the quantum state of particle spin. Entanglement occurs when a pair of particles, such as photons, interacts physically. A laser beam fired through a certain type of crystal can cause individual photons to be split into pairs of entangled photons. A large distance, hundreds of kilometres or even more, can separate the photons. When observed, photon A takes on an up-spin state (with 0.5 probability). Entangled photon B, though now far away, takes up a state relative to that of photon A (in this case, a down-spin state) with probability 1. The transfer of state between photon A and photon B takes place at a speed of at least 10,000 times the speed of light, possibly even instantaneously, regardless of distance. Is that spooky or what? Einstein certainly thought so and said so.
Recent theoretical physics research is looking at this paradox (how can a transfer of state be accomplished at much greater than the speed of light when the speed of light is an absolute maximum?) There is a clear disconnect between theory and experimental results (which show conclusively that entanglement effects happen instantaneously irrespective of distance).
This ‘weirdness’ is not well understood, but current work is focusing on the nature of time itself. Our existential experience is that time always flows forward with an arrow direction that cannot be reversed. Some explanations of entanglement require time to flow in both directions. We say the speed of light is fixed and nothing can travel faster than the speed of light. However speed is determined by distance travelled in a period of time. This assumes that time itself is constant. The theoretical physicists have much work to do on the nature of the space-time continuum to explain the practical results of their experimental physics colleagues.
The entanglement principle is used to store information in an entangled pair. The quantum information bit (qubit) is not held by any particle individually, but by the entangled correlation shared between them. This is hidden until you expose one of the pair of quantum values. If the thought experiment by Schrodinger about the cat in the box (simultaneously alive and dead) were to be modelled with entanglement between two such cats, then when box A were opened and the cat were alive, we would know that the cat in box B is dead. (It’s not clear how that could be achieved, but suspend your disbelief for a few moments to get your head around the idea of entangled particles storing information).
The technical challenges to building the hardware for a quantum computer are centred mainly on the need to protect the qubits from interactions with the environment. If they are exposed to environmental forces the values will be revealed and the computation will be destroyed (a phenomenon called decoherence). The current method of protecting against decoherence is to encode a single qubit across several entangled quantum states. If one state is revealed it does not reveal the value of the qubit, and that component can be repaired, again without revealing the value of qubit.
Materials science will play a big part in the development of quantum computing hardware. Input and output technologies will be largely classical in nature. Current implementations are based on superconducting circuits held at very low temperatures, but there are other technological avenues to explore in building the hardware.
For software (if that’s the right term) development there are algorithms (such as one by Peter Shor in 1994) that can leverage the properties of superposition allowing an entire cryptographic key space to be searched (almost) instantaneously. The key length becomes irrelevant, provided that you can build a quantum computer with sufficient ‘qubits’ – something still not technically possible but experts predict that in future it will be (perhaps 50 qubits within two years from now, and then progressing year by year until millions of entangled cubits are possible). Let’s assume the experts are right and that quantum computing is a threat to all modern cryptographic systems. What shall we do then?
To our (partial) rescue comes quantum cryptography. The concept is based on a fundamental law of physics: if you inspect a quantum state to measure it, you cannot avoid changing the state. Alice and Bob exchange information bit-encoded as quantum particles in a stream of laser-generated single photons. Eve (the eavesdropper) can look at the stream and measure its bits, but will leave a trail that is detectable. Only when Alice and Bob find they have a tamper-free stream will they use it for secure communications. Error detection encoding reveals the changes. The exchanges are generically known as quantum key distribution protocols (QKD).
The history of cryptology is one of new emerging cryptographically secure methods (meaning beyond current technical resources), only to be followed by new cryptanalytic methods to break them. So it goes on. It turns out to be ‘too difficult’ at present to produce a stream of true single photons required for QKD. In practice a stream of attenuated time-gap laser pulses is used, each pulse having a Poisson-distributed probability of containing less than one photon of energy. Some pulses will contain no photons, some one, and some will be multi-photon. This enables an attack scenario known as ‘photon number splitting’ (PNS). Let’s just say it’s complicated, but Eve can exploit this without disturbing the quantum states. Whoops!
Next up comes the ‘decoy state’ approach. Using randomly chosen, multiple intensity levels at the transmitter’s source, (one signal state and several decoy states), the photon number statistics vary throughout the channel. At the end of the transmission Alice announces publicly which intensity level has been used for each qubit. This defeats the PNS attack. No channel is error free, and error rates increase with distance. To be successful Eve would need to maintain the expected bit error rate (BER) at the receiver’s end (Bob). She cannot achieve this with multiple photon statistics. If Alice and Bob monitor all the BERs they will detect an attack by Eve. Phew!
Related Cryptographic Research
Some readers may be familiar with another relatively new form of ciphering known as holographic cryptography. This uses the disruption of a holographic optical image using a variety of image masks. The image is illuminated with coherent laser beams producing an interference pattern, and in this respect bears some conceptual similarities to the superposition of quantum states. However, the similarity ends there. This is not quantum computing. You need to have the optical masks (keys) to decipher the original image. Using both a phase change mask (phase key) and an amplitude change mask (amplitude key) along with 3-D rotation, the image is securely encrypted. It is not clear from the current published works reviewed by The Attributer whether or not this will resist a quantum computer attack, but it is likely going to be as vulnerable as any bit-manipulation algorithm.
There is a story (true or not is not known) from WWII in which the RAF allegedly translated messages into Welsh language before encrypting them. The point of this being that the plaintext was not recognisable as expected output and therefore was overlooked by the German code breakers, even though it was correct. This suggests that a similar technique might be used in holographic encryption by first embedding the real image in a large background of random image noise. Would this prevent the deciphered plaintext from being identified? Probably not.
There are also a variety of ‘keyless encryption algorithms’ being developed. These depend on using the original plaintext data to manipulate itself into ciphertext. Again the literature review by The Attributer has revealed no specific comments on resistance to quantum computing, but it seems unlikely.
So there you have it: The Attributer’s Guide to Quantum Physics for Dummies. The research effort will go on and on. Thrust and parry. Make and break. However, The Attributer wants to draw attention to some things that seem to be ignored with the present direction of cryptographic research into QKD and quantum computing.
First of all, let’s be reminded that security mechanisms alone are not a means to secure a system. You can develop a hi-tech locking mechanism for your car or your house, but if someone knocks you on the head and steals your keys they have easy access to both. What SABSA Thinking tells us is that it’s all about security architecture: end-to-end, holistic security that addresses all identified risks and deals with the interaction between those risks. One new mechanism might help but it is not in itself architecture.
Secondly SABSA security architecture is service oriented, using security mechanisms to build security services. Thus a new mechanism has to be serviceable. It has to be packaged into a service unit with a service level agreement and a service interface by which it can be called. There is clearly a lot of work to be done turning quantum information processing mechanisms into services.
Architecture must address a range of interacting risks, one of which is loss of service availability. One of the classical attack methods on any security system is to disable it so that the users are forced to move to another capability to maintain business continuity. If Eve were to flood the QKD photon channel with noise and mount a denial of service (DoS) attack, what will Alice and Bob do then? As always in SABSA Thinking, security architecture must be a holistic, end-to-end approach. The most secure techniques will never help us if there are other, easier attack routes for our adversaries.
Earlier in this article we talked about partial rescue by quantum cryptography. QKD at present only addresses transmission of information. What about stored information? Conventional cryptography depends on exploiting mathematical problems that are ‘computationally hard’ to solve with conventional digital computers. RSA is a cryptographic algorithm that depends on one such piece of mathematics: the difficulty in factoring the product of two large prime numbers.
John Martinis at UCSB has shown that to solve this ‘hard problem’ (for RSA 2048) with today’s transistor computers you would need to build a server farm occupying around 25% of the area of the North America, at a cost of $106 trillion, consuming 106 terawatts of power (which is 105 times the world output), and would consume the world’s supply of fossil fuels in one day. However, it would take a ten-year run time to get the solution. RSA is safe for the time being.
Conversely Martinis has estimated that for much lower cost ($100 billion – but still too expensive) you could use a quantum computer based on scaled up versions of today’s technology to ‘break’ RSA 2048 in around 16 hours and consume only 10 megawatts. The cost is still prohibitive but the example demonstrates the real threat posed by quantum computing. Once the cost comes down, as it will, RSA will fall.
How will quantum technology be developed that can use computationally hard problems of a different type – hard even for a quantum computer? The answer here is not in the qubit technology but in the mathematics. We need some new innovative maths to provide such hard problems. There seems to be little public evidence of progress at present in this direction. However, the economic value of such maths will be so high that one imagines that the research may well be being conducted in secret.
And another thing: what about all that data currently encrypted with today’s crypto technology? Once the quantum computer is available, any data collected today (encrypted with strong AES 256 for example) with expectations of long security life, will fall immediately to the superposition search capabilities of quantum computers. Be careful what you commit to public collection for future harvesting in the post-quantum era.
A more sinister aspect of all this is bothering The Attributer. The sudden appearance of quantum computers will not benefit every one in the world. Early adopters will be rich and powerful parties. If you want to estimate who will get them first, look around at those who already possess today’s supercomputers. This could create an asymmetry in society that would have serious implications for the balance of power and who holds it. These issues need to be held up for public debate. Society itself is at risk, because opportunities for the few will lead to threats for the many.
The SABSA Institute vision statement talks of a ‘a global business world of the future, leveraging the power of digital technologies, enabled in the management of information risk, information assurance and information security through the adoption of SABSA as the framework and methodology of first choice for commercial, industrial, educational, government, military and charitable enterprises, regardless of industry sector, nationality, size or socio-economic status, and leading to enhancements in social well-being and economic success’. The Attributer has concerns that quantum technology may prove to be a disturbance to this vision. The SABSA Community has a social responsibility to ensure that social solutions are matched to technology solutions.
(1) Also known as Quantum Mechanics.
(2) The Attributer is quoting the sizes sold in the UK. There may be differences in other countries.
(3) This description of an orbit treats the electron as a particle, first proposed by Niels Bohr and Ernest Rutherford in 1913. They saw the electron as similar to a planet orbiting the sun in our solar system. There is an alternative description of an electron as an electromagnetic wave (described by the Schrodinger equation) in which the orbit is a probability density cloud surrounding the nucleus. Both models are useful for describing electron behaviour in terms of real world existential human experience, but the sub-atomic reality may be something different. These are only visualisation models that help us to observe and predict electron behaviour. The Schrodinger equation gives the complete mathematical description, but not necessarily the human visualisation.
(4) A valance electron is one in the outer energy shell of the atom. It is the type of electron available for chemical reactions with other atoms.
(5) Two wave sources are perfectly coherent if they have a constant phase difference, the same frequency, and the same waveform. Coherence is an ideal property of waves that enables a stationary interference pattern (constant in time and space). Coherence is necessary property for entanglement.
(With acknowledgement for the input in private conversations from David Fagan).