Continuous-OT-MP-PSI/Shamir_Secret_Sharing.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8a105f7c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 15, 12, 18]\n",
      "18*x^3 + 12*x^2 + 15*x\n",
      "share 1: 7\n",
      "share 2: 13\n",
      "share 3: 12\n",
      "share 4: 17\n",
      "share 5: 3\n",
      "share 6: 2\n",
      "[(1, 7), (2, 13), (3, 12), (4, 17), (5, 3), (6, 2)]\n",
      "0\n",
      "[0, 15, 12, 18]\n",
      "0\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "import hashlib\n",
    "import random\n",
    "\n",
    "# Prime order of the finite field\n",
    "q = 19\n",
    "\n",
    "Fq = GF(q)\n",
    "R = PolynomialRing(Fq,\"x\")\n",
    "\n",
    "t = 4\n",
    "m = 7\n",
    "S = 0\n",
    "\n",
    "coefficients = []\n",
    "coefficients.append(S)\n",
    "for i in range(1, t):\n",
    "    coefficients.append(Fq.random_element())\n",
    "\n",
    "print(coefficients)\n",
    "\n",
    "f_x = R(coefficients)\n",
    "print(f_x)\n",
    "shares = []\n",
    "for i in range(1, m):\n",
    "    print(f\"share {i}: {f_x(i)}\")\n",
    "    shares.append((i, f_x(i)))\n",
    "\n",
    "def secret_recovery(shares): \n",
    "    return sum([i[1] * prod([(0-j[0] * pow(i[0] - j[0], -1, q)) for j in shares[:t] if i[0] != j[0]]) for i in shares[:t]])\n",
    "\n",
    "S_man = 0\n",
    "for i in shares[:t]:\n",
    "    im_prod = i[1]\n",
    "    for j in shares[:t]:\n",
    "        if j[0] != i[0]:\n",
    "            im_prod *= ((-j[0]) * pow(i[0] - j[0], -1, q)) % q\n",
    "    S_man += im_prod\n",
    "        \n",
    "\n",
    "print(shares)\n",
    "S_sage = R.lagrange_polynomial(shares[:t])\n",
    "print(S_sage[0])\n",
    "print(coefficients)\n",
    "print(S_man % q)\n",
    "print(secret_recovery(shares[:t]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "e5c47c9d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Information Word a: \t[0, 15, 10, 13, 13, 17, 5, 2, 8, 12, 7]\n",
      "Code Word D: \t\t[7, 9, 5, 9, 0, 2, 9, 1, 7, 16, 17, 12, 18, 6, 12, 11, 8, 3]\n",
      "a_0: \t\t\t0\n",
      "Manipulated Codeword: \t[6, 9, 5, 9, 0, 2, 9, 1, 7, 16, 16, 12, 18, 6, 12, 11, 8, 3]\n",
      "a_0: \t\t\t2\n"
     ]
    }
   ],
   "source": [
    "non_zero_elem_of_Fq = [x for x in Fq if x != 0]\n",
    "k = 11\n",
    "\n",
    "information_word = []\n",
    "information_word.append(S)\n",
    "for _ in range(0, k-1):\n",
    "    information_word.append(Fq.random_element())\n",
    "\n",
    "print(f\"Information Word a: \\t{information_word}\")\n",
    "\n",
    "code_word = []\n",
    "for i in range(0, q-1):\n",
    "    code_word.append(sum([information_word[j] * pow(non_zero_elem_of_Fq[i], j) for j in range(0, k)]))\n",
    "\n",
    "print(f\"Code Word D: \\t\\t{code_word}\")\n",
    "\n",
    "secret = -sum([code_word[d] for d in range(0, q-1)])\n",
    "print(f\"a_0: \\t\\t\\t{secret}\")\n",
    "\n",
    "assert(secret == information_word[0] == S)\n",
    "\n",
    "manipulated_codeword = []\n",
    "for i in range(0, len(code_word)):\n",
    "    if i % 10 == 0:\n",
    "        manipulated_codeword.append(code_word[i]-1 % q)\n",
    "    else:\n",
    "        manipulated_codeword.append(code_word[i])\n",
    "\n",
    "print(f\"Manipulated Codeword: \\t{manipulated_codeword}\")\n",
    "\n",
    "secret_man = -sum([manipulated_codeword[d] for d in range(0, q-1)])\n",
    "print(f\"a_0: \\t\\t\\t{secret_man}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cff95199",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "152ae6a0",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.6",
   "language": "sage",
   "name": "sagemath"
  },
  "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}