Mustafa Khan

Working On Encryption Using Quantum Physics

Posted 12 December, 2019 by Mustafa Khan

In December of 2019 I visited the University of Waterloo’s Institute for Quantum Computing and worked on a really interesting quantum physics experiment! These are my experiences and takeaways from the trip.


As is the case with most of quantum physics, we began our lab with a thought experiment: How can Alice send a private message M to Bob in a secure manner? If you are aware of the rich history of transmitting secure messages from one place to another, you will quickly realize that this question is the cornerstone of cryptography! The aim of the lab we were conducting was to use something known as Quantum Key Distribution (QKD) in order to tackle this problem.


So, what is Quantum Key Distribution?


Quantum Key Distribution provides a way of distributing and sharing private keys in a secure manner. The security of QKD is based on a fundamental characteristic of quantum mechanics: The act of measuring a quantum system disturbs the system. Therefore, an eavesdropper (called Eve) trying to intercept an exchange done through this process will inexorably leave detectable traces. This allows the parties trying to establish a secure transmission (Alice and Bob) to discard the corrupted information and begin again. Of course, Alice can’t use this technique to send a private message, because it’s only possible to detect Eve after she has listened in. Instead, Alice uses it to send Bob a key — a one-time pad — that he can use to encrypt a message and send it over a classical channel. A one-time pad is provably secure, provided nobody else knows the key.


What does this actually look like?


Well, let’s recap some physics. Unpolarized light waves are made of electro-magnetic waves oscillating in all sorts of directions. Polarized light waves are light waves in which the vibrations occur in a single plane. The process of transforming unpolarized light into polarized light is known as polarization and is shown below:



From your sunglasses to the apparatus we used in the labs shown below, polarizers come in all shapes and sizes.



Next, we need to understand the Heisenberg Uncertainty Principle (HUP), which states that in a quantum system only one property of a pair of conjugate properties can be known with certainty. Heisenberg, who was initially referring to the position and momentum of a particle, described how any conceivable measurement of a particle’s position would disturbs its conjugate property, the momentum. It is therefore impossible to simultaneously know both properties with certainty. Quantum cryptography can leverage this principle but generally uses the polarization of photons on different bases as the conjugate properties in question. This is because photons can be exchanged over fiber optic links and are perhaps the most practical quantum systems for transmission between two parties wishing to perform key exchange.


One principle of quantum mechanics, the no cloning theorem, intuitively follows from Heisenberg’s Uncertainty Principle. The no cloning theorem, published by Wooters, Zurek, and Dieks in 1982 stated that it is impossible to create identical copies of an arbitrary unknown quantum state. One could see that without the no cloning theorem, it would be possible to circumvent Heisenberg’s uncertainty principle by creating multiple copies of a quantum state and measuring a different conjugate property on each copy. This would allow one to simultaneously know with certainty both conjugate properties of the original quantum particle which would violate HUP.


The other important principle on which QKD can be based is the principle of quantum entanglement. It is possible for two particles to become entangled such that when a particular property is measured in one particle, the opposite state will be observed on the entangled particle instantaneously. This is true regardless of the distance between the entangled particles. It is impossible, however, to predict prior to measurement what state will be observed thus it is not possible to communicate via entangled particles without discussing the observations over a classical channel. The process of communicating using entangled states, aided by a classical information channel, is known as quantum teleportation and is the basis of Eckert’s protocol (another method of encryption that uses quantum physics, however, will not be our main focus).


In 1984 Charles Bennett and Gilles Brassard published the first QKD protocol. It was based on Heisenberg’s Uncertainty Principle and is simply known as the BB84 protocol after the authors names and the year in which it was published. It is still one of the most prominent protocols and one could argue that all of the other HUP based protocols are essentially variants of the BB84 idea. The basic idea for all of these protocols then is that Alice can transmit a random secret key to Bob by sending a string of photons where the secret key’s bits are encoded in the polarization of the photons. Heisenberg’s Uncertainty Principle can be used to guarantee that an Eavesdropper cannot measure these photons and transmit them on to Bob without disturbing the photon’s state in a detectable way thus revealing her presence. This is the protocol we used at the IQC to encrypt a secret key.


The image below shows how a bit can be encoded in the polarization state of a photon in BB84.



We define a binary 0 as a polarization of 0 degrees in the rectilinear bases or 45 degrees in the diagonal bases. Similarly a binary 1 can be 90 degrees in the rectilinear bases or 135 in diagonal bases. Thus a bit can be represented by polarizing the photon in either one of two bases.


In the first phase, Alice will communicate to Bob over a quantum channel. Alice begins by choosing a random string of bits. For each bit, Alice will randomly choose either a rectilinear or diagonal basis by which to encode the bit. She will transmit a photon for each bit with the corresponding polarization to Bob. For every photon Bob receives, he will measure the photon’s polarization by a randomly chosen basis. If, for a particular photon, Bob chose the same basis as Alice, then in principle, Bob should measure the same polarization and thus he can correctly infer the bit that Alice intended to send. If he chose the wrong basis, his result, and thus the bit he reads, will be random.


In the second phase, Bob will notify Alice over any insecure channel what basis he used to measure each photon. Alice will report back to Bob whether he chose the correct basis for each photon. At this point Alice and Bob will discard the bits corresponding to the photons which Bob measured with a different basis. Provided no errors occurred or no one manipulated the photons, Bob and Alice should now both have an identical string of bits which is called a sifted key. The example below shows the bits Alice chose, the bases she encoded them in, the bases Bob used for measurement, and the resulting sifted key after Bob and Alice discarded their bits as just mentioned.



Before they are finished however, Alice and Bob agree upon a random subset of the bits to compare to ensure consistency. If the bits agree, they are discarded and the remaining bits form the shared secret key. In the absence of noise or any other measurement error, a disagreement in any of the bits compared would indicate the presence of an eavesdropper on the quantum channel. This is because if the eavesdropper, Eve, were attempting to determine the key, she would have no choice but to measure the photons sent by Alice before sending them on to Bob. This is true because the no cloning theorem assures that she cannot replicate a particle of unknown state. Since Eve will not know what bases Alice used to encoded the bit until after Alice and Bob discuss their measurements, Eve will be forced to guess. If she measures on the incorrect bases, the Heisenberg Uncertainty Principle ensures that the information encoded on the other bases is now lost. Thus when the photon reaches Bob, his measurement will now be random and he will read a bit incorrectly 50% of the time. Given that Eve will choose the measurement basis incorrectly on average 50% of the time, 25% of Bob’s measured bits will differ from Alice. If Eve has eavesdropped on all the bits then after n bit comparisons by Alice and Bob, they will reduce the probability that Eve will go undetected to ¾n. The chance that an eavesdropper learned the secret is thus negligible if a sufficiently long sequence of the bits are compared.



By going through this process, of sending a polarized photons with an encoded bit and then receiving it one by one. Then, comparing whether each polarization angle used to encode the bit and receive the bit was the same or not, Alice and Bob are able to construct a secret key. This can be used to encrypt messages and can then be sent through open or public channels without the worry that an eavesdropper has the secret key that could decrypt the transmissions.


So, why is this important?


Encryption is an essential part of data security. It not only shields confidential data from exposure to attacks but is also used to protect information stored in files and data transferred across telecommunications networks. More importantly however, Quantum Key Distribution is important as conventional key distribution methods have their limitations.

Encryption is a method by which we protect privacy. Privacy is power. What people don't know they can't ruin.

Conventional ciphers are based upon mathematical calculations that are simple to compute, but that require an infeasible amount of processing power to invert. For example, it is easy to calculate the product of two large prime numbers, but much harder to factor the product to derive the primes. This key distribution approach presents multiple challenges. Its security is threatened by weak random number generators, advances to CPU power, new attack strategies, and the emergence of quantum computers. Quantum computers will ultimately render much of today’s encryption unsafe. A particular concern is that data encrypted today can be intercepted and stored for decryption by quantum computers in the future. In 1977, a seminal article on public key cryptography in Scientific American estimated that it would take 40 quadrillion years to crack a message asymmetrically encrypted with the RSA-129 cipher. In actuality, it was cracked less than 20 years later, within six short months, by using a distributed network of computers. To stay ahead of the trend, ever increasingly larger asymmetric keys are required to securely distribute symmetric keys. All these factors, especially the continued progress in quantum information processing, make it necessary to rethink how to securely distribute cryptographic keys.


Quantum Key Distribution is not without its limitations, however its theoretical basis offers great potential to create a means of conducting successful encryption. QKD, you see, is unconditionally secure in the sense that no assumptions are made about Eve’s inability to compute hard mathematical problems but rather her inability to violate physics. Even with this security, however, the QKD protocols are still susceptible to a man-in-the-middle attack where Eve pretends to be Bob to Alice and simultaneously pretends to be Alice to Bob. Such an attack is impossible to prevent under any key distribution protocol without Alice and Bob authenticating each other first. Furthermore it is not immediately obvious whether QKD protocols are perfectly secure when used with imperfect equipment and in the presence of noise. What this means is, in real systems, if Alice and Bob discover their measurements are not perfectly correlated, it is difficult for them to determine whether the discrepancy was caused by using noisy imperfect equipment or whether there was an eavesdropper present creating perturbations in the state of the photons by measuring them. Nevertheless, with improvements in the protocols used to conduct quantum encryption, two parties, given access to an insecure quantum and classical channel, can securely establish a secret key without making any assumptions about the capabilities of an eavesdropper who might be present.


My takeaways from this trip:

  • I learnt about the nature of Quantum Key Distribution, how it works, what it’s benefits, limitations and future out of the lab look like.

  • I was able to apply the physics I’ve learnt in classes to a lab setting in order to tackle a problem. At the time I visited the IQC at the University of Waterloo, I was learning about atomic, nuclear and particle physics. I found that this lab greatly complemented my learning.

  • I gained a deeper appreciation of leading research in encryption using quantum physics. Though the establishment of BB84 as an idea is groundbreaking, I find that the development of the protocols after this initial one are true testaments to scientific rigour. This is because each subsequent protocol such as Eckert’s Protocol or Entangled BB84 Variants, amongst many others, each seek to improve upon the previous methods of encryption. Too often, those outside immediate research in a particular field will come in to praise the potential of emerging ideas and technology and then take a break until the hard work of actually developing and fine tuning those ideas and technology is complete.

Thanks for reading and be sure to check out my other work as well.



AstroTech


EcoBin


Patcher

GET IN TOUCH

I'd Love To Hear From You