QuantDART
Published in

QuantDART

Quantum Computing Threatens Public Key Encryption: Do We Need to Worry?

Google announces quantum computing supremacy in October of 2019 but do we really need to start worrying about the public-private key encryption which is in widespread use today? And if so when? We got you covered with Quantum Key Distribution and BB84.

The Fall on Constantinople 1453. Army Museum, Istanbul, Turkey

A cacophony of yells and curses filled the air. It drowned out the slight gusting of the spring breeze. That wind wasn’t cool enough to hold the steady stream of sweat pouring down the men’s backs as they toiled, stripped to the waist. Dozens and dozens of them were crowded around an enormous bronze tube. It was 27 feet long, the opening at the end was large enough for one of the sweating men to crawl inside on his hands and knees. The tube was a cannon, a bombard to be precise, heaving on ropes, straining muscles and tearing tendons. One group of the men struggled to pull it into place for a shot.

Another team, lugged bags full of volatile gunpowder, very carefully ported it, hundreds of pounds worth. Still, another team hefted a thousand pounds stone cannonball to the opening, and slowly, slowly pushed it back down the barrel toward the gunpowder. Standing behind the great bombard was an aging man in a tall white cap. He sighted down the barrel, peering out at his target, the great ancient walls of Constantinople where big blocks of white stone threaded through with red brick.

Two walls, an outer and an inner, the inner studded with tall towers stared back at the master gunner. There he saw it. That was the spot, a place on the outer wall that had fallen and then been repaired at some point in the last thousand years. He called out orders to the sweating, cursing laborers. “A few inches this way. No, not so far. An inch back.” Two smaller Cannon flanked the big one and he yelled instructions on where he wanted them targeted to the sides and a bit down in a triangle pattern.

An assistant placed a reed taper into the rear of the great cannon and the master gunner lit it with a torch. Everyone took cover and jammed their hands over their heads. A massive roar filled the air as the gunpowder exploded and sent the stone ball hurtling toward the wall. A moment later, a resounding crash echoed back as the ball smacked into the ancient masonry. Two more loud explosions followed as the other cannon fire. Then two more crashes when their projectiles impact.

There was silence then a loud rumble. Blocks of shattered stone tumbled down from the wall, leaving a triangular breach where the three balls had hit. The walls of Constantinople had stood for a millennium in 1453. They had stood up to the Avars, the Persians, the Vikings and the Arabs.¹ It was accepted wisdom that the walls of Constantinople were invincible. Invasions came and invasions were repulsed. Few things were ever as dependable. But there is a greater constancy — change. Advancements in cannon technology, and an audacious battle plan by Mehmed the Conqueror struck the walls at its weakest point, ending the last chapter of the Roman Empire.

Likewise, RSA-2048 has long served as the bastion of public key cryptography, without which secured communication and digital commerce over the internet would be impractical. Likewise with new technology and tactics, RSA’s assurance in protecting the networks are threatened by quantum computing working in combination with Shor’s algorithm. Mind you that quantum computers already exists today. Both Google and IBM have 53-qubit quantum computers, however that is nowhere near the approximately 4,000 qubit units needed to crack RSA.

When will we achieve that level? Estimates range from as early as about 2025 CE (doubtful) to another 10–20 years out. While some say it’s only a matter of engineering, scaling up the qubit ladder is still challenging. My previous article, Answering the Chicken or the Egg, was an introduction to quantum mechanics and computing where I describe how qubits are the ultimate tech divas. It’s quite possible that practical quantum computing may never see fruition. Maybe it’s just that last sense of self-doubt ingrained in humanity just before previous monumental breakthroughs: the unleashing of the power of the atom, the breaking of the sound barrier, the giant leap for mankind, or the ending of the Red Sox curse.

Innovation does not progress linearly so it’s difficult to predict if or when a major technical breakthrough will occur. A simple serendipitous discovery in material science or subatomic particle, or photon orientation could be the vital enabler to qubit scalability and quantum supremacy. And just because I am paranoid [about encryption vulnerability] doesn’t mean that they aren’t out to get me. I will explain how we can use quantum cryptography to protect against quantum computing attacks.

BB84 Protocol

BB84 was created by Charles Bennett and Gilles Brassard in 1984 and is considered the first quantum cryptography protocol. Be it seconds, minutes, hours, or days, quantum computing in conjunction with Shor’s algorithm can crack RSA-2048 very efficiently. Interestingly quantum computing, does not threaten symmetric encryption. So once a symmetric key is generated and safely disseminated between two parties, confidentiality is reliably maintained using traditional channels even against the threat of quantum computing. In other words, quantum computing threatens only the public-private key generation that is the rationale behind RSA, which it achieves by factoring large prime numbers quickly. BB84, by using quantum computing, is therefore only concerned with the generation and dissemination of this symmetric key in what is known as quantum key distribution (QKD).

How does BB84 work?

BB84 has been lab proven although it’s not the only QKD or post-quantum cryptography. It is based on one simple, albeit strange (to me at least), quantum physics known as the no-cloning theorem. What it means is that a qubit cannot be cloned/copied. I am scratching my head searching for cliches but none exists. Like paper currency, you can spend it, you can put it in your wallet, you can borrow it, you can stuff it under your mattress. But you can’t copy it. Just keep that in mind and I will explain in detail as we go through the example using Alice (Initiator), Bob (counter-party to Alice), and Eve (eavesdropper).

Let’s start with the happy day scenario, no eavesdropping. The goal is for Alice and Bob to establish a secret key so that Alice can communicate confidentially with Bob using said key. Note that the BB84 protocol is only concerned with the QKD portion, the creation and safe distribution of the key. Alice initiates the process by creating qubits in the form of photons and sending them over to Bob. These qubits have two attributes: value (0 or 1) and basis (which I will call A and B for simplicity). Alice will generate them randomly, so that about half of them will be valued at 0’s and the other half 1’s. Likewise, the basis will also be about half A’s, and half B’s.

Alice records the order, value and basis of each qubit before sending it over to Bob. Each qubit value/basis combination will occur about 25% of the time equally: 0A, 0B, 1A, 1B.

Figure 1- Qubit values and basis using photons

Now this is where the quantum mechanics kick in. When Bob receives the qubit, he has no idea what their basis are. He has two qubit basis readers, an A and B reader respectively. And he takes a random guess at which reader to use for each incoming qubit. If he guesses correctly, he will be able to read the value, a 0 or 1, correctly. But if he guesses incorrectly, the incompatible reader will only give him the correct value about 50% the time. Bob will not know whether he guessed correctly or not. He simply records the basis that he used, and the value read out. A quick check shows that he will guess the basis correctly 50% of the time, which means those values will be guessed correctly 100% of the time. For the 50% of the times when he guesses incorrectly, he will still get 50% of the value correctly and 50% incorrectly. All in all, he will still get 75% of the values correctly.

Bob will then send back the ordered list of the basis he used to read the qubits. Alice cross references it against her list, before replying back to Bob which qubits can be used. Bob then discards the incorrectly guessed ones. The saved list can now be the candidate string for the symmetric key from which Alice and Bob can then use to encrypt the transmission. However, we must always assume an eavesdropper is present, so we next go thru the crucial process of reconciliation.

Now we still have to do the eavesdropper scenario. Eve sits in the middle of the secured channel chain listening in. She too has no idea what basis the qubits are sent. It’s a 50–50 proposition, so she guesses the basis, records the value (0 or 1), and forwards a qubit to Bob. Bob uses the same guessing process as before. Tidbit: his success rate of guessing correctly the values goes down to 62.5% from 75% with no eavesdropper (see derivation below).

Chart 1 — Bit concurrence drops to 62.5% in the presence of Eve

Why couldn’t Eve just leave things alone and just read the qubit and send it to Bob as is? She can’t. The qubits are adhering to the no-cloning theorem. And since she doesn’t know the basis, she can’t reliably recreate a copy of it. The best she can do is a 50–50 guess on the basis. Qubits can’t be cloned and it is the hidden unknowable basis, which affects the probability of correctly guessing.

Continuing with the reconciliation process, Bob sends his ordered list of basis to Alice. About 50% of the basis will agree while the ones in disagreement are discarded, irrespective of whether those values agree. Alice and Bob will then sacrifice a subset of the basis concurrences meaning they will openly expose the values behind this subset. They are trying to ascertain if anyone has been mucking around the qubits. If they do not have 100%* agreement, then they must assume that they have been eavesdropped. This is because Eve, never knowing the original basis from Alice, has to guess the basis either each time. If Alice sends an A qubit, and Eve guesses B, she will send a B qubit to Bob. Bob has no clue of the basis, and he guesses A, making a right out of two wrongs. This occurs 25% of the time when Bob’s basis will match Alice’s original intended basis (row 4 from chart 1 above). The basis match because Eve guessed wrong, but Bob then guessed wrong on the qubit Eve sent. Of these, 50% of the values will still match. But just one or more occurrence of this mismatch will confirm eavesdropping. Eve can never win and it will always be futile for her to try to compromise their confidentiality.

Conversely if Alice and Bob can confirm that all the sacrificed values are in synced, then can rest assure that their communique has been unfettered. They will then use the remaining, non-sacrificed values to establish a symmetric key.

Cleanup

BB84 is used only for the QKD portion of the communique. Once the symmetric key is established then messages are sent over a normal channel. BB84 has been successfully tested for up to 240 km.² In actual tests, the qubits are transmitted as photons — pulses of light. The basis of the photon are represented as to whether they are oriented in horizontally/vertically (basis A), or at a diagonal X angle (basis B). Furthermore a 0 is represented by a horizontal photon in the A basis or a negatively sloping diagonal for the B basis. Likewise a vertically oriented photon is a 1 in the A basis along with a positively sloped photon in the B basis (see figure 1). You have a 50/50 chance of using the correct filter orientation. Use the right filter, and you will get the correct value 100% of the time. Use the wrong filter, and you will get the correct value only 50% of the time. Here is where quantum comes in — you have no way of knowing if you chose the correct filter (basis) or not, and you can’t reuse the qubit, clone it, or pass it along after you have read it. This is where you in effect break the seal.

BB84 does not provide for authenticity between the two parties and would therefore still be susceptible to man-in-the-middle attacks. For an example, Eve can masquerade as Bob when reconciling with Alice while at the same time masquerading as Alice when communicating with Bob. An authentication scheme would be needed as a complementary stack to the BB84.

Finally for those who are interested in why the bit value concurrence goes down from 75% to 62.5% when a eavesdropper is present can follow the chart below. I have already explained above how bit value concurrence comes out to 75% between Alice and Bob when there are no eavesdroppers present. If you recall Eve will randomly guess the basis from Alice and get it correctly 50% of the time. Whatever her guess is regardless if she is right or wrong, she will send that over to Bob the same way she guessed it. Bob also has no inkling of the basis, so he must layer his basis guess on top of Eve’s. Now if you take a cross product of Eve guessing correctly against Bob guessing correctly relative to Eve, we have four outcomes for which we can sum up the probabilities since they are distinct (see chart 1). Since each of the outcomes have an equal probability of 0.25, we can multiply the 3rd column and summate as

0.675 = (0.25 * 1) + (0.25 * 0.5) + (0.25 * 0.5) + (0.25 * 0.5).

While you may be tempted to use this difference as an eavesdropping indicator, you can’t because you would have then exposed your sifted key candidate.

Conclusion

Like the Ottoman siege and against the last of the Byzantine Empire, attackers always aim at their enemies’ vulnerabilities. Changes are ever present and they either adapt or give way. It’s a constant battle and no one gives way. Attackers use quantum mechanics, defenders use quantum mechanics, and the next weakest link is focused upon. In fact there has been an interesting problem which until recently has no known solution. The problem is called, ironically, the Byzantine Generals Problem which is based on the challenge of coming to a consensus. And the solution is — the blockchain.

References

1. The Fall of Constantinople and the Tragic End of the Byzantines

2. Long-distance quantum key distribution secure against coherent attacks

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store