Quantum Cryptography
- rachaelperkins357
- Sep 17, 2020
- 8 min read
Updated: May 22, 2021
Foreword
This blog post is based off an essay I completed for my Quantum and Particle Physics Module. I decided to re-edit it and turn it into a blog post because I found this topic really interesting. References are included at the bottom and denoted by [] brackets. Thanks for reading!
Originally posted 17/10/2020, updated on 22/05/2021
An Introduction to Cryptography
Cryptography is the science of transmitting or sharing information between two or more legitimate parties such that outside parties won't be able to correctly interpret the information being exchanged. A famous example of cryptography in action was the Enigma Machine. Created by German engineer Arthur Scherbius, it had 158,962,555,217,826,360,000 different settings! That's 158 Quintillion different settings or a million times bigger than a trillion! To make it harder to crack, it's setting was changed every day. Lets picture a lock and key game. Imagine trying to open a locked door and you were given 158 Quintillion possible keys where only one would work. It would take a long time to find the correct key by trial and error, definitely longer than a day. Now imagine that every day, the lock was changed, so all the work you did the previous day is useless. Now you have to start all over again. That's what trying to solve enigma was like! You can see why the Germans were confident that their cypher would be unbreakable. During WWII, using Enigma helped the Germans to keep their messages unintelligible to enemy forces, even when their messages were intercepted. Every time a German message was intercepted, enemy forces would have to play the lock and key game from above. This meant that German strategies and plans would remain a secret, giving the Germans an advantage over their enemies. The Enigma Machine was eventually solved in 1940 by Alan Turing and his team at Bletchley Park [1], a turning point in the war which potentially helped shorten WWII. Side note: if you haven't watched the 'Imitation Game', it's a really good film based on Alan Turing and his teams' work on breaking the Enigma Machine code. A great film I've watched and really recommend!
Cryptography has evolved greatly since the Enigma machine, especially with the introduction of computers and the internet. The basics of any cryptography method includes using some sort of method to encrypt or jumble up information, sending the jumbled information to another person/computer/user in some way, then decrypting or unjumbling the information once received.
An important part of Cryptography, is the use of a 'key'. The key might not be a physical object like in the lock and key game above, instead, the key might be a number, though not always. The key is top secret information that is required to encrypt/decrypt information and should only be known to the legitimate parties. In the case of the Enigma Machine, the key would be knowing the exact setting used that day. In computational methods, the key might be knowing which mathematical function was used to encrypt so you'd be able to apply the correct inverse function for decryption. If an outside party comes to know your key, they now have the ability to decrypt any messages you send, therefore it is of high importance that a key remains a secret to anyone but the legitimate parties. The key must be prearranged between the legitimate parties, which can be done in various ways. Some of which include:
Meeting face to face to swap the Private Key
This is often impractical if users live in different locations, however it reduces the risk from online eavesdroppers. You'd still have to worry about people around you eavesdropping however, this is still a lesser risk than those online.
Use Public Channels
This is a more practical method logistically, hence is a favoured method however it's more susceptible to online eavesdroppers.
Public Key Distribution (RSA Protocol)
Imagine we have a scenario with 2 users known as User A and User B. They want to be able to send encrypted information to each since they can't meet in person due to living in a different locations. Therefore, they have to use a public channel such as an email service or over the internet. So how do they do this in such a way that their data is protected from online eavesdroppers?
User A comes up with a method where they multiply two large prime numbers together, These two large prime numbers are known as the private key. Their product creates an even larger number, known as the public key. The public key (the big number) can be used by User B to send User A encrypted data along a public channel. Once User A receives the information, they use their private key to decrypt it [2]. In this scenario, anyone can use the public key to encrypt and send information to User A, but since only User A knows which two large prime numbers make up the private key, only User A can decrypt the information. See Figure 1 below.
Figure 1 depicts the RSA protocol.
This method is known as the RSA protocol and will only remain secure as long as the public key remains unfactorized. This explains the reason why User A used large prime numbers to create the public key. Prime numbers can only be factorised by 1 and themselves. Multiplying two prime numbers together creates a semiprime number. A semiprime number can only be factorised into 1, itself and the two prime numbers that were multiplied together to make it. This makes factorising a semiprime number hard. The larger the semiprime number, the harder it is to factorise, but not impossible. Due to the development of factoring algorithms and the arrival of quantum computers, factorising semiprime public keys is becoming more efficient [3]. This poses a problem for User A in our scenario. If their public key is successfully factorised, it would allow outside parties the ability to decrypt any information sent to User A via the public key. User A's private key is compromised and communication using these keys would have to stop. In comes Quantum mechanics to help with this issue. Quantum Mechanics can offer us a way to make using public channels even more secure.
A Little Quantum Background
Using quantum properties such as Heisenberg's Uncertainty Principle and Quantum Entanglement, we can theoretically send a quantum key over public channels without the key being intercepted/copied, thus making the transmission of a secure private key possible.
Heisenberg tells us that we cannot simultaneously know the values of two paired properties of a particle. This is commonly shown through the complementary pairing of position, x and momentum, p as seen below in Equation 1. It can more commonly be explained as: the more accurately you know a particle's position (x), the less you'd know about its momentum (p) due to these properties being complementary paired.
Equation 1:
The Heisenberg Uncertainty Principle
relating to position, x and momentum, p.
When it comes to the polarisation of photons, we see there is a complementary pairing between rectilinear polarisation (vertically or horizontally polarised) and diagonal polarisation. Each photon will 'decide' what its polarisation will be with regards to its base, rectilinear or diagonal. If a photon is rectilinear, it has a 50:50 chance of being vertically polarised or vertically polarised. If the photon is diagonal, it has an equal chance of being in any diagonal state. Each base is made up of a superposition of all possible options. This means that each base contains all the possible options one on top of another. Remember above I mentioned that the rectilinear and vertical polarisations are complimentary pairs? We can apply Heisenberg's Uncertainty Principle. This means that once we measure/define one base, we lose all information about the other.
Figure 2: Depicts an experiment that measures
the polarisation of randomly polarised photons.
In figure 2, we see what happens to photons when they pass through different polarisers. We begin with randomly polarised photons. The first polariser is rectilinear, specifically vertically polarised, therefore, we have defined the polarisation of the the rectilinear base. We do not know the polarisation of the diagonal base. As the photons travel through the second polariser (a diagonal one), we have now defined the diagonal base but have lost all information about the rectilinear base. As the photons travel through the final polariser, the rectilinear base has been defined as horizontal but we can no longer be sure about the diagonal base. Through this experiment, we see the Heisenberg Uncertainty Principle in action.
That's all fine and dandy, but you might be wondering how this relates to cryptography...
Quantum Key Distribution (QKD)
Knowing the above, User A can generate a random string of bits and assign a random polarisation base to each bit. A bit is a binary number, 1 or 0. Binary is the 'language` that computers operate with behind the scenes. User A then sends this photon sequence across a public channel to User B, who measures these photons using a random polariser for each photon. Over the same channel, both users decide on a random subset of their bits. User A then reveals the bases assigned to each photon in the original string. User B compares their randomly selected subset of bits to their original bases. If the polariser used to measure the bits and original photon base were the same base, then User B should have the same result as User A. Otherwise the result is random and disregarded. This leaves both users with the same sequence of bits, which becomes their private key. This method is known as the BB84 quantum key distribution protocol. It was named after the surname initials of the scientists who created it, Bennett and Brassard, and the year in which they did so, 1984.
Figure 3: BB84 Protocol - named after
Charles Bennett and Gilles Brassard after they put forward the
protocol in their 1984 paper [4]. In this image, the rectilinear base was assigned as 1 and the diagonal base was assigned 0.
This protocol not only allows the parties involved to make a secure private key over public channels (without having to meet in person) but it also has an in built eavesdropper detection system. If a middle man, User C, were to measure the photons before User B, they would have disturbed the system as User C would also be using random polarisers to measure each photon. If User A and User B used the same transmission base and polariser to transmit and measure a photon, yet the base outcome is a different base, there must have been a disruption to the system. User B has successfully detected an eavesdropper. In this case, communication on that channel would cease [5]. There is a possibility that the eavesdropper could have guessed the correct bases for the photons. The chance of this gets smaller the more photons there are in the sequence P = 1/2 ^ (photon number).
In conclusion, cryptography can get quite complicated and no method is without it's issues, but using modern techniques and applying quantum mechanics principals can make encryption method more secure and a little bit harder to hack [6].
References
[2] Nigel P Smart. Cryptography Made Simple. Springer, 2016.
[3] Arjen K. Lenstra and Mark S. Manasse. Factoring with two large primes. In Ivan Bjerre Damgard, editor, Advances in Cryptology | EUROCRYPT '90, pages 72{82, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg.
[4] Charles Bennett and Gilles Brassard. Withdrawn: Quantum cryptography: Public key distribution and coin tossing. volume 560, pages 175-179, 01 1984.
[5] Charles H. Bennett, Francois Bessette, Gilles Brassard, Louis Salvail, and John Smolin. Experimental quantum cryptography. Journal of Cryptology, 5(1):3-28, Jan 1992.
[6] Shor and Preskill. Simple proof of security of the bb84 quantum key distribution protocol. Physical review letters, 85 2:44, 1-4, 2000.
Aweseom 😎, really interesting article.