Information-Theoretic Security.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Information-Theoretic Security (examples and exercises)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Definitions of Information Entropy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Source Entropy\n",
    "\n",
    "Given a message $m$ taken from a set of messages $\\{m_1, \\dots, m_N\\}$ with probabilities $p(m_i)\\ 1\\leq i \\leq N$, the source entropy is\n",
    "\n",
    "$H(m) = -\\sum_{i=1}^N p_i \\log_2 p_i$\n",
    "\n",
    "Source entropy measures the minimum number of bits necessary to encode the source messages."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Joint Entropy\n",
    "\n",
    "Given a message $m$ taken from a set of messages $\\{m_i\\}$ with probabilities $p(m_i)$ and a message $c$ taken from a set of messages $\\{c_j\\}$  with probabilities $p(c_j)$ and joint probabilities $p(m_i,c_j)$, the joint entropy is\n",
    "\n",
    "$H(m,c) = - \\sum_{i,j} p(m_i,c_j) \\log_2 p(m_i,c_j)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Conditional Entropy\n",
    "\n",
    "Given a message $m$ taken from a set of messages $\\{m_i\\}$ with probabilities $p(m_i)$ and a ciphertext $c$ taken from a set of messages $\\{c_j\\}$  with probabilities $p(c_j)$ and joint probabilities $p(m_i,c_j)$, the conditional entropy is\n",
    "\n",
    "$H(c|m) = \\sum_i H(c|m_i) \\Pr[m_i]$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chain Rule\n",
    "\n",
    "$H(m,c) = H(m) + H(c|m) = H(c) + H(m|c)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bayes' Theorem\n",
    "\n",
    "$H(m|c) = H(c|m) - H(c) + H(m)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Mutual Information\n",
    "\n",
    "$I(m;c) = H(m)-H(m|c) = H(c)-H(c|m)$\n",
    "\n",
    "Mutual information is equal to zero if and only if the message and the ciphertext  are independent."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 1\n",
    "\n",
    "Assume that the message space is $M = \\{\\texttt{A}, \\texttt{Z} \\}$.\n",
    "Alice chooses $m=\\texttt{A}$ with probability 0.7 and $m=\\texttt{Z}$ with probability 0.3. Alice encrypts the message with some random key.\n",
    "\n",
    "Eve, an eavesdropper, sees $c=\\texttt{B}$. What can she say about the plaintext?\n",
    "What is $I(m;c)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution (analytical)**\n",
    "\n",
    "The entropy of the message source is:\n",
    "\n",
    "$H(m) =\n",
    "- \\Pr[m=\\texttt{A}] \\log_2 \\Pr[m=\\texttt{A}]\n",
    "- \\Pr[m=\\texttt{Z}] \\log_2 \\Pr[m=\\texttt{Z}]\t\n",
    "= 0.88\\,\\mathrm{bit}$\n",
    "\n",
    "Given a plaintext, all ciphertexts are equally likely, so \n",
    "\n",
    "$H(c|m) = 26 \\times \\frac{1}{26}\\log_2 26 = 4.7\\,\\mathrm{bit}$\n",
    "\n",
    "We already know that\n",
    "\n",
    "$\\Pr[c=\\texttt{A}]=\\dots=\\Pr[c=\\texttt{Z}]=1/26$\n",
    "\n",
    "thus $H(c)=4.7\\,\\mathrm{bit}$.\n",
    "\n",
    "Therefore:\n",
    "\n",
    "$I(m;c) = H(c) - H(c|m) = 0$\n",
    "\n",
    "No information is learned."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution (empirical)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import random, randint\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# calculates the entropy of a list of elements\n",
    "# builds the empyrical pdf of the list\n",
    "# then applies the definition\n",
    "def entropy_of_list(l):\n",
    "    histogram = {x:(l.count(x)+0.0)/len(l) for x in l}\n",
    "    return sum([-x*log(x,2) for x in histogram.values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Instantiate a shift cipher over the alphabet\n",
    "S = ShiftCryptosystem(AlphabeticStrings());\n",
    "\n",
    "# Define the random key generator\n",
    "def keygen():\n",
    "    return randint(0,25)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# message source\n",
    "def message1():\n",
    "    if random()<=0.7:\n",
    "        return 'A'\n",
    "    else:\n",
    "        return 'Z'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Empirical Entropy of source is: 0.893173458377857\n"
     ]
    }
   ],
   "source": [
    "# generate several random messages \n",
    "m = [S.encoding(message1()) for i in range(1000)]\n",
    "\n",
    "# print empirical entropy of the message source\n",
    "print \"Empirical Entropy of source is:\", entropy_of_list(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Empirical Entropy of ciphertext is: 4.68926722828748\n"
     ]
    }
   ],
   "source": [
    "# Encrypt each message with a different random key\n",
    "c = [ S.enciphering( keygen() , x ) for x in m ]\n",
    "\n",
    "print \"Empirical Entropy of ciphertext is:\", entropy_of_list(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 2\n",
    "\n",
    "Assume that $\\Pr[m=\\texttt{kim}]=0.5$, $\\Pr[m=\\texttt{ann}]=0.2$, and $\\Pr[m=\\texttt{boo}]=0.3$.\n",
    "\n",
    "What is $I(m;c)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution (analytical)** \n",
    "Analogous calculations can be done using information entropy.\n",
    "The entropy of the message source is:\n",
    "\n",
    "$H(m) = 1.49 bit$\n",
    "\n",
    "Ciphertexts are not equally likely. There are only $26+26=52$ different CTs, half of which obtained from $\\texttt{kim}$ and half from $\\texttt{ann}$ and $\\texttt{boo}$.\n",
    "\n",
    "$H(c) = - 52 \\frac{1}{52}\\log_2\\frac{1}{52} = 5.7 bit$\n",
    "\n",
    "Given a plaintex, all ciphertexts are equally likely:\n",
    "$H(c|m) = 4.7 bit$.\n",
    "\n",
    "$I(m;c) = H(c) -H(c|m) = 1 bit$\n",
    "meaning that knowledge of $c$ gives us 1 bit of information.\n",
    "\n",
    "What does it mean that mutual information is 1 bit? It means that there exists an agorithm that can answer a yes/no question about the plaintext by just looking to the ciphertext.\n",
    "\n",
    "This does not tell us what is the algorithm to obtain this bit. Neither whether this algorithm is efficient. It only tells us that this algorithm exists.\n",
    "The following is just an example:\n",
    "\n",
    "```\n",
    "def plaintext_is_kim(ciphertext):\n",
    "    if last two letters of ciphertext are the same:\n",
    "        return false # plaintext is not kim\n",
    "    else\n",
    "        return true # plaintext is kim\n",
    "    end if\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Solution (empirical)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "# generate random three letter messages\n",
    "def message2():\n",
    "    r = random() \n",
    "    if r <= 0.5:\n",
    "        return 'KIM'\n",
    "    if r <= 0.7:\n",
    "        return 'ANN'\n",
    "    else:\n",
    "        return 'BOO'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Empirical Entropy of source is: 1.47717700758957\n"
     ]
    }
   ],
   "source": [
    "# generate random messages \n",
    "m = [S.encoding(message2()) for i in range(1000)]\n",
    "\n",
    "# print empirical entropy of the message source\n",
    "print \"Empirical Entropy of source is:\", entropy_of_list(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Empirical Entropy of ciphertext is: 5.67313984293835\n"
     ]
    }
   ],
   "source": [
    "# Encrypt each message with a random key\n",
    "c=[S.enciphering( keygen(), x) for x in m]\n",
    "\n",
    "print \"Empirical Entropy of ciphertext is:\", entropy_of_list(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise 3\n",
    "\n",
    "Consider a Vigènere cipher. Messages are 4-character sequences of letters. Passwords are $n$-character long.\n",
    "\n",
    "Assume that there are three possible messages, with different probabilities.\n",
    "\n",
    "| Message | Probability |\n",
    "|---|---|\n",
    "| $m_1$ = BEBA | 0.5 |\n",
    "| $m_2$ = DEDA | 0.3 |\n",
    "| $m_3$ = CFCB | 0.2 |\n",
    "\n",
    "1. Calculate the entropy of the source.\n",
    "2. Calculate the entropy of the key with $n=1,2,4$.\n",
    "3. Calculate the entropy of the ciphertext with $n=1,2,4$.\n",
    "4. Calculate the information leak of the ciphertext with $n=1,2,4$\n",
    "5. Is the cipher of this exercise perfectly secret?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Solution\n",
    "\n",
    "#### Part 1\n",
    "\n",
    "$H(M) = -0.5\\log_2 0.5 -0.3\\log_2 0.3 -0.2\\log_2 0.2 = 1.48$\n",
    "\n",
    "#### Part 2\n",
    "\n",
    "| $n$ | $H(K)$ |\n",
    "| --- | ------ |\n",
    "| 1   | 4.7    |\n",
    "| 2   | 9.4    |\n",
    "| 4   | 18.8   |\n",
    "\n",
    "\n",
    "#### Part 3\n",
    "\n",
    "Let call $C_i$ the set of possible ciphertexts for message $m_i$.\n",
    "\n",
    "With $n=1$, we have\n",
    "* $C_1 = \\{ \\text{BEBA}, \\text{CFCB}, \\text{DGDC}, \\dots \\}$\n",
    "* $C_2 = \\{ \\text{DEDA}, \\text{EFEB}, \\text{FGFB}, \\dots \\}$\n",
    "* $C_3 = \\{ \\text{CFCB}, \\text{DGDC}, \\text{EHED}, \\dots \\}$\n",
    "\n",
    "So $C_1 = C_3$, while $C_2$ is distinct. Thus, we have $2\\times26=52$ ciphertexts. The first set has probability $0.5+0.2=0.7$. The second set has probability $0.3$.\n",
    "\n",
    "$H(C)=\n",
    "    -26\\times 0.7/26\\log_2 0.7/26\n",
    "    -26\\times 0.3/26\\log_2 0.3/26\n",
    "    = 5.58\n",
    "$\n",
    "\n",
    "With $n=2$, we have again $C_1 = C_2 = C_3$. In fact, the key $(2,0)$ can map BEBA into DEDA, while the key $(1,1)$ can map BEBA into CFCB. Consequently all the messages generate the same $26^2=676$ ciphertexts.\n",
    "\n",
    "$H(C)= -676 / 676 \\log_2(1/676)=9.4$\n",
    "\n",
    "With $n=4$, we have $C_1 = C_2 = C_3$. Thus, we have $26^4=456976$ equally likely ciphertexts.\n",
    "\n",
    "$H(C)= 26^4 / 26^4 \\log_2(1/26^4)=18.8$\n",
    "\n",
    "#### Part 4\n",
    "\n",
    "With $n=1$\n",
    "\n",
    "$H(C|M)=H(C_1)\\Pr(m_1) + H(C_2)\\Pr(m_2) + H(C_3)\\Pr(m_3)= 4.7$\n",
    "\n",
    "Then\n",
    "$\n",
    "\tI(M;C) =\n",
    "\tH(C)-H(C|M) = 5.58 - 4.7 = 0.88\n",
    "$\n",
    "\n",
    "With $n=2$\n",
    "\n",
    "$\n",
    "\tH(C|M)=H(C_1)\\Pr(m_1) + H(C_2)\\Pr(m_2+m_3)= 9.4\n",
    "$\n",
    "\n",
    "Then\n",
    "$\n",
    "\tI(M;C) =\n",
    "\tH(C)-H(C|M) = 9.4-9.4 = 0\n",
    "$\n",
    "\n",
    "With $n=4$\n",
    "\n",
    "$\n",
    "\tH(C|M)=H(C_1)\\Pr(m_1+m_2+m_3)= 18.8\n",
    "$\n",
    "\n",
    "Then\n",
    "$\n",
    "\tI(M;C) =\n",
    "\tH(C)-H(C|M) = 18.8-18.8=0\n",
    "$\n",
    "\n",
    "#### Part 5\n",
    "If these three are the only possible messages, then with $n=2$ and $n=4$ we have perfect secrecy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}