@adlrocha - Modelling a quantum symmetric key exchange

In Qiskit

It’s been a crazy week. Throughout the week I’ve come up with a ton of ideas for the newsletter but I’ve ended up having no time to develop nor write about any of them. From my attendance to one of the highest quality summits I’ve ever been to, the Randomness Summit (which by the way, from what I’ve heard it was organized in record time); to the new laptop I’ve bought in order to be able to work properly; or the awful experience I am having starting a company in Spain. A lot of potential topics but a clear lack of time. 

So here I am, already Sunday and without anything to share with my beloved audience. Instead of rushing into writing a low-quality piece for today about any of the aforementioned topics, I chose to search through my archive for something not yet shared in this newsletter, and I came across this cool article from last year. I wrote that piece after attending Qiskit’s first hackathon in Europe. Before this hackathon I knew almost nothing about quantum computing (to be completely fair I read a few books about the topic, but I don’t have a PhD in Physics in case you are wondering). Apart from this I knew a bit about cryptography and computer science, and that’s it.

Modelling the problem…

First things first, for the profane in the matter, what is Qiskit? Qiskit is an open-source quantum computing framework. In short, with Qiskit we are able to build, test and simulate quantum computing circuits and algorithms easily in our local machines. To add some excitement to the library, Qiskit also lets you run your quantum circuits and algorithms in one of IBM’s quantum computers (you can run your programs in a 5 qubits or a 16 qubits quantum computer -at the time of writing-. More than enough to have a glimpse of how quantum behaves in real life. Small piece of advice? Beware of the noise :) ).

The aim of the hackathon was to build a project using Qiskit. Due to my background (and deep love) in cryptography, I decided that for the hackathon I wanted to build some kind of cryptographic system using quantum computing. I thought about open problems in cryptography, and I realized it would be really cool to try and optimize classical symmetric key exchange algorithms, such as Diffie-Hellman, using quantum computing. I wanted to remove the need for several interactions between parties, and a key generation based on prime numbers (you know, due to Shor’s algorithm and stuff).

We started our project with the following system model in mind: Alice and Bob (of course) want to exchange encrypted data using a classical channel and classical encryption algorithms, but they want to generate and share the symmetric key used for encryption using a quantum (and secure) channel independent from their data channel. For this, Alice and Bob use a quantum random number generator and a set of entangled bits for the generation and exchange of the key.

…and growing it

With the problem to be tackled, and the programming framework ready, building this in Qiskit was pretty straightforward (one qubit for each party, a Hamadard gate in one of them, and a CNOT between the two would do the job). That’s when we thought it’d be cool to include a new party in our system model, Eve, a malicious agent looking to disturb, eavesdrop or sabotage our quantum link, and consequently our key exchange protocol.

We modeled the effect of Eve using a set of rotation matrices. Having an external observer in our quantum link would increase the noise in our channel. What we wanted to simulate was the effect of an observation or disturbance from Eve previous to B’s measurement. Bearing in mind these assumptions, modelling our man-in-the-middle through a set of rotation matrices applied to the specific qubits manipulated by him made a lot of sense. Even more, through the angle of the rotation matrices we could simulate the strength of Eve’s disturbance over the channel.

Modelling this scenario using Qiskit was quite an interesting and challenging work, but still not enough for a 24h hackathon. We thought then of using a parity qubit as a tool to detect potential noise or malicious effects over our key distribution channel. Both our qubits for A and B are entangled, so when measuring them both must collapse to the same value. If this is not the case, it means that something has happened in the channel. Consequently, we developed a quantum circuit with a parity qubit that was set to 1 if both qubits had the same value, and 0 otherwise. We transmitted this parity qubit with each independent qubit of the key so that the receiver could detect if something had disturbed the key exchange.

The key is generated and shared one qubit at a time, and with each bit an additional parity qubit is sent. The algorithm was implemented so that if sender and receiver measure a zero in the parity qubit, that bit of the key was discarded, as most probably something happened during the exchange.

We also implemented what we called a “security threshold” in our algorithm, which meant that sender and receiver could agree in advance on a maximum number of disturbance accepted in the quantum channel, so that if a number of bits larger than the security threshold were discarded in the key distribution, the key would be marked as invalid, and a new key generation would be triggered. This security threshold could be set to a baseline level according to the noise of our quantum device, as part of the disturbance in the channel may not be accounted for by a man-in-the-middle, but due to the noise of the device.

And with our keys generated and shared through our quantum channel, we could seamlessly use our classical algorithms to encrypt and decrypt our data (as shown in the sample execution depicted above). Check our project’s github repo in case you want to give a try to our algorithm (disclaimer: I haven’t looked at this code for more than a year, so it may be significantly outdated. Post an issue if you want me to have a look at it).

This quantum key distribution was only the first stage of our project. Actually, this stage was only an excuse to learn Qiskit and play with quantum computing with concepts well understood so we could move to more interesting matters. 

As part of the hackathon we also attempted to model and design our very own blockchain quantum consensus. This is something I haven’t shared anywhere since we flirted with the idea in the hackathon, so it may be worth talking about it other day.