docs/user-guide/shamir.ipynb

{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. _shamir:\n",
    "\n",
    "Shamir Secret Sharing\n",
    "---------------------\n",
    "\n",
    "As one alternative to :class:`additive secret sharing <cicada.additive.AdditiveProtocolSuite>`, Cicada provides Shamir sharing, which supports the same set of mathematical and logical operations. Unlike additive sharing, Shamir's is a threshold scheme such that for any set of :math:`n` players, a threshold :math:`k` can be specified where any subset of :math:`n >= k` can reveal a secret.  To accomplish this, Shamir's scheme is based on creating and evaluating polynomials over an integral field.  To share a secret :math:`s` among :math:`n` parties with threshold :math:`k`, a random polynomial with the following form is generated over the field :math:`\\mathbb{Z}_p`, where the :math:`c` coefficients are all random field elements: \n",
    "\n",
    ".. math::\n",
    "\n",
    "  f(x)=(c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+\\dots+c_{2}x^{2}+c_{1}x+s)\\mod p\n",
    "\n",
    "\n",
    "After construction of the polynomial, the :math:`c` coefficients become the shares that are distributed among players. Reconstruction of the secret is accomplished with straightforward Lagrange interpolation. In the following, :math:`x` and :math:`y` with subscripts have their usual meaning in the context of successive points at which a polynomial is evaluated and the result of that evaluation respectively, and the subscripts denote the position of each within a list of such pairs:\n",
    "\n",
    ".. math::\n",
    "\n",
    "  s= f(0)=\\sum_{j=1}^{n}y_j \\prod_{k=1:k\\neq j}^{n} \\frac{-x_k}{x_j-x_k}\n",
    "\n",
    "Cicada defines two protocol suites that implement Shamir's scheme: :class:`~cicada.shamir.ShamirBasicProtocolSuite` supports a subset of operations that work with any :math:`k \\leq n`, while :class:`~cicada.shamir.ShamirProtocolSuite` provides the full set of operations supported by :class:`~cicada.additive.AdditiveProtocolSuite`, albeit with the constraint that\n",
    "\n",
    ".. math::\n",
    "\n",
    "  k \\leq \\frac{n+1}{2}\n",
    "\n",
    "Let's consider an example using :class:`~cicada.shamir.ShamirBasicProtocolSuite` that doubles a secret value using addition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:root:Player 0 value: 2.5\n",
      "INFO:root:Player 1 value: None\n",
      "INFO:root:Player 2 value: None\n",
      "INFO:root:Player 0 doubled value: 5.0\n",
      "INFO:root:Player 1 doubled value: 5.0\n",
      "INFO:root:Player 2 doubled value: 5.0\n"
     ]
    }
   ],
   "source": [
    "import logging\n",
    "logging.basicConfig(level=logging.INFO)\n",
    "\n",
    "import numpy\n",
    "\n",
    "from cicada.shamir import ShamirBasicProtocolSuite, ShamirProtocolSuite\n",
    "from cicada.communicator import SocketCommunicator\n",
    "from cicada.logging import Logger\n",
    "\n",
    "def main(communicator):\n",
    "    log = Logger(logging.getLogger(), communicator)\n",
    "    protocol = ShamirBasicProtocolSuite(communicator, threshold=3)\n",
    "\n",
    "    value = numpy.array(2.5) if communicator.rank == 0 else None\n",
    "    log.info(f\"Player {communicator.rank} value: {value}\")\n",
    "    \n",
    "    value_share = protocol.share(secret=value, src=0, shape=())\n",
    "    double_share = protocol.add(value_share, value_share)\n",
    "    double = protocol.reveal(double_share)\n",
    "\n",
    "    log.info(f\"Player {communicator.rank} doubled value: {double}\")\n",
    "\n",
    "SocketCommunicator.run(world_size=3, fn=main);"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    "Aside from using :class:`~cicada.shamir.ShamirBasicProtocolSuite`, this is identical to the code you would write to perform the same operation using :class:`~cicada.additive.AdditiveProtocolSuite`. \n",
    "\n",
    "To use multiplication or any operation dependent on multiplication, you must use :class:`~cicada.shamir.ShamirProtocolSuite` instead.  But, as we discussed above, it places stronger constraints on :math:`k` ... let's see what happens if we simply substitue :class:`~cicada.shamir.ShamirProtocolSuite` and try to square our secret value using multiplication:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "ERROR:cicada.communicator.socket:Comm world player 0 failed: ValueError('threshold must be <= 2, or world_size must be >= 5')\n",
      "ERROR:cicada.communicator.socket:Comm world player 1 failed: ValueError('threshold must be <= 2, or world_size must be >= 5')\n",
      "ERROR:cicada.communicator.socket:Comm world player 2 failed: ValueError('threshold must be <= 2, or world_size must be >= 5')\n"
     ]
    }
   ],
   "source": [
    "def main(communicator):\n",
    "    log = Logger(logging.getLogger(), communicator)\n",
    "    protocol = ShamirProtocolSuite(communicator, threshold=3)\n",
    "\n",
    "    value = numpy.array(2.5) if communicator.rank == 0 else None\n",
    "    log.info(f\"Player {communicator.rank} value: {value}\")\n",
    "    \n",
    "    value_share = protocol.share(secret=value, src=0, shape=())\n",
    "    square_share = protocol.multiply(value_share, value_share)\n",
    "    square = protocol.reveal(square_share)\n",
    "\n",
    "    log.info(f\"Player {communicator.rank} squared value: {square}\")\n",
    "\n",
    "SocketCommunicator.run(world_size=3, fn=main);"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    "... the program raises an exception when constructing the :class:`~cicada.shamir.ShamirProtocolSuite` object, because :math:`k` is too large for the given :math:`n`.  We can solve the problem by making :math:`k` smaller or :math:`n` larger.  Let's try the latter, and re-run the program with five players:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "INFO:root:Player 0 value: 2.5\n",
      "INFO:root:Player 1 value: None\n",
      "INFO:root:Player 2 value: None\n",
      "INFO:root:Player 3 value: None\n",
      "INFO:root:Player 4 value: None\n",
      "INFO:root:Player 0 squared value: 6.25\n",
      "INFO:root:Player 1 squared value: 6.25\n",
      "INFO:root:Player 2 squared value: 6.25\n",
      "INFO:root:Player 3 squared value: 6.25\n",
      "INFO:root:Player 4 squared value: 6.25\n"
     ]
    }
   ],
   "source": [
    "def main(communicator):\n",
    "    log = Logger(logging.getLogger(), communicator)\n",
    "    protocol = ShamirProtocolSuite(communicator, threshold=3)\n",
    "\n",
    "    value = numpy.array(2.5) if communicator.rank == 0 else None\n",
    "    log.info(f\"Player {communicator.rank} value: {value}\")\n",
    "    \n",
    "    value_share = protocol.share(secret=value, src=0, shape=())\n",
    "    square_share = protocol.multiply(value_share, value_share)\n",
    "    square = protocol.reveal(square_share)\n",
    "\n",
    "    log.info(f\"Player {communicator.rank} squared value: {square}\")\n",
    "\n",
    "SocketCommunicator.run(world_size=5, fn=main);"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    "Thus, Shamir offers straightforward resilience against data loss by allowing a subset of players to reveal data even after some players fail; however, this comes at a cost: it is less resistant to coalitions, since a sufficiently large coalition could reveal a secret that would otherwise remain private using additive sharing. Further, greater care is required to ensure that the number of players and threshold are chosen correctly, depending on the set of operations to be performed.\n",
    "\n",
    ".. seealso:: :ref:`active`"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "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.11.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}