07 Sep Quantum Computing & Cryptography: moving from binary to superposition
I’d like to thank Bruno Fedrici PhD in Physics and Quantum Technologies Advisor for the resources and advice on the subject. We had the opportunity to meet through the Microsoft AI class led by the programming school Simplon in Lyon.
Since one of my priorities is helping the general public understand new technologies, I’ve been wanting to give Quantum Computing a try. I have to say that it is indeed a fascinating subject but when I saw the potential regarding cryptography, I couldn’t avoid thinking when quantum cryptography will make current encryption standards obsolete and how are we going to actually face it?
Quantum Mechanics Basics
First of all, is important to understand 3 quantum properties: Indeterminacy, Superposition and Entanglement.
Indeterminacy is the fundamental limit to the precision that certain pairs of physical properties of a quantum state can be known, like its position and momentum (speed). This means that the more precise the position, the less precisely its momentum can be known and vice versa. A consequence of indeterminacy is the No-Cloning Theorem which states that it is impossible to create an identical copy of an arbitrary unknown quantum state (which is an important element of quantum cryptography).
The second one is superposition, which refers to the quantum properties such as particles’ “position” that can take multiple values at the same time as illustrated by Schrödinger’s cat example. This means that the cat is in a state 50% alive and 50% dead before opening the box. When we open the box this is considered as observation/measurement making the system “the cat” falling to one specific component of the superposition: dead or alive.
In classical computation we store information using binary values 0 and 1 before to process it thanks to a set of logic gates. Quantum computation uses quantum logic gates acting on two level systems in superposition (Qbits for quantum bits). This means it relies on the ability of manipulating both values 1 and 0 simultaneously, also called “quantum parallelism”.
The third one is entanglement, which is just something spooky … Einstein literally referred to it as “Spooky action at a distance” which I find hilarious… Entanglement is when two quantum objects or more behave like a single system so measuring one subsystem affects the other, the idea is that the whole is more than a simple addition of the parts. It will be like if we run the Schrödinger cats’ experiment with two cats. If their state was entangled one will for instance always be dead when the other is alive even if they were physically separated in opposites sides of the universe!
As you know, a lot of our current online security depends on the effectiveness of public key cryptography. With quantum computers existing encryption standards will be obsolete at some point yes, but not in the near future. According to the state of the art quantum algorithms we need around 4000 Qubits to break existing public key encryption standards like the 2048-Bit RSA which is a lot compared to the 50 – 60 Qbits needed to have a quantum advantage or the 150-300 Qubits needed for calculations in quantum chemistry (like molecular simulations). Which explains why pharma and medicine will be one of the primaries business applications for this technology like Blockchain was for finance. Keeping this in mind it is suggested that businesses could be preparing for security threats from quantum computers in at least a decade. Even if is not in the near future, this shouldn’t prevent us for starting to prepare right away, sensitive data can be stored today and decrypted later when the technology will allow it.
On the same subject, an article submitted on 28 Oct 2017 by Cornell’s University researchers stated that “ the elliptic curve signature scheme used by Bitcoin is much more at risk, and could be completely broken by a quantum computer as early as 2027, by the most optimistic estimates “.
Most recently on May 13th 2019, an article from the Boston Consulting Group website said that “In 10 to 20 years, quantum computers are expected to achieve superior performance in tasks of genuine industrial significance”.
As we can see this technology is in an early stage and is still quite expensive, sensitive and the error rate is high. The most advanced superconducting Qbits are between 50-100 Qbits and they are still fragile which results in errors in the form of “noise”. That is why we are currently in what is called the NSQI era (Noisy Intermediate-Scale Quantum).
QKD Quantum Key Distribution
If quantum physics is a threat to cybersecurity, it can also be used to protect us. QKD offers a different approach where information encoded on single photons can allow us to agree on a shared secret key that will allow us to encrypt and decrypt messages (I assume Kerckhoff would love this since he was all about protecting the private key). This new approach is very interesting since we switch from using mathematical algorithms to using the laws of physics to guarantee security.
What I find amazing is QKD being possible thanks to quantum properties. Especially indeterminacy since it is central to quantum cryptography. Indeterminacy or No-Cloning means that since it is impossible to create a perfect copy of quantum particles, as an eavesdropper I would be forced to measure the original particle and altering it which ends up revealing my presence. On the other hand, if quantum states are entangled, they behave like a single system. That means I can’t intercept the key without disturbing states entangled properties and thus revealing my presence. More precisely, the idea of QKD protocols based on entanglement is that if a spy makes a measurement to acquire information, it will destroy this entanglement (measuring is a projective operation) and the results of the two communicating parties will no longer be systematically correlated.
This makes undetected eavesdropping impossible which is a crucial difference with public key standards where the potential presence of an eavesdropper remains unknown all along a particular protocol.
At first, I thought about this as being very theoretical but, in 2017 the Chinese satellite MICIUS did some trials on sending entangled photons between the Delingha station and the Lijiand station which are 1200km apart. I strongly believe that it is a good idea to keep an eye on the Quantum race and its disruptive potential (keeping in mind that error correction is one of the biggest challenges scientists will face in the coming years). I assume we will be hearing a lot from the public sector after billions euros/dollars recently invested through national initiatives in the US, EU and China, as well as from the private sectors with tech giants such as IBM, Google, Alibaba, or Atos, and spin off such as the American companies Rigetti, Zapata, IonQ and the Canadian 1QBIT to quote only a few of them.