Day 5 BB84 Protocol.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SRuLyIYAPT4S"
   },
   "source": [
    "# Quantum Cryptography using BB84\n",
    "This third exercise focuses on **[BB84](https://en.wikipedia.org/wiki/BB84)**, a cryptography protocol developed in 1984 by one of the most famous IBMers, Charles Bennett, together with his colleague Gilles Brassard. This scheme was realized five years later in the first demonstration of [quantum key distribution](https://en.wikipedia.org/wiki/Quantum_key_distribution) by Bennett and colleague John Smolin at IBM [C. H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin, J. of Cryptography **5**, 3 (1992) ].  Both Charles and John are still members of the IBM Quantum team.\n",
    "\n",
    "\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/qiskit-community/may4_challenge_exercises/master/ex03/charlie_john_qkd.jpg\" width=\"500\"/>\n",
    "<center>Charles Bennett and John Smolin working on the first demonstration of quantum key distribution, IBM T.J. Watson Research Center.</center>\n",
    "\n",
    "\n",
    "\n",
    "The goal of the BB84 protocol is to create a secret key between two parties, Alice and Bob, that can then be used by both parties to encrypt and decrypt a hidden message. In this exercise we will guide you through the different steps of the protocol to create such a secret key to decrypt our encrypted message.\n",
    "\n",
    "\n",
    "## BB84 protocol\n",
    "\n",
    "Let's walk through the steps of the BB84 protocol:\n",
    "\n",
    "1. In the first step, Alice chooses two random bit strings, $k$ and $b$, that each consist of $n$ bits. Her bit string $k$ contains the actual bits she wants to encode (out of which the key will later be formed), while $b$ determines the bases in which she will encode her bits. For $b_i=0$ (i.e., if the $i^{th}$ bit is zero), she encodes the $i^{th}$ qubit in the standard $\\{|0\\rangle, |1\\rangle \\}$ basis, while for $b_i=1$, she encodes it in the $\\{|+\\rangle, |-\\rangle \\}$ basis, where $|+\\rangle:=\\frac{1}{\\sqrt{2}}(|0\\rangle +|1\\rangle)$, $|-\\rangle:=\\frac{1}{\\sqrt{2}}(|0\\rangle -|1\\rangle)$. \n",
    "This becomes more illustrative when representing each basis by two perpendicular arrows, where the two different bases are rotated by $45^\\circ$.\n",
    "The encoding of each qubit $q_i$ would therefore look like the following:\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/qiskit-community/may4_challenge_exercises/master/ex03/encoding_Alice.png\" alt=\"drawing\" width=\"300\"/>\n",
    "\n",
    "2. After encoding her $n$ qubits, Alice sends these qubits to Bob. Bob also chooses a random bit string $\\tilde{b}$ consisting of $n$ bits that determines in which bases he is going to perform measurements. He stores the outcomes of his measurements $\\tilde{k_i}$ together with the corresponding basis bits $\\tilde{b_i}$ in a table.\n",
    "\n",
    "3. Next, Alice and Bob compare their basis bits $b_i$ and $\\tilde{b}_i$. Whenever $b_i \\neq \\tilde{b}_i$, Bob measured in a different basis than Alice's qubit was encoded in, so he gets each outcome with probability $\\frac{1}{2}$. Alice and Bob therefore discard all key bits corresponding to these basis bits. If $b_i = \\tilde{b}_i$, however, they prepared and measured the qubit in the same basis, so (unless someone eavesdropped) Bob will get the key bit that Alice encoded, $\\tilde{k}_i = k_i$. These outcomes then compose the key.\n",
    "\n",
    "## An illustrated example\n",
    "\n",
    "Suppose Alice's random bit strings are $k=`0111001`$ and $b=`1101000`$ and Bob's random bit string is $\\tilde{b}=`1001101`$. Try to understand the other entries in the table below. Note that in the case where the basis bits are different, Bob has a 50% chance to get each outcome, so here one of them was chosen randomly.\n",
    "\n",
    "<img src=\"https://raw.githubusercontent.com/qiskit-community/may4_challenge_exercises/master/ex03/example_bb84.png\" alt=\"drawing\" width=\"600\"/>\n",
    "\n",
    "The key produced in this example would be '0110'. To make sure that the key is secret and correct, Alice and Bob would \"sacrifice\" some of their key bits to check that no one eavesdropped. If someone had measured a qubit on the way, this could have changed the state of that qubit and with probability $\\frac{1}{4}$, Bob's and Alice's key bits will be different. By checking $m$ bits, the probability to not notice an eavesdropper decreases as $\\left(\\frac{3}{4}\\right)^m$. Thus, if they check enough bits and they are all the same, they can assume that no one eavesdropped and their key is secret. However, to keep things simple, we will not perfom these tests in this excercise. Instead, all bits of the key will be used.\n",
    "\n",
    "### Message encrpytion\n",
    "Once a secret key is distributed, Alice can encrypt her message by using the so-called [one-time pad](https://en.wikipedia.org/wiki/One-time_pad) technique: she simply adds the key bits on top of her secret message bits that she wants to send. Using the example above, her key is $\\text{key}=`0110`$. If her secret message bit string is $m=`1100`$, the encrypted message will be $c=m\\oplus \\text{key} \\mod 2 = `1010`$. Bob can then decrypt the message by adding his key on that encrypted message, $m=c\\oplus \\text{key} \\mod 2$.\n",
    "\n",
    "## Your task \n",
    "\n",
    "In the following tasks, you play the role of Bob. You will create such a secret key with Alice and use it to decrypt the encrypted message from her.\n",
    "\n",
    "(**2 points**)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "tf9C08ykPT4t"
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "# Importing standard Qiskit libraries\n",
    "import random\n",
    "from qiskit import *\n",
    "from qiskit.tools.jupyter import *\n",
    "from qiskit.visualization import *\n",
    "\n",
    "#Get the library to check the answers\n",
    "%pip install -I git+https://github.com/mnp-club/MnP_QC_Workshop.git\n",
    "from mnp_qc_workshop_2020.bb84 import *\n",
    "\n",
    "# Configuring account\n",
    "provider = IBMQ.load_account()\n",
    "backend = provider.get_backend('ibmq_qasm_simulator')  # with this simulator it wouldn't work \\\n",
    "\n",
    "# Initial setup\n",
    "random.seed(64) # do not change this seed, otherwise you will get a different key"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "Collecting git+https://github.com/mnp-club/MnP_QC_Workshop.git\n",
    "  Cloning https://github.com/mnp-club/MnP_QC_Workshop.git to /tmp/pip-req-build-fn6a1g3t\n",
    "  Running command git clone -q https://github.com/mnp-club/MnP_QC_Workshop.git /tmp/pip-req-build-fn6a1g3t\n",
    "Building wheels for collected packages: mnp-qc-workshop-2020\n",
    "  Building wheel for mnp-qc-workshop-2020 (setup.py) ... done\n",
    "  Created wheel for mnp-qc-workshop-2020: filename=mnp_qc_workshop_2020-0.1-py3-none-any.whl size=6878 sha256=c24d68e0234beab968f5f3b13aa37e618bfa7c51a0e8ddd5c668d9b4c5b3fc80\n",
    "  Stored in directory: /tmp/pip-ephem-wheel-cache-g4vb4u20/wheels/8a/05/36/f117ccc148756e959adcc34f0e038da439d98f3d4d8b1e8133\n",
    "Successfully built mnp-qc-workshop-2020\n",
    "Installing collected packages: mnp-qc-workshop-2020\n",
    "Successfully installed mnp-qc-workshop-2020-0.1\n",
    "Note: you may need to restart the kernel to use updated packages.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BzRs6563PT44"
   },
   "source": [
    "\n",
    "\n",
    "### Simulating this protocol in Qiskit\n",
    "\n",
    "(**8 points**)\n",
    "\n",
    "In this exercise, there are three steps. Each of these three steps is completed $n=16$ times. Before the protocol begins, Alice will choose two random bit strings, $k$ and $b$.\n",
    "\n",
    "1. Alice will prepare each qubit using the function `Alice_prepare_qubit`, which is already written for you.\n",
    "\n",
    "2. Bob measures his qubit using a specific set of bases, which we have given you in a variable called `bases`. **You will supply the procedure that Bob takes in the function `Bob_measure_qubit`.**\n",
    "\n",
    "3. A quantum circuit for this sequence of operations is created. It will be called `this_qubit_circuit` for each qubit, and all such circuits are collected together in an array called `all_qubit_circuits`. We have supplied the code to do this.\n",
    "\n",
    "Finally, we run `all_qubit_circuits` on the IBM high-performance cloud simulator called `ibmq_qasm_simulator` and collect the results of the measurements into a bitstring called `bits`. We have supplied the code to do this.\n",
    "\n",
    "You will then follow the protocol to decrypt a message using the extracted key from the BB84 protocol.\n",
    "\n",
    "\n",
    "### i) Execute step 2 of the BB84 protocol to get your bitstring\n",
    "To do so, you need a random bit string $\\tilde{b}$ that determines the bases in which you should perform the measurements. In order to reproduce the key that we used to encrypt our secret message, we provide you with this \"random\" `bases` bit string of 16 bits that uses seed \"64\".\n",
    "**Perform measurements in the bases corresponding to the given bit string and return the outcome as a bit string in the form '$\\tilde{b}_0\\tilde{b}_1...\\tilde{b}_{n-1}$'.** Note that Qiskit returns outcomes always in reverse order, so if $|\\tilde{q}_0\\rangle = |0 \\rangle $ and $|\\tilde{q}_1\\rangle = |\\tilde{q}_2\\rangle = |1 \\rangle $, it will return the outcome '110'. You can check whether your bit string is correct by `check_bits(bitstring)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "p_rBUf_RPT46"
   },
   "outputs": [],
   "source": [
    "# This is your 'random' bit string that determines your bases\n",
    "numqubits = 16\n",
    "bob_bases = str('{0:016b}'.format(random.getrandbits(numqubits)))\n",
    "\n",
    "def bb84():\n",
    "    print('Bob\\'s bases:', bob_bases)\n",
    "\n",
    "    # Now Alice will send her bits one by one...\n",
    "    all_qubit_circuits = []\n",
    "    for qubit_index in range(numqubits):\n",
    "\n",
    "        # This is Alice creating the qubit\n",
    "        thisqubit_circuit = alice_prepare_qubit(qubit_index)\n",
    "\n",
    "        # This is Bob finishing the protocol below\n",
    "        bob_measure_qubit(bob_bases, qubit_index, thisqubit_circuit)\n",
    "        \n",
    "        # We collect all these circuits and put them in an array\n",
    "        all_qubit_circuits.append(thisqubit_circuit)\n",
    "        \n",
    "        \n",
    "    # Now execute all the circuits for each qubit\n",
    "    results = execute(all_qubit_circuits, backend=backend, shots=1).result()\n",
    "    # And combine the results\n",
    "    bits = ''\n",
    "    for qubit_index in range(numqubits):\n",
    "        bits += [measurement for measurement in results.get_counts(qubit_index)][0]\n",
    "        \n",
    "    return bits\n",
    "\n",
    "# Here is your task\n",
    "def bob_measure_qubit(bob_bases, qubit_index, qubit_circuit):\n",
    "    if (bob_bases[qubit_index] == '1'):\n",
    "        qubit_circuit.h(0)\n",
    "    qubit_circuit.measure(0,0)\n",
    "           \n",
    "bits = bb84()      \n",
    "print('Bob\\'s bits: ', bits)\n",
    "check_bits(bits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "Bob's bases: 0111100111100101\n",
    "Bob's bits:  1001001010000000\n",
    "So far, so good 🎉! You got the right bits!\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "q5KORnjcPT5C"
   },
   "source": [
    "After you performed your measurements, Alice announces her bases bits which are stored in <code>alice_bases</code> in the next cell\n",
    "\n",
    "### ii) Execute step 3 of the BB84 protocol to extract the key\n",
    "To do so, compare Alice's bases bits $b$ to your bases bits $\\tilde{b}$ (given in the previous step) and extract the key by keeping only the outcomes when your bases were the same.\n",
    "You can check whether your key is correct by `check_key(key)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "69m4Px15PT5F"
   },
   "outputs": [],
   "source": [
    "alice_bases = '0100000101011100' # Alice's bases bits\n",
    "key = ''\n",
    "for i in range(numqubits):\n",
    "    if (alice_bases[i] == bob_bases[i]):\n",
    "        key += bits[i]\n",
    "print(key)\n",
    "check_key(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "10010000\n",
    "So far, so good 🎉! You got the right key!\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "xzHVo1R_PT5N"
   },
   "source": [
    "Using this key, Alice can now send you her private encrypted message. While for full security a key would only be used once, she will now use her 8-bit-long key 43 times in a row to encrypt her 344-bit-long message. Her encrypted message is stored in <code>message</code> variable of the next cell.\n",
    "\n",
    "A small note I would like to make is that generally the key is kept to be of a larger length since this ratio is actually very skewed but for demonstration purposes of the concept in play we will use it in this way.\n",
    "\n",
    "### iii) Decrypt the message using the extracted key\n",
    "The message encryption section in the introduction describes how to do so. You can check whether your decrypted message bit string is correct by <code>check_decrypted(decrypted)</code>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "wi3f0W8tPT5O"
   },
   "outputs": [],
   "source": [
    "message = get_message()# encrypted message\n",
    "decrypted = ''\n",
    "\n",
    "for i in range(len(message)):\n",
    "    decrypted += str((int(message[i])+int(key[i % 8])) % 2)\n",
    "print(decrypted)\n",
    "check_decrypted(decrypted)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "01101000011101000111010001110000011100110011101000101111001011110111011101110111011101110010111001111001011011110111010101110100011101010110001001100101001011100110001101101111011011010010111101110111011000010111010001100011011010000011111101110110001111010111010101100010001110000011001001011000011000100011000101000011001110000110111101110011\n",
    "So far, so good 🎉! You got the right decrypted message!\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Jee1GdjiPT5a"
   },
   "source": [
    "Now you would have obtained the decrypted message. You have a pleasent surprise waiting for you after you convert this using ASCII notation. In the cell below, convert every of the forty three 8 bit pieces of the string to a character using the regular ASCII notation. The <code>check_message</code> function will tell you whether you have correctly converted it or not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "42slKb6aPT5b"
   },
   "outputs": [],
   "source": [
    "decrypted_to_string_ASCII = ''\n",
    "for i in range(0,len(decrypted),8):\n",
    "    decrypted_to_string_ASCII += chr(int(decrypted[i:i+8], 2))\n",
    "print(decrypted_to_string_ASCII)    \n",
    "check_message(decrypted_to_string_ASCII)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "https://www.youtube.com/watch?v=ub82Xb1C8os\n",
    "Congratulations 🎉! You have succesfully decrypted the message which is https://www.youtube.com/watch?v=ub82Xb1C8os. Do go ahead and try the link. Its worth it ;)\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "mhi2TD2EPT5i"
   },
   "source": [
    "The documentation in this notebook has been taken mainly from <a href=\"https://github.com/qiskit-community/may4_challenge_exercises/blob/master/ex03/Challenge3_BB84.ipynb\">here</a>. Kudos to the qiskit team for documenting this so well."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Day 5 BB84 Protocol.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}