Towards Quantum Computing (II): The Secure Quantum Channel
In this new chapter on the introductory series on Quantum Computing, we'll learn about its impact on Cryptography.
Missed the previous chapter of the series? I got you covered:
Hello, Hypers!
Let’s continue our series on Quantum Computing. In the previous chapter, we learned about the two main properties of particles that can be useful for computation: superposition and entanglement.
But we didn’t know why are these properties important in the context of Computer Science. In this post, I’ll show you a cool cryptographic application of quantum principles. Let’s get started!
Symmetric Cryptography
Remember when we learned how cryptography works? Don’t worry, check the post again:
We saw that the main problem with symmetric cryptography is that Alice and Bob need to agree on a key, but that agreement cannot be protected with cryptography because they would need to agree on a key first, and… Yep, a problem indeed.
As we discussed in that post about cryptography, there is no truly secure channel to confidently send the key. A bad actor can always intercept the message. But symmetric cryptography still has hope because Quantum Mechanics comes to the rescue!
The Qubit and the Photon
We also talked about what a qubit is. It is the quantum version of a bit, so it can be in a superposition of zero and one simultaneously. But, how can we create these qubits? Well… they are out there in nature. Remember, quantum behavior is the natural behavior of subatomic particles.
For example, a photon can be polarized in many directions. We’ll denote those directions as u (up), r (right), d (down), and l (left). The photon can be polarized in other directions like ne (northeast). But the northeast direction can be seen as a combination of the u and r directions:
Note: The use of these coefficients will be explained in a future post. Right now, we just need to know that a direction can be expressed as a combination of other two directions.
In the same way, the u direction can be expressed as a combination of ne (northeast) and nw (northwest) for example:
As a photon has a quantum behavior, it doesn’t have a specific polarization direction but its polarization is in a superposition of all the possible directions at the same time. Only when we measure the polarization, it collapses in a single direction.
We can also force a photon to collapse its polarization to a set of two possible options. For example, we can measure the polarization in a way that the result of the measurement is either u or r, or we can force the result to be either ne or nw. Thus, we can interpret one of the two possible results as a zero and the other one as a one.
We have converted our photon into a qubit! This qubit will be in a superposition of zero and one until we measure its value (measure the polarization of the photon and force it to have two possible values).
Note: We can force the result of the measurement to be in a set of two possible values by using polarization filters.
Note that we can measure the qubit in different ways by picking different sets of possible values. So, if we measure the polarization of a photon, forcing its value to be either u or r where u = 1 and r = 0, we can obtain a different value than when measuring the polarization of the same photon but using ne = 1 and nw = 0 as the possible values. This will be key to building our secure communication channel.
For example, if a photon polarization is u and we measure taking u and r as a reference, then we’ll obtain the value u when measuring that polarization, and we can interpret it as a one. What happens if we use ne and nw as a reference instead? Remember the previous equation:
When the polarization is u in the u and r system, it is in a superposition in the nw and ne system. If we measure with the nw-ne reference, we’ll have a 50% chance of getting nw and 50% of getting ne. It all depends on the measuring reference. Let’s see how to use this to build a secure channel to share our secret keys.
The Channel
Now we can understand how a secure channel can be implemented using Quantum Mechanics. The goal of this channel is that Alice can send a secret key to Bob securely. This secret key will be a sequence of zeros and ones that will allow Alice and Bob to encode and decode messages in a way that a bad actor Evil cannot understand.
The communication will be done through two channels: one classical bidirectional channel that allows Alice and Bob to send and receive bits (zeros and ones), and a quantum unidirectional channel that allows Alice to send qubits (photons in a superposition of polarization directions) to Bob. A bad actor Evil can intercept both channels.
First of all, Alice will generate a random sequence of bits. Then, she encodes the value of each bit in the polarization state of a photon by randomly choosing for each bit one of two possible sets of reference: Up-Right (u and r) or Northeast-Northwest (ne and nw). After that, she sends the photons to Bob through the quantum channel.
Bob measures the state of each photon also by randomly picking either of each reference set. This way, Bob obtains a sequence of bits with the same length as the one generated by Alice. Now the fun begins!
Over the classical channel, Alice and Bob check that Bob has received all the photons Alice sent. Then, they share which reference set they used for encoding and decoding each of the photons. In the cases where the sets are the same (both chosen u and r, or both chosen ne and nw for that bit), Bob’s measured bit value agrees with the bit value that Alice generated. The bits for which the sets are not the same are discarded.
Now Alice and Bob have the same sequence of bits! The last step is choosing some bits from the sequence and comparing them through the classical channel to be sure everything is ok.
They shared a secret key over a secure channel..! Right?
Playing the role of Evil
As we said before, Evil has access to both the classical and the quantum channel. Let’s see what this bad actor can do to get the secret key.
Note that the classical channel is only used to discuss the choice of the sets and not the bit values themselves. So, Evil cannot gain any information from this channel alone. To gain information, Evil must intercept the photons transmitted from Alice to Bob through the quantum channel.
Evil must intercept the photons and send another photon to Bob before knowing the choice of reference made by Alice and Bob because they compare the sets only after Bob has confirmed receipt of the photons.
If Evil sends different photons to Bob, Alice, and Bob will detect that something is wrong in the last step when comparing some of their bits. But sending the same photon without doing anything does not give any information.
Evil must measure before sending the photon to Bob. But Evil doesn’t know the reference Alice used. By choosing a set at random, the probability of measuring with the wrong set is 50%. This measurement will change the polarization of the photon (welcome to the quantum world). That means that later, when Bob measures the photon, even if he chooses the same reference as Alice, the probability of getting the same bit that Alice generated is just 50%.
Overall, for each of the qubits that are not discarded, if it was measured by Evil before Bob received it, there will be a 25% chance that Bob measures a different bit value than the one Alice generated. Thus, if Alice and Bob check a sufficiently large number of bits in the last step of the process, they can realize whether a bad actor is eavesdropping.
Now we can say it confidently: the secret key is indeed secret!
And that’s all for this week, I hope you have enjoyed this post. If you got lost at some point, re-read this and the previous chapter of the series on Quantum Computing as much as you need. If you want to make some questions or suggestions don’t hesitate to use the comment section or reply to this email. If you liked this post, let me know by hitting that heart button.
Thanks for reading and see you soon!