<jupyter_start><jupyter_text>Quantum CryptographyIn 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 ou to read the [Introduction notebook](https://github.com/rugantio/Quantum_crypto/blob/master/Introduction.ipynb), 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.  RequirementsThroughout the notebook we will make use of:- Python 3.6 (although python 3.5 works as well)- QISKit (with a Qconfig file for remote backend) - Standard python scientific libs stack: numpy etc.- Knowledge of basic Quantum Mechanics is assumed- Notions of traditional Cryptography are helpful although not strictly necessary  Quantum Key DistributionIn 1984, building on the work of *Wiesner*, *<NAME>*, an IBM's researcher, and *<NAME>*, 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.   QKD proof of concept on a quantum  computerQuantum 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:<jupyter_code># Checking the version of PYTHON; we only support > 3.5
import sys
if sys.version_info < (3,5):
    raise Exception('Please use Python version 3.5 or greater.')

# Import numpy for random number generation
import numpy as np

# Import QISKit
from qiskit import QuantumProgram

# Import credentials for chip backend
# Qconfig.py has to be initiated with an API token for a remote backend
from qiskit import Qconfig

# Import basic plotting tools
from qiskit.tools.visualization import plot_histogram<jupyter_output><empty_output><jupyter_text>Next we do some preliminary settings to better manipulate quantum circuits and we set the number of available (qu)bits to 16<jupyter_code># Quantum program setup 
qp = QuantumProgram()
qp.set_api(Qconfig.APItoken, Qconfig.config['url']) # set the APIToken and API url

# 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 = qp.create_quantum_register('qr', n)
cr = qp.create_classical_register('cr', n)<jupyter_output><empty_output><jupyter_text>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<jupyter_code># Quantum circuit for alice state
alice = qp.create_circuit('Alice', [qr], [cr])

# 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<jupyter_output><empty_output><jupyter_text>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.<jupyter_code># 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<jupyter_output><empty_output><jupyter_text>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.<jupyter_code># 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 = qp.get_qasm([qc1_name][0]).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')<jupyter_output><empty_output><jupyter_text>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<jupyter_code>bob = qp.create_circuit('Bob', [qr], [cr])

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')<jupyter_output><empty_output><jupyter_text>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).<jupyter_code># Measure all qubits
for index in range(len(qr)): 
    bob.measure(qr[index], cr[index])
    
# Execute the quantum circuit 
backend = 'local_qasm_simulator' 
result = qp.execute('Bob', backend=backend, shots=1, timeout=600)
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<jupyter_output><empty_output><jupyter_text>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.<jupyter_code>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)<jupyter_output>Same choice for qubit: 0, basis: Z
Different choice for qubit: 1, Alice has Z, Bob has X
Same choice for qubit: 2, basis: X
Different choice for qubit: 3, Alice has Z, Bob has X
Same choice for qubit: 4, basis: X
Different choice for qubit: 5, Alice has Z, Bob has X
Different choice for qubit: 6, Alice has Z, Bob has X
Same choice for qubit: 7, basis: Z
Same choice for qubit: 8, basis: X
Same choice for qubit: 9, basis: Z
Same choice for qubit: 10, basis: X
Same choice for qubit: 11, basis: Z
Different choice for qubit: 12, Alice has X, Bob has Z
Same choice for qubit: 13, basis: X
Different choice for qubit: 14, Alice has Z, Bob has X
Different choice for qubit: 15, Alice has X, Bob has Z<jupyter_text>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.<jupyter_code>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)<jupyter_output>Percentage of qubits to be discarded according to table comparison:  0.5625
Measurement convergence by additional chance:  0.75<jupyter_text>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.<jupyter_code>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))<jupyter_output>Percentage of similarity between the keys:  1.0<jupyter_text>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.<jupyter_code>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)<jupyter_output>Key exchange has been successfull
New Alice's key:  ['0', '0', '1', '1', '1', '0', '0', '0', '1']
New Bob's key:  ['0', '0', '1', '1', '1', '0', '0', '0', '1']<jupyter_text>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.<jupyter_code>eve = qp.create_circuit('Eve', [qr], [cr])
SendState(alice, eve, 'Alice')<jupyter_output><empty_output><jupyter_text>Just like Bob, Eve doesn't know which basis to use and she picks them randomly while recording her choice in a (table) list<jupyter_code>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')<jupyter_output><empty_output><jupyter_text>She measures according to her basis choice and she generates her candidate key<jupyter_code>for index in range(len(qr)): 
    eve.measure(qr[index], cr[index])
    
# Execute (build and run) the quantum circuit 
backend = 'local_qasm_simulator' 
result = qp.execute('Eve', backend=backend, shots=1, timeout=600)

# Result of the measure is Eve's key
eve_key = list(result.get_counts('Eve'))[0]
eve_key = eve_key[::-1]<jupyter_output><empty_output><jupyter_text>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.<jupyter_code># 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])<jupyter_output>Different choice for qubit: 0, Alice has Z, Eve has X
Different choice for qubit: 1, Alice has Z, Eve has X
Different choice for qubit: 2, Alice has X, Eve has Z
Same choice for qubit: 3, basis: Z
Same choice for qubit: 4, basis: X
Different choice for qubit: 5, Alice has Z, Eve has X
Same choice for qubit: 6, basis: Z
Different choice for qubit: 7, Alice has Z, Eve has X
Same choice for qubit: 8, basis: X
Different choice for qubit: 9, Alice has Z, Eve has X
Different choice for qubit: 10, Alice has X, Eve has Z
Same choice for qubit: 11, basis: Z
Different choice for qubit: 12, Alice has X, Eve has Z
Same choice for qubit: 13, basis: X
Same choice for qubit: 14, basis: Z
Same choice for qubit: 15, basis: X<jupyter_text>Eve's altered state is now sent to Bob that performs the usual routine<jupyter_code>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 = qp.execute('Bob', backend=backend, shots=1, timeout=600)
plot_histogram(result.get_counts('Bob'))

bob_key = list(result.get_counts('Bob'))[0]
bob_key = bob_key[::-1]<jupyter_output><empty_output><jupyter_text>After the measure Alice and Bob share the basis table lists and perform the usual checks<jupyter_code>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)<jupyter_output>Different choice for qubit: 0, Alice has Z, Bob has X
Different choice for qubit: 1, Alice has Z, Bob has X
Same choice for qubit: 2, basis: X
Same choice for qubit: 3, basis: Z
Same choice for qubit: 4, basis: X
Same choice for qubit: 5, basis: Z
Same choice for qubit: 6, basis: Z
Same choice for qubit: 7, basis: Z
Different choice for qubit: 8, Alice has X, Bob has Z
Different choice for qubit: 9, Alice has Z, Bob has X
Same choice for qubit: 10, basis: X
Same choice for qubit: 11, basis: Z
Same choice for qubit: 12, basis: X
Different choice for qubit: 13, Alice has X, Bob has Z
Same choice for qubit: 14, basis: Z
Different choice for qubit: 15, Alice has X, Bob has Z

Percentage of qubits to be discarded according to table comparison:  0.625
Measurement convergence by additional chance:  0.3125

Percentage of similarity between the keys:  0.4

Key exchange has been tampered! Check for eavesdropper or try again
New Alice's key is invalid:  ['0', '1', '1', '0', '1', '1', '0', '0', '1[...]
{'fraction_non_alphanumeric': 0.08383089561210179, 'fraction_numerical': 0.011741134041274293, 'mean_word_length': 4.215464994775339, 'pattern_counts': {'":': 0, '<': 70, '<?xml version=': 0, '>': 68, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '305688', 'license': 'Apache-2.0', 'n_tokens_mistral': 7341, 'n_tokens_neox': 6772, 'n_words': 3526, 'path': 'Cryptography.ipynb', 'repo_name': 'rugantio/Quantum_crypto', 'size': '24973'}