Challenge3_BB84.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise 3: Quantum Cryptography\n",
    "This third exercise focuses on **[BB84](https://en.wikipedia.org/wiki/BB84)**, a cryptography protocol developed in 1984 by one of our 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=\"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=\"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=\"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",
    "## The challenge \n",
    "\n",
    "In the following four 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",
    "---\n",
    "For useful tips to complete this exercise as well as pointers for communicating with other participants and asking questions, please take a look at the following [repository](https://github.com/qiskit-community/may4_challenge_exercises). You will also find a copy of these exercises, so feel free to edit and experiment with these notebooks.\n",
    "\n",
    "---\n",
    "\n",
    "### How we simulate this protocol in Qiskit\n",
    "\n",
    "In this exercise, there are three steps. Each of these three steps is completed $n=100$ 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 100 bits that uses seed \"84\".\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": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "ibmqfactory.load_account:WARNING:2020-05-06 15:46:09,305: Credentials are already in use. The existing account in the session will be replaced.\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Bob's bases: 1100111010011111111111110100000111010100100010011001001110100001010010111011010001011001111111011111\n",
      "Bob's bits:  1100110000011110001110001011000111110100000001001111110000000110000000001100010101010101101100000000\n",
      "So far, so good 🎉! You got the right bits!\n"
     ]
    }
   ],
   "source": [
    "%matplotlib inline\n",
    "\n",
    "# Importing standard Qiskit libraries\n",
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "from qiskit import execute, Aer, IBMQ\n",
    "from qiskit.tools.jupyter import *\n",
    "from qiskit.visualization import *\n",
    "from may4_challenge.ex3 import alice_prepare_qubit, check_bits, check_key, check_decrypted, show_message\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(84) # do not change this seed, otherwise you will get a different key\n",
    "\n",
    "# This is your 'random' bit string that determines your bases\n",
    "numqubits = 100\n",
    "bob_bases = str('{0:0100b}'.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",
    "    # Now execute all the circuits for each qubit\n",
    "    results = execute(all_qubit_circuits, backend=backend, shots=1).result()\n",
    "\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",
    "\n",
    "def bob_measure_qubit(bob_bases, qubit_index, qubit_circuit):    \n",
    "    if bob_bases[qubit_index] == '0':\n",
    "        qubit_circuit.measure(0,0)\n",
    "    elif 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": [
    "After you performed your measurements, Alice announces her bases bits:\n",
    "$$\n",
    "b = 1000000000010001111111001101100101000111110100110111111000110000011000001001100011100111010010000110\n",
    "$$ \n",
    "\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": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "So far, so good 🎉! You got the right key!\n"
     ]
    }
   ],
   "source": [
    "alice_bases = '10000000000100011111110011011001010001111101001101111110001100000110000010011000111'\\\n",
    "              '00111010010000110' # Alice's bases bits\n",
    "key = ''\n",
    "for i in range(len(alice_bases)):\n",
    "    if alice_bases[i] == bob_bases[i]:\n",
    "       key += bits[i]\n",
    "\n",
    "check_key(key)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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 50-bit-long key four times in a row to encrypt her 200-bit-long message. Her encrypted message is\n",
    "\n",
    "$$\n",
    "m = 0011011010100011101000001100010000001000011000101110110111100111111110001111100011100101011010111010\\\\\n",
    "\\qquad 1110100011101010010111111100101000011010011011011011101111010111000101111111001010101001100101111011\n",
    "$$\n",
    "\n",
    "### iii) Decrypt the message using the extracted key\n",
    "The [message encryption](#Message-encrpytion) section in the introduction describes how to do so. You can check whether your decrypted message bit string is correct by `check_decrypted(decrypted)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(50, 200)"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(key), len(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "So far, so good 🎉! You decrypted the message!\n"
     ]
    }
   ],
   "source": [
    "m = '0011011010100011101000001100010000001000011000101110110111100111111110001111100011100101011010111010111010001'\\\n",
    "    '1101010010111111100101000011010011011011011101111010111000101111111001010101001100101111011' # encrypted message\n",
    "decrypted = ''\n",
    "for i in range(len(m)):\n",
    "    var = int(m[i]) + int(key[i%len(key)])\n",
    "    var = var % 2\n",
    "    decrypted += str(var)\n",
    "\n",
    "check_decrypted(decrypted)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course there is an actual message encoded in this bit string. To encode letters, Alice used Morse code (see here for more details: https://en.wikipedia.org/wiki/Morse_code). However, as she could only send zeros and ones and wanted to keep her message as short as possible, she encoded \n",
    "\n",
    "- a dot (\"dit\") as '1'\n",
    "- a dash (\"dah\") as '11'\n",
    "- an intra-character gap (between each dot and dash within a character) as '0'\n",
    "- a short gap (that separates letters) as '00'\n",
    "- a medium gap (that separates words) as '000'.\n",
    "\n",
    "Here is an example:\n",
    "<img src=\"qiskit_morse.png\" alt=\"drawing\" width=\"500\"/>\n",
    "\n",
    "### iv) Try to decode Alice's message!\n",
    "In a first step, convert the decrypted message from above into morse code. In a second step, use the provided dictionary to decode the morse code. Copy and paste the solution string on the IBM Quantum Challenge page to complete the exercise and track your progress."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10110100100110101001101010010100110010110101101011001101011010011011011001101100110101011010010110100110101011010011011001011001101011011001010101011001101101011001010110010110011010011001010110011011\n",
      "['.-.', '.', '-..', '-..', '..', '-', '.-.-.-', '-.-.', '---', '--', '-..-.', '.-.', '-..-.', '--', '.-', '-.--', '....-', '--.-', '..-', '.-', '-.', '-', '..-', '--']\n"
     ]
    }
   ],
   "source": [
    "bin2morse = {'1':'.', '11': '-', '': '  '}\n",
    "morse = ''\n",
    "for i in decrypted.split('0'):    \n",
    "    morse += bin2morse[i]\n",
    "    #morse += ' '\n",
    "print(decrypted)\n",
    "print(morse.split('  '))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "e\n"
     ]
    }
   ],
   "source": [
    "for character, morse in MORSE_CODE_DICT.items():\n",
    "    if morse == '.':\n",
    "        print(character)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "    <p style=\"border: 2px solid black; padding: 2rem;\">\n",
       "        Congratulations 🎉! Submit the following text\n",
       "        <samp\n",
       "            style=\"font-family: monospace; background-color: #eee;\"\n",
       "        >reddit.com/r/may4quantum</samp>\n",
       "        on the\n",
       "        <a href=\"https://quantum-computing.ibm.com/challenges/4anniversary/?exercise=3&amp;answer=reddit.com%2Fr%2Fmay4quantum\" target=\"_blank\">\n",
       "            IBM Quantum Challenge page\n",
       "        </a>\n",
       "        to see if you are correct.\n",
       "    </p>\n",
       "    "
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "MORSE_CODE_DICT = { 'a':'.-', 'b':'-...', \n",
    "                    'c':'-.-.', 'd':'-..', 'e':'.', \n",
    "                    'f':'..-.', 'g':'--.', 'h':'....', \n",
    "                    'i':'..', 'j':'.---', 'k':'-.-', \n",
    "                    'l':'.-..', 'm':'--', 'n':'-.', \n",
    "                    'o':'---', 'p':'.--.', 'q':'--.-', \n",
    "                    'r':'.-.', 's':'...', 't':'-', \n",
    "                    'u':'..-', 'v':'...-', 'w':'.--', \n",
    "                    'x':'-..-', 'y':'-.--', 'z':'--..', \n",
    "                    '1':'.----', '2':'..---', '3':'...--', \n",
    "                    '4':'....-', '5':'.....', '6':'-....', \n",
    "                    '7':'--...', '8':'---..', '9':'----.', \n",
    "                    '0':'-----', ', ':'--..--', '.':'.-.-.-', \n",
    "                    '?':'..--..', '/':'-..-.', '-':'-....-', \n",
    "                    '(':'-.--.', ')':'-.--.-'} \n",
    "bin2morse = {'1':'.', '11': '-', '': '  '}\n",
    "morse = ''\n",
    "for i in decrypted.split('0'):    \n",
    "    morse += bin2morse[i]\n",
    "\n",
    "solution = ''\n",
    "for i in morse.split('  '):\n",
    "    for character, morse in MORSE_CODE_DICT.items():\n",
    "        if morse == i:\n",
    "            solution += character\n",
    "            \n",
    "show_message(solution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "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": 4
}