In this notebook we are going to introduce the theory of Quantum Cryptography and one of its possible applications.
If you are new to this topic, I suggest you to read the Introduction notebook, where you can find basic required notions of cryptography and quantum computers. If you feel confident about your background, or you just want to take a peek, you can follow up.
This notebook consists in a possible implementation of the BB84 cryptographic protocol on a quantum computer, reproducing Quantum Key Distribution and eavesdropper detection. It makes use of IBM's QISKit, a python library that can manipulate quantum circuits, either via a simulation or a real execution on IBM's backend.
In 1984, building on the work of Wiesner, Charles Bennett, an IBM's researcher, and Gilles Brassard, of the Université de Montréal, developed the first quantum cryptographic protocol, which goes under the codename of BB84.
Suppose that Alice and Bob are connected via a quantum channel that they can use to exchange qubits. This channel is not used directly to send a private message, but only to exchange random qubits that after processing will compose the encryption key.
If key sharing is completed successfully, this key can be used in the well known way as a one-time pad (OTP) to produce a safely encrypted message to be delivered over a classical channel using symmetrical cryptography. The key should be completely random, as long as the message, and discarded after use; the procedure can be repeated for every message that needs to be delivered.
More specifically Alice produces an initial key, selecting a sequence of random bits, '$0$' and '$1$', and picking a sequence of polarization eigenstates, with respect to a randomly chosen basis between: rectilinear $\{\lvert 0 \rangle,\ \lvert 1 \rangle\}$ and diagonal $\{\lvert \nearrow \rangle,\ \lvert \searrow \rangle\}$.
Alice encodes the classical bits of the key one by one in a qubit, by preparing each qubit in an eigenstate of the basis chosen, so that only by measuring the qubits in the right basis one can retrieve with certainty the right classical bit, just as it happens with quantum money. In the meantime Alice keeps a note (in a table) of the basis that she has picked for every single qubit she has encoded.
Now, using the quantum channel, she sends the stream of qubits to Bob, who is unaware of the basis used by Alice for the encoding. Bob receives these qubits prepared in a certain polarization eigenstate but, due to the no-cloning theorem, he is unable to recognize which basis Alice used, because he cannot distinguish non-orthogonal states with a single measurement. Nonetheless he proceeds anyway with measuring each photon's polarization using a basis chosen randomly (between rectilinear and diagonal), and he keeps a note of the measurement result and the associated basis that he used in a report table.
Statistically, Bob will pick the right basis, the same that Alice picked, about $1/2$ of the times, and the wrong basis about $1/2$ of the times. When he measures using the right basis he correctly retrieves the information bit of the key, but when he picks the wrong basis the information bit is not certain, since with respect to this basis, the qubit is in a superposition of the eigenstates of the right bases, and it can collapse in either two of them with equal probability of $1/2.$
For this reason Alice and Bob decide to sift their key, which in practical terms means that they discard from the key all the bits obtained via measurements made in the wrong basis, since they are not reliable. The price for this action is that the key will lose about $1/2$ of its length, but the payoff is that they don't need to unveil their measurements, they just need to compare their tables, where they recorded the basis chosen, and they do that after the measurement has occurred.
So they open the classical channel and only now Alice tells (publicly) Bob which basis she used to encode the key; they compare the tables and discard the bits obtained measuring qubits in different basis. What they obtain is a perfectly correlate sifted key, the same for both of them, ready for use. This key can be employed as a one-time pad and once is used up completely, the procedure can be repeated again to produce a new random key.
What happens if we now introduce an eavesdropper in the communication? Suppose that Eve is able to intercept the qubits that Alice sends to Bob, and that she can also tap the classical communication channel. When she gets hold of the qubits she still doesn't know which basis Alice used, just like Bob. She is forced to make a guess, and she will pick the wrong basis $1/2$ of the times. If she measures in the wrong basis she has $1/2$ probability to make the qubit collapse in the wrong eigenstate, so that on the whole she will have altered about $1/4$ of the original qubits. This is the main difference with classical crypto: thanks to quantum mechanics observing implies measuring, and if this is not done accordingly, it changes the actual state (key).
Eve produces a candidate key and passes on these (now altered) qubits to Bob who proceeds himself with his measurements. Bob constructs his table list of random basis and also obtains his candidate key, which will of course be different from Eve's. When Alice broadcasts his basis table on the classical channel and Bob sift his key accordingly, he will obtain a key different from Alice's, unusable, since even in the same basis choice qubits will be different about $1/4$ of the times. If Alice try to encrypt a message, symmetrical cryptography would fail and both Alice and Bob will know that communication has been compromised.
If Alice and Bob never compare their measurement and they only compare basis tables they have no way of knowing that the state has been altered, until the encrypted message is produced, sent and decryption fails. However they can decide to initiate key sharing by also comparing their measurement on a certain number of qubits, and, only when they are convinced that the channel is free of interference, they proceed with the actual key sharing. Of course the part of the key that represents the unveiled measurement has to be discarded from it. In real world application is comprises about $1/3$ of the whole key.
In this notebook I will be demonstrating exactly this behavior, how initial key sharing can be used to detect an eavesdropper.
Quantum Key Distribution requires special apparatus made for key sharing. Having at our disposal IBM's quantum computer, here we present a proof-of-concept of how the process can be realized, using real quantum measuring devices.
The key sharing part will be simulated using different quantum circuits one for each party (Alice, Bob, Eve) in the exchange, since we don't have a real quantum channel. We present first the simple case in which only Alice and Bob are present, and we later proceed to introduce Eve and demonstrate how she can be caught.
First we check for and import the required libraries:
In [1]:
# Import numpy for random number generation
import numpy as np
# importing Qiskit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute, Aer
# Import basic plotting tools
from qiskit.tools.visualization import plot_histogram
Next we do some preliminary settings to better manipulate quantum circuits and we set the number of available (qu)bits to 16
In [2]:
# Creating registers with n qubits
n = 16 # for a local backend n can go as up as 23, after that it raises a Memory Error
qr = QuantumRegister(n, name='qr')
cr = ClassicalRegister(n, name='cr')
We create Alice's quantum circuit, made of $n$ qubits (and $n$ bits in a classical register, for measuring). We use $randint$ from numpy to generate a random number in the available range which will be our key and then we write the resulted number in binary and we memorize the key in a proper variable
In [3]:
# Quantum circuit for alice state
alice = QuantumCircuit(qr, cr, name='Alice')
# Generate a random number in the range of available qubits [0,65536))
alice_key = np.random.randint(0, high=2**n)
# Cast key to binary for encoding
# range: key[0]-key[15] with key[15] least significant figure
alice_key = np.binary_repr(alice_key, n) # n is the width
Parse the generated key and we encode it in Alice's circuit, initializing her qubits to the computational basis: $\{\lvert 0 \rangle,\ \lvert 1 \rangle\}$, according to the value bit. Then we apply a rotation to about half of these qubits, so that about $1/2$ of them will now be in one of the eigenstates of the diagonal basis: $\{\lvert \nearrow \rangle,\ \lvert \searrow \rangle\}$. We record the basis choice in a list (table) that will later be used for key verification.
In [4]:
# Encode key as alice qubits
# IBM's qubits are all set to |0> initially
for index, digit in enumerate(alice_key):
if digit == '1':
alice.x(qr[index]) # if key has a '1', change state to |1>
# Switch randomly about half qubits to diagonal basis
alice_table = [] # Create empty basis table
for index in range(len(qr)): # BUG: enumerate(q) raises an out of range error
if 0.5 < np.random.random(): # With 50% chance...
alice.h(qr[index]) # ...change to diagonal basis
alice_table.append('X') # character for diagonal basis
else:
alice_table.append('Z') # character for computational basis
How can we send this state to Bob? As said, we don't have another quantum computer, but we can create another quantum circuit, which we call $bob$, and initialize Bob's initial state to Alice's output state. To accomplish this task we define a helper function, SendState, that retrieves the qasm code of a given quantum circuit, $qc1$, does some filtering to extract the quantum gates applied, and produces new instructions that uses to initialize another circuit, $qc2$. This trick works because QISKit maintains a python dictionary of quantum circuits with their relative qasm instructions.
In [5]:
# get_qasm method needs the str label
# alternatively we can use circuits[0] but since dicts are not ordered
# it is not a good idea to put them in a func
# circuits = list(qp.get_circuit_names())
def SendState(qc1, qc2, qc1_name):
''' This function takes the output of a circuit qc1 (made up only of x and
h gates and initializes another circuit qc2 with the same state
'''
# Quantum state is retrieved from qasm code of qc1
qs = qc1.qasm().split(sep=';')[4:-1]
# Process the code to get the instructions
for index, instruction in enumerate(qs):
qs[index] = instruction.lstrip()
# Parse the instructions and apply to new circuit
for instruction in qs:
if instruction[0] == 'x':
old_qr = int(instruction[5:-1])
qc2.x(qr[old_qr])
elif instruction[0] == 'h':
old_qr = int(instruction[5:-1])
qc2.h(qr[old_qr])
elif instruction[0] == 'm': # exclude measuring:
pass
else:
raise Exception('Unable to parse instruction')
Now we can create Bob's circuit and "send" Alice's qubits to Bob. We pretend that this state is unknown to Bob so that he doesn't know which basis to use and decides randomly that $1/2$ of the qubits are to be measured in the rectilinear basis and the other $1/2$ in the diagonal basis; we then record Bob's choice in his table list variable
In [6]:
bob = QuantumCircuit(qr, cr, name='Bob')
SendState(alice, bob, 'Alice')
# Bob doesn't know which basis to use
bob_table = []
for index in range(len(qr)):
if 0.5 < np.random.random(): # With 50% chance...
bob.h(qr[index]) # ...change to diagonal basis
bob_table.append('X')
else:
bob_table.append('Z')
Bob can now go ahead and measure all his qubits and store the measurement in the classical register. We build and run the circuit on the local backend, but, if a token is provided and enough credits are available, it can also be executed on the remote backend with 16 qubits, ibmqx5. Note that is very important that $shots=1$, since we have to pretend that Bob has only one measurement chance, otherwise he could statistically infer the basis used (you can try).
In [7]:
# Measure all qubits
for index in range(len(qr)):
bob.measure(qr[index], cr[index])
# Execute the quantum circuit
backend = Aer.get_backend('qasm_simulator')
result = execute(bob, backend=backend, shots=1).result()
plot_histogram(result.get_counts(bob))
# Result of the measure is Bob's key candidate
bob_key = list(result.get_counts(bob))[0]
bob_key = bob_key[::-1] # key is reversed so that first qubit is the first element of the list
The histogram is not highly informative of course, but we can see that the measure has been performed correctly. Alice and Bob can switch over to the classical channel, compare their basis table lists, and discard qubits measured using different basis.
In [8]:
keep = []
discard = []
for qubit, basis in enumerate(zip(alice_table, bob_table)):
if basis[0] == basis[1]:
print("Same choice for qubit: {}, basis: {}" .format(qubit, basis[0]))
keep.append(qubit)
else:
print("Different choice for qubit: {}, Alice has {}, Bob has {}" .format(qubit, basis[0], basis[1]))
discard.append(qubit)
We know that Bob will pick the wrong basis for $1/2$ of the qubits, so we can check that this theoretical probability is indeed replicated. We also know that although Bob picks the wrong basis, he can still end up with right eigenstate, and that he will do so about $1/2$ of the times, getting right $3/4$ of the qubits. We can check when Alice's and Bob's measurements coincide due to pure chance, although noting that this step is never performed in the actual key sharing step, but only in the inital sharing to test for eavesdropper.
In [9]:
acc = 0
for bit in zip(alice_key, bob_key):
if bit[0] == bit[1]:
acc += 1
print('Percentage of qubits to be discarded according to table comparison: ', len(keep)/n)
print('Measurement convergence by additional chance: ', acc/n)
Now before sifting the keys we perform a check on a certain number of the qubits, comparing their value to see if they have been altered. Since we have only 16 qubits, which is a really low number, we check all of them. Although the procedure is limited to exchange 16 qubits at a time it can be repeated as many times as needed.
In [10]:
new_alice_key = [alice_key[qubit] for qubit in keep]
new_bob_key = [bob_key[qubit] for qubit in keep]
acc = 0
for bit in zip(new_alice_key, new_bob_key):
if bit[0] == bit[1]:
acc += 1
print('Percentage of similarity between the keys: ', acc/len(new_alice_key))
If the qubits measured are the same can accept the new sifted keys. The new sifted keys are printed to stdout, of course this step is just to verify the rightness of the protocol, when the procedure is repeated, each party is not supposed to know the other's sifted key.
Note that, in the real world, quantum channel are subject to information loss since detectors are not perfectly efficient and some photons are going to be lost along the way. Thus, the similarity between the keys will hardly be $1.0$, but surely not as low as $0.75$ which we know is the case in which it has been eavesdropped. As a percentage cut-off we can pick $0.9$ and perform a check before calling the exchange successfull or invalid. You can try to insert a parameter that represents this loss as exercise.
In [11]:
if (acc//len(new_alice_key) == 1):
print("Key exchange has been successfull")
print("New Alice's key: ", new_alice_key)
print("New Bob's key: ", new_bob_key)
else:
print("Key exchange has been tampered! Check for eavesdropper or try again")
print("New Alice's key is invalid: ", new_alice_key)
print("New Bob's key is invalid: ", new_bob_key)
Everything overlaps perfectly, that is indeed almost trivial. It's time to introduce Eve, the eavesdropper, and see what happens. We create Eve's circuit and we initiliaze it to Alice's state.
In [12]:
eve = QuantumCircuit(qr, cr, name='Eve')
SendState(alice, eve, 'Alice')
Just like Bob, Eve doesn't know which basis to use and she picks them randomly while recording her choice in a (table) list
In [13]:
eve_table = []
for index in range(len(qr)):
if 0.5 < np.random.random():
eve.h(qr[index])
eve_table.append('X')
else:
eve_table.append('Z')
She measures according to her basis choice and she generates her candidate key
In [14]:
for index in range(len(qr)):
eve.measure(qr[index], cr[index])
# Execute (build and run) the quantum circuit
backend = Aer.get_backend('qasm_simulator')
result = execute(eve, backend=backend, shots=1).result()
# Result of the measure is Eve's key
eve_key = list(result.get_counts(eve))[0]
eve_key = eve_key[::-1]
Up to now, Eve did exactly what Bob did in the previous example. From this point on, however, things are a bit tricky. Eve has measured the state causing qubits to collapse in different eigenstates. This property is not easy to implement in QISKit because measurement results are stored in classical registered, while the qubits themselves are "unchanged". Therefore we need to update Eve's qubits to the new altered states starting from the results of the measures (Eve's key), reversing the instructions that Eve has executed, and apply them to qubits when necessary, which means when the basis choice was different.
You can try figure out yourself how a state is changed after a measurement, but remember that unitary operators in general don't commute.
In [15]:
# Update states to new eigenstates (of wrongly chosen basis)
for qubit, basis in enumerate(zip(alice_table, eve_table)):
if basis[0] == basis[1]:
print("Same choice for qubit: {}, basis: {}" .format(qubit, basis[0]))
else:
print("Different choice for qubit: {}, Alice has {}, Eve has {}" .format(qubit, basis[0], basis[1]))
if eve_key[qubit] == alice_key[qubit]:
eve.h(qr[qubit])
else:
if basis[0] == 'X' and basis[1] == 'Z':
eve.h(qr[qubit])
eve.x(qr[qubit])
else:
eve.x(qr[qubit])
eve.h(qr[qubit])
Eve's altered state is now sent to Bob that performs the usual routine
In [16]:
SendState(eve, bob, 'Eve')
bob_table = []
for index in range(len(qr)):
if 0.5 < np.random.random():
bob.h(qr[index])
bob_table.append('X')
else:
bob_table.append('Z')
for index in range(len(qr)):
bob.measure(qr[index], cr[index])
result = execute(bob, backend=backend, shots=1).result()
plot_histogram(result.get_counts(bob))
bob_key = list(result.get_counts(bob))[0]
bob_key = bob_key[::-1]
After the measure Alice and Bob share the basis table lists and perform the usual checks
In [17]:
keep = []
discard = []
for qubit, basis in enumerate(zip(alice_table, bob_table)):
if basis[0] == basis[1]:
print("Same choice for qubit: {}, basis: {}" .format(qubit, basis[0]))
keep.append(qubit)
else:
print("Different choice for qubit: {}, Alice has {}, Bob has {}" .format(qubit, basis[0], basis[1]))
discard.append(qubit)
acc = 0
for bit in zip(alice_key, bob_key):
if bit[0] == bit[1]:
acc += 1
print('\nPercentage of qubits to be discarded according to table comparison: ', len(keep)/n)
print('Measurement convergence by additional chance: ', acc/n)
new_alice_key = [alice_key[qubit] for qubit in keep]
new_bob_key = [bob_key[qubit] for qubit in keep]
acc = 0
for bit in zip(new_alice_key, new_bob_key):
if bit[0] == bit[1]:
acc += 1
print('\nPercentage of similarity between the keys: ', acc/len(new_alice_key))
if (acc//len(new_alice_key) == 1):
print("\nKey exchange has been successfull")
print("New Alice's key: ", new_alice_key)
print("New Bob's key: ", new_bob_key)
else:
print("\nKey exchange has been tampered! Check for eavesdropper or try again")
print("New Alice's key is invalid: ", new_alice_key)
print("New Bob's key is invalid: ", new_bob_key)
As you can see when Alice and Bob reveal their key to each other they notice a discordance: Eve has been caught! To really get the percentages right, you can try repeating the experiment multiple times or you can write a higher routine that iterates the key sharing; in either case you will se that they converge to the expected values.