11 - Secret Sharing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Secret Sharing\n",
    "\n",
    "In this notebook, you'll learn some basic building blocks of Secure Multiparty Computation (MPC or SMPC). In doing so, you'll be able to more clearly reason about use cases where MPC is a good fit. Remember: the goal isn't to roll your own crypto, but instead to develop a basic mental model to understand why, where and how MPC can help.\n",
    "\n",
    "If this is interesting to you and you'd like to learn more, please have a read through [Morten Dahl's informative blog series on this topic and more in MPC!](https://mortendahl.github.io/2017/06/04/secret-sharing-part1/) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randrange"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 45"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's try to \"hide\" our number in a few ways naively..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "keys = [100, 22, 43, 56]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "enc_x = x - sum(keys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-176"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enc_x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "enc_x = x - sum(keys)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This \"works\", but it actually leaks information! Let's take another x as an example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = -1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "enc_x = x - sum(keys)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1221"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enc_x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, if someone was using the same keys, I could infer that one number is smaller than the other number or otherwise leak information about the original values.\n",
    "\n",
    "We could naively continue to find mechanisms that make this more secure, but there is actually a better way if we know some cryptography-math. Let's look at how we can hide information better in a field."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = 431\n",
    "x = 45"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "enc_x = (x - sum(keys)) % Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "255"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enc_x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "keys = [33, 52, 167, 55, 77]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "enc_x = (x - sum(keys)) % Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "92"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "enc_x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Because a field helps the numbers \"wrap\", it hides the extra information that we leaked without it. \n",
    "\n",
    "![Cats and Clocks](https://c.tenor.com/yz_7VcX0WjYAAAAd/cat-changing-the-clock-changing-the-time.gif \"A black cat is standing up and playing with the minute arm of a clock, tapping it forward playfully.\")\n",
    "\n",
    "\n",
    "### But Math?\n",
    "Currently this \"encryption scheme\" is not very helpful, because I can't do math with it... if I just wanted to encrypt and decrypt, there are a bunch of schemes I could use. We are here to do math!\n",
    "\n",
    "To make it easier, I just wanted to support addition. I could combine the secret with my \"keys\" so that if you add them all together, they equal the secret."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "Q = 431\n",
    "num_players = 5\n",
    "x = 45\n",
    "\n",
    "shares = [randrange(Q) for _ in range(num_players-1)]\n",
    "shares += [(x - sum(shares)) % Q]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[151, 262, 162, 200, 132]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shares"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "807"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(shares)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "45"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(shares) % Q"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Now let's try a negative number!\n",
    "\n",
    "We can start the same way as our sum, but think about modular math. What happens when you \"subtract\" time (i.e. come 13 hours before noon.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(12 - 13) + 24"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To keep our \"negative\" in our positive field space, we add our Q back... now let's see how it works with our current scheme...."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[93, 159, 31, 340, 184]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = -55\n",
    "\n",
    "shares = [randrange(Q) for _ in range(num_players-1)]\n",
    "shares += [(x - sum(shares)) % Q]\n",
    "\n",
    "shares"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# now, try to \"decrypt\" your secret! Hint: take a look at the \"addition result\" and your field...."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %load solutions/subtraction.py\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's make this easier by creating some helper functions to build our shares and combine them to decrypt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_additive_shares(secret, Q=431, num_players=5):\n",
    "    shares = [randrange(Q) for _ in range(num_players-1)]\n",
    "    shares += [(secret - sum(shares)) % Q]\n",
    "    return shares\n",
    "\n",
    "def decrypt(result, Q=431):\n",
    "    return result if result <= Q/2 else result - Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-33"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shares = create_additive_shares(-33)\n",
    "decrypt(sum(shares) % Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Replicated Secret Sharing\n",
    "\n",
    "What if we wanted to multiply instead of add?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 44\n",
    "b = 55\n",
    "Q=2147487"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "a_shares = create_additive_shares(a, Q=2147487, num_players=3)\n",
    "b_shares = create_additive_shares(b, Q=2147487, num_players=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These are then distributed to three players: each gets two shares from of each secret.\n",
    "\n",
    "Player 1 (owns A): keeps a1, a2, receives b2, b3\n",
    "Player 2 (owns B): keeps b1, b2, receives a1, a3\n",
    "Player 3: receives a2, a3, b1, b3\n",
    "\n",
    "\n",
    "c1= a1b2 + a1b3 + a2b2 \n",
    "\n",
    "c2= a1b1 + a3b1 + a3b2\n",
    "\n",
    "c3= a2b1 + a3b3 + a2b3\n",
    "\n",
    "\n",
    "c1 + c2 + c3 = a1(b1 + b2 + b3) + a2(b1 + b2 + b3) + a3(b1 + b2 + b3) \n",
    "\n",
    "             = (a1 + a2 + a3)(b1 + b2 + b3) \n",
    "             \n",
    "             = ab"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "a1, a2, a3 = a_shares\n",
    "b1, b2, b3 = b_shares"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# write a method to multiply the shares. It should take the first share and the second share. They need to be\n",
    "# multiplied together and stay in the field!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# %load solutions/multiply.py\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "887134"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c1 = multiply(a1, b2) + multiply(a1, b3) + multiply(a2, b2)\n",
    "c1 % Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "296786"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c2= multiply(a1, b1) + multiply(a3, b1) + multiply(a3, b2)\n",
    "c2 % Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "965987"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c3= multiply(a2, b1) + multiply(a3, b3) + multiply(a2, b3)\n",
    "c3 % Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2420"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(c1+c2+c3) % Q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2420"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a*b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see here though that if two of the players collude, they have enough to recover extra information about the secret. They might also use the final step to learn more about the other shares. To avoid this, each player can \"blind\" their intermediary value before sharing it and then reveal the blind to another party later.\n",
    "\n",
    "Player 1 has c1, adds blind (r1), receives c2+r2, keeps r1\n",
    "\n",
    "Player 2 has c2, adds blind (r2), receives c3+r3, keeps r2\n",
    "\n",
    "Player 3 has c3, adds blind (r3), receives c1+r1, keeps r3\n",
    "\n",
    "Player 1 calculates: c2+r2-r1\n",
    "\n",
    "Player 2 calculates: c3+r3-r2\n",
    "\n",
    "Player 3 calculates: c1+r1-r3\n",
    "\n",
    "Combined, they get c1+c2+c3 without leaking the extra information."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Challenge\n",
    "\n",
    "- Can you write a way to securely generate the blinds and pass them among the participants?"
   ]
  },
  {
   "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.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}